Попадает ли точка в замкнутый многоугольник

← →
kudatsky (2010-04-22 11:54) [0]

На экране находится не выпуклый многоугольник, заданный координатами X1,Y1,X2,Y2,X3,Y3 и т.д. Задана точка X,Y. Как определить, находится ли точка внутри фигуры ? Нет ли для этого системной функции ?

← →
oldman © (2010-04-22 12:11) [1]

> Нет ли для этого системной функции ?

Огорчу. Нет.

← →
Дмитрий Белькевич (2010-04-22 12:14) [2]

function IsPointInPolygon(X, Y: integer; TepmPolyLine: TDAPoint): boolean; var i, n: integer; begin i := 0; n := Length(TepmPolyLine) - 1; Result := False; repeat if not ((y > TepmPolyLine[i].Y) xor (y <= TepmPolyLine[i + 1].Y)) then if x - TepmPolyLine[i].X < (y - TepmPolyLine[i].Y) * (TepmPolyLine[i + 1].X - TepmPolyLine[i].X) / (TepmPolyLine[i + 1].Y - TepmPolyLine[i].Y) then Result := not Result; i := i + 1; until i >= n; end;

TDAPoint = array of TPoint;

Системной - не видел.

← →
kudatsky (2010-04-22 12:26) [3]

Дмитрий, спасибо !
Сейчас буду разбираться !

← →
Leonid Troyanovsky © (2010-04-22 12:27) [4]

> Дмитрий Белькевич (22.04.10 12:14) [2]

> Системной - не видел.

PtInRegion ?

--
Regards, LVT.

← →
Омлет © (2010-04-22 13:53) [5]

> Дмитрий Белькевич (22.04.10 12:14) [2]

Работает неверно.

← →
Омлет © (2010-04-22 14:02) [6]

Пардон. Работает верно, но если последняя точка в массиве совпадает с первой.

← →
Омлет © (2010-04-22 14:09) [7]

Если использовать PtInRegion, то можно не замыкать точки.

function IsPointInPolygon(X, Y: integer; Points: TDAPoint): boolean; var Rgn : HRGN; begin Result := False; Rgn := CreatePolygonRgn(Pointer(@Points[0])^, Length(Points), WINDING); if Rgn <> 0 then begin Result := PtInRegion(Rgn, X, Y); DeleteObject(Rgn); end; end;

← →
Sha © (2010-04-22 14:10) [8]

А ничего, что за границу массива выходит?

← →
Sha © (2010-04-22 14:11) [9]

[8] относится к [2]

← →
kudatsky (2010-04-22 14:15) [10]

Всё прекрасно работает.
Всем спасибо ;-)))

← →
Ins © (2010-04-22 14:39) [11]

> А ничего, что за границу массива выходит?

Не выходит:

> i := i + 1;
>until i >= n;

> Омлет © (22.04.10 14:09) [7]
> Если использовать PtInRegion, то можно не замыкать точки.
>

Зато скорость выполнения в сотни раз может быть больше. Регион - это множество непересекающихся прямоугольников. Если их сотни, то и сотни раз проверить на вхождение (в каждый) нужно.

← →
Ins © (2010-04-22 14:42) [12]

> Зато скорость выполнения

Время выполнения, оговорился...

← →
Sha © (2010-04-22 14:53) [13]

> Ins © (22.04.10 14:39) [11]

Да, точно. По инерции считал, что n - количество точек.

← →
Sha © (2010-04-22 15:59) [14]

Алгоритм [2] не работает, если точка лежит левее последнего отрезка
и ее ордината лежит между ординатами последнего отрезка.

Например, для квадрата a[0].y:=0; a[0].x:=2; a[1].y:=0; a[1].x:=0; a[2].y:=2; a[2].x:=0; a[3].y:=2; a[3].x:=2;

Подправить можно так:
function ShaIsPointInPolygon(X, Y: integer; TepmPolyLine: TDAPoint): boolean; var i1, i2: integer; begin Result:=false; i2:=0; i1:=Length(TepmPolyLine)-1; while i1>=0 do begin; if not ((TepmPolyLine[i1].x < x) xor (x <= TepmPolyLine[i2].x)) then if y - TepmPolyLine[i1].y < (x - TepmPolyLine[i1].x) * (TepmPolyLine[i2].y - TepmPolyLine[i1].y) / (TepmPolyLine[i2].x - TepmPolyLine[i1].x) then Result:=not Result; i2:=i1; i1:=i1-1; end; end; procedure TForm1.Button2Click(Sender: TObject); var a: TDAPoint; x, y: integer; begin; SetLength(a,4); a[0].y:=0; a[0].x:=2; a[1].y:=0; a[1].x:=0; a[2].y:=2; a[2].x:=0; a[3].y:=2; a[3].x:=2; x:=1; y:=1; Memo1.Lines.Add(IntToStr(Ord(IsPointInPolygon(x, y, a)))); Memo1.Lines.Add(IntToStr(Ord(ShaIsPointInPolygon(x, y, a)))); end;

← →
Омлет © (2010-04-22 16:41) [15]

> Sha © (22.04.10 15:59) [14]
> Алгоритм [2] не работает, если точка лежит левее последнего отрезка

Если замкнуть точки (т.е. чтобы последняя была равна первой), то работает.

← →
Дмитрий Белькевич (2010-04-22 16:45) [16]

> [8] относится к [2]

Алгоритм рабочий. N - количетво точек минус одну, да. Что бы лишних телодвижений не делать в цикле.

За [14] спасибо. Проверю.

← →
Дмитрий Белькевич (2010-04-22 16:49) [17]

> Если замкнуть точки (т.е. чтобы последняя была равна первой),
> то работает.

+1. У меня замыкается.

← →
Sha © (2010-04-22 16:57) [18]

> Омлет © (22.04.10 16:41) [15]
> Если замкнуть точки (т.е. чтобы последняя была равна первой), то работает.

Очень похоже на костыль.

← →
Sha © (2010-04-22 16:59) [19]

> Дмитрий Белькевич (22.04.10 16:45) [16]
> За [14] спасибо. Проверю.

Надо иметь в виду, что в нем массив не замыкается.

← →
Sha © (2010-04-22 17:00) [20]

Еще у этого алгоритма есть одно слабое место:
он дает разные ответы, в случаях когда точка лежит на левом или правом отрезке.
Имеет смысл включить границы, заменив неравенство на нестрогое в последнем if

← →
Sha © (2010-04-22 17:05) [21]

Sha © (22.04.10 17:00) [20]

Хотя нет, не подумал, это не поможет.

← →
Дмитрий Белькевич (2010-04-22 19:31) [22]

> Очень похоже на костыль.

Возможно. Попробую [14].

← →
Sha © (2010-04-23 00:30) [23]

Кстати, можно в несколько раз повысить скорость вычислений алгоритма [14].
если изменить объявление параметров функции следующим образом:
function ShaIsPointInPolygon(X, Y: integer; var TepmPolyLine: TDAPoint): boolean;

Можно ускорить функцию еще примерно в полтора раза,
но уже ценой ухудшения читаемости кода:
function ShaIsPointInPolygon2(Pt: PPoint; Poly: PPoint; Count: integer): boolean; type TPointArray = array[0..$6ffffff] of TPoint; PPointArray = ^TPointArray; var Last: PPoint; Cross, dxLine, dxPoint, xOld, yOld: integer; Internal: boolean; begin; Last:=@PPointArray(Poly)[Count-1]; with Last^ do begin; xOld:=x; yOld:=y; end; Cross:=0; Internal:=true; repeat; dxPoint:=Poly.x - Pt.x; xOld:=xOld - Pt.x; if dxPoint xor xOld<0 then begin; dxLine:=dxPoint - xOld; yOld:=(yOld - Poly.y) * dxPoint + (Poly.y - Pt.y) * dxLine; if yOld=0 then Internal:=not Internal else Cross:=Cross xor yOld xor dxLine; end; xOld:=Poly.x; yOld:=Poly.y; inc(Poly); until dword(Poly)>dword(Last); Result:=boolean(Cross shr 31) and Internal; end;

В последнем варианте функции передаются три параметра:
указатель на проверяемую точку,
указатель на первую вершину многоугольника,
количество вершин многоугольника.

Для точек, лежащих на границе многоугольника, поведение этой функции
единообразно: граничные точки не считаются внутренними.
Это отличается от предыдущей функции, которая может возвращать произвольный результат.

← →
Sha © (2010-04-23 01:09) [24]

Если требуется совместимость с алгоритмом [14]
(границы с меньшими абсциссами/ординатами включаются, с большими - исключаются),
то можно использовать такую модификацию алгоритма:
function ShaIsPointInPolygon3(Pt: PPoint; Poly: PPoint; Count: integer): boolean; type TPointArray = array[0..$6ffffff] of TPoint; PPointArray = ^TPointArray; var Last: PPoint; Cross, dxLine, dxPoint, xOld, yOld: integer; begin; Last:=@PPointArray(Poly)[Count-1]; with Last^ do begin; xOld:=x; yOld:=y; end; Cross:=0; repeat; dxPoint:=Poly.x - Pt.x; xOld:=xOld - Pt.x; if dxPoint xor xOld<0 then begin; dxLine:=xOld - dxPoint; yOld:=(yOld - Poly.y) * dxPoint + (Pt.y - Poly.y) * dxLine; if yOld<>0 then Cross:=Cross xor yOld xor dxLine; end; xOld:=Poly.x; yOld:=Poly.y; inc(Poly); until dword(Poly)>dword(Last); Result:=boolean(Cross shr 31); end;

← →
Дмитрий Белькевич (2010-04-23 01:27) [25]

Неплохо. Оптимизацию по скорости почти не делал - так только - убрал очевидное. Тоже как-то замечал, что const/var в параметрах может ускорить обработку - убирается косвенный доступ к массивам.

← →
Sha © (2010-04-23 14:32) [26]

Можно заметить, что в выражениях для соседних отрезков имеется общая часть.
Это можно использовать для дополнительного ускорения функции:
type TPointArray = array[0..$0ffffffe] of TPoint; PPointArray = ^TPointArray; function ShaIsPointInPolygon1(Pt: PPoint; Poly: PPoint; Count: integer): boolean; var Last: PPoint; dx1, dx2, Delta, yOld, Res: integer; begin; Res:=0; Last:=@PPointArray(Poly)[Count-1]; with Last^ do begin; dx1:=x - Pt.x; yOld:=y; end; repeat; dx2:=Poly.x - Pt.x; if dx1 xor dx2 < 0 then begin; dx1 := dx1 - dx2; Delta := (Pt.y - Poly.y) * dx1 + (yOld - Poly.y) * dx2; if Delta<>0 then Res:=Res xor dx1 xor Delta; end; yOld:=Poly.y; inc(Poly); if dword(Poly)>dword(Last) then break; dx1:=Poly.x - Pt.x; if dx2 xor dx1 < 0 then begin; dx2 := dx2 - dx1; Delta := (Pt.y - Poly.y) * dx2 + (yOld - Poly.y) * dx1; if Delta<>0 then Res:=Res xor dx2 xor Delta; end; yOld:=Poly.y; inc(Poly); until dword(Poly)>dword(Last); Result:=boolean(Res shr 31); end;

← →
Игорь Шевченко © (2010-04-23 18:24) [27]

> dx2:=Poly.x - Pt.x;
> if dx1 xor dx2 < 0 then begin;

можно для бестолковых этот участок кода перевести ?

← →
MBo © (2010-04-23 18:50) [28]

>можно для бестолковых этот участок кода перевести ?
Это сравнение знаков dx1 и dx2 - вопрос об этом?

← →
Sha © (2010-04-23 19:10) [29]

>> if dx1 xor dx2 < 0 then begin;
> можно для бестолковых этот участок кода перевести

Общая идея алгоритма: проводим из точки луч верикально вверх
и узнаем четность числа его пересечений со сторонами многоугольника.

Сравнением dx1 xor dx2 < 0 мы проверяем выполние одного условий
Poly.x < Pt.x <= Old.x
Old.x < Pt.x <= Poly.x
где Poly и Оld - координаты концов отрезка, Pt - наша точка.

Т.о. блок begin будет выполнен, если точка лежит под/над отрезком.

← →
Игорь Шевченко © (2010-04-23 21:06) [30]

Sha © (23.04.10 19:10) [29]
MBo © (23.04.10 18:50) [28]

Круто. Но нифига не понятно с первого взгляда. Хоть бы скобки поставлены были...

← →
antonn © (2010-04-23 22:14) [31]

Спасибо :)

← →
Вася (2010-04-24 05:24) [32]

по тестам вроде создать регион и проверить попадание в него на winapi быстрее будет...=\

← →
Sha © (2010-04-24 10:17) [33]

> Вася (24.04.10 05:24) [32]
> по тестам вроде создать регион и проверить попадание в него на winapi быстрее будет...=\

Хотелось бы увидеть

← →
Leonid Troyanovsky © (2010-04-24 10:39) [34]

> Вася (24.04.10 05:24) [32]

> на winapi быстрее будет...=\

http://support.microsoft.com/kb/121960

--
Regards, LVT.

← →
Sha © (2010-04-24 14:45) [35]

Все ранее приведенные функции на границах региона дают результат, отличающийся от PtInRegion.
Для совместимости с API пришлось пускать луч вдоль оси X и поменять порядок анализа концов отрезков.
На моих тестах следующая функция выдает результат, совпадающий с API-шной PtInRegion,
но работает в разы быстрее (без учета времени на создание/удаление региона).
Разумеется, полная совместимость не гарантируется.
function ShaIsPointInPolygon4(Pt: PPoint; Poly: PPoint; Count: integer): boolean; var Last: PPoint; dy1, dy2, Delta, xOld, Res: integer; begin; Res:=0; Last:=@PPointArray(Poly)[Count-1]; with Last^ do begin; dy1:=Pt.y - y; xOld:=x; end; repeat; dy2:=Pt.y - Poly.y; if dy1 xor dy2 < 0 then begin; dy1 := dy1 - dy2; Delta := (Pt.x - Poly.x) * dy1 + (xOld - Poly.x) * dy2; if Delta<>0 then Res:=Res xor dy1 xor Delta; end; xOld:=Poly.x; inc(Poly); if dword(Poly)>dword(Last) then break; dy1:=Pt.y - Poly.y; if dy2 xor dy1 < 0 then begin; dy2 := dy2 - dy1; Delta := (Pt.x - Poly.x) * dy2 + (xOld - Poly.x) * dy1; if Delta<>0 then Res:=Res xor dy2 xor Delta; end; xOld:=Poly.x; inc(Poly); until dword(Poly)>dword(Last); Result:=boolean(Res shr 31); end;

← →
Ins © (2010-04-24 23:22) [36]

> Все ранее приведенные функции на границах региона дают результат,
> отличающийся от PtInRegion.

А кто сказал, что именно PtInRegion дает на границах правильный результат? Регион, полученный вызовом CreatePolygonRgn, это не многоугольник, а его грубое пиксельное приближение со всеми вытекающими... Да и кому нужна эта строгая точность на границах, учитывая что функция наверняка нужна для HitTest-а

← →
Игорь Шевченко © (2010-04-24 23:35) [37]

> А кто сказал, что именно PtInRegion дает на границах правильный
> результат?

Например я :)

А для хит-теста народ рекомендует вот такой более быстрый способ.

http://support.microsoft.com/kb/121960

← →
Ins © (2010-04-24 23:56) [38]

> Например я :)

Дан многоугольник (треугольник), координаты вершин:
(0; 0)
(6; 0)
(3; 10)
Берем точку (0;1). Очевидно, чисто геометрически она не входит в многоугольник, но PtInRegion вам скажет иначе

← →
Sha © (2010-04-25 00:08) [39]

> Игорь Шевченко © (24.04.10 23:35) [37]
> А для хит-теста народ рекомендует вот такой более быстрый способ.
> http://support.microsoft.com/kb/121960

Вовсе он и не быстрый.

> Ins © (24.04.10 23:56) [38]
> Очевидно, чисто геометрически она не входит в многоугольник, но PtInRegion вам скажет иначе

Не скажет.

← →
Дмитрий Белькевич (2010-04-25 00:18) [40]

Мне, например, не для хиттеста нужна. Забираю алгоритмом выделенный массив точек (векторный редактор). Если несколько потеряется по краям - то не критично, даже и не знал, что проблема существует.

← →
Sha © (2010-04-25 00:27) [41]

> Дмитрий Белькевич (25.04.10 00:18) [40]
> даже и не знал, что проблема существует.

Существует. PtInRegion теряет точки на правой и нижней границе.

Это не проблема, если регионы прямоугольные и имеют общие границы, параллельные осям.

Но в общем случае это может привести к выпадению точек между регионами,
даже если у них общая граница.

← →
Ins © (2010-04-25 00:43) [42]

> Не скажет.

А, ну да, он лишнего не включает, насколько я вижу, скорее теряет недостающее. Да в любом случае никакой геометрической точности тут нет и быть не может в силу природы регионов - они "ступенчатые", растровые, а не векторные.

← →
Игорь Шевченко © (2010-04-25 00:51) [43]

Ins © (25.04.10 00:43) [42]

В компьютере все дискретно...

← →
Ins © (2010-04-25 00:56) [44]

> В компьютере все дискретно...

Это понятно, вопрос только насколько эта дискретность грубая. Так есть ли повод утверждать, что именно PtInRegion на границе считает правильно, и равнять под него алгоритм с меньшей степенью грубости?

← →
Sha © (2010-04-25 01:18) [45]

Нормально, вроде, он считает.
Более того, никак не удается построить пример выпадения точек у регионов с общими границами.
Похоже, в [41] я заблуждался насчет выпадения.

Ins © (25.04.10 00:56) [44]

> Это понятно, вопрос только насколько эта дискретность грубая.
> Так есть ли повод утверждать, что именно PtInRegion на
> границе считает правильно, и равнять под него алгоритм с
> меньшей степенью грубости?

Не совсем понимаю, в чем проблема - внутренняя структура региона тайны не представляет, определить, принадлежит ли точка всем прямоугольникам из этой структуры задача вполне однозначно осуществимая.

Допустим, на плоскости заданы 4 точки с целочисленными координатами,
являющиеся вершинами горизонтально расположенного прямоугольника.

Добавим к этому множеству точек произвольное количество новых точек,
лежащих внутри или на границах прямоугольника и также имеющих
целочисленные координаты.
> Игорь Шевченко © (25.04.10 01:33) [46]

Затем создадим множество непересекающихся многоугольников произвольной формы, используя в качестве их вершин наше множество точек.

Нам хотелось бы, чтобы функция, определяющая принадлежность точек
многоугольникам, относила каждую внутреннюю точку исходного прямоугольника,
а также точки, лежащие на его верхней и левой сторонах,
в точности к одному многоугольнику
и считала, что точки, лежащие на правой и нижней сторонах,
не входят ни в один многоугольник.

Вопрос в том, является ли PtInRegion такой функцией?
Все говорит за то, что является.

Окошко для редактирования текста маловато.
В результате так фигово пост [47] оформлен, но смысл должен быть понятен.

> В результате так фигово пост [47] оформлен

А в чём собственно "фиговость"? Читается нормально.

В [47] подразумевается, что общая площадь многоугольников равна площади исходного прямоугольника, т.е. он разрезан на многоугольники.

> Германн © (25.04.10 02:19) [49]
> А в чём собственно "фиговость"?

Лесенка строк режет глаз. От цитаты остался заголовок, который затесался в середину текста.

> Ins © (25.04.10 00:43) [42]
> он лишнего не включает, насколько я вижу, скорее теряет

Это псевдо-потеря. Граничная точка, как и любая другая, должна входить только в один регион. Вот она и входит в соседний регион, даже если он воображаемый.

> Sha © (25.04.10 02:21) [50]
>
> В [47] подразумевается, что общая площадь многоугольников
> равна площади исходного прямоугольника, т.е. он разрезан
> на многоугольники.

Так ты про суть или про оформление?

> Германн © (25.04.10 02:34) [52]
> Так ты про суть или про оформление?

В [47] коряво оформлено корявое изложение совершенно очевидной вещи :)

Если мы при помощи PtInRegion возьмемся красить точки каждого многоугольника в свой цвет,
то у нас не останется неокрашенных и не придется перекрашивать.

Лучше я уж промолчу.

> Sha © (25.04.10 02:31) [51]

Да, это фишка Windows при работе с прямоугольниками - на пиксель меньше, даже при рисовании проявляется

> Не совсем понимаю, в чем проблема - внутренняя структура
> региона тайны не представляет, определить, принадлежит ли
> точка всем прямоугольникам из этой структуры задача вполне
> однозначно осуществимая.

Брр... Нисколько в этом не сомневаюсь, я и не о том вообще... Тут выше была попытка адаптировать алгоритм с другой логикой так, чтобы он работал именно как PtInRegion. А зачем? Если этот алгоритм работает вполне правильно (я считаю, что точнее), то какая разница как работает PtInRegion, у которого свои причуды? Или эти причуды во что бы то ни стало должны быть одинаковыми?

> Граничная точка, как и любая другая, должна входить только
> в один регион.

Кому это она должна? :) Это смотря в какой задаче

Ins © (25.04.10 11:51) [56]

> А зачем? Если этот алгоритм работает вполне правильно (я
> считаю, что точнее), то какая разница как работает PtInRegion,
> у которого свои причуды? Или эти причуды во что бы то ни
> стало должны быть одинаковыми?

Я сильно извиняюсь, а какие причуды у PtInRegion ?

> Ins © (25.04.10 11:45) [55]
> Да, это фишка Windows при работе с прямоугольниками - на пиксель меньше, даже при рисовании проявляется

Если работать только с прямоугольными регионами, то можно подумать, что Windows исключает правую и нижнюю границу по одной и той же причине.
На самом деле это не так.
Обычно лучевой алгоритм проверки вхождения точки в регион проверяет, что точка находится строго левее линии. Поэтому вся левая граница не принадлежит региону. Если заменить равенство на нестрогое, то лучше не станет - тогда пропадет правая граница.
С нижней границей дело обстоит иначе. Очевидно, алгоритм не должен считать дважды перечение луча с границей многоугольника в случае когда луч проходит точно через его вершину. Поэтому алгоритм не учитывает концы отрезков, имеющих бОльшую ординату. Это выглядит как срезание локальных выступов снизу региона, а не как полное исключение нижней границы.
Поэтому, например, невозможно создать такой регион, в который входили бы точки, помеченные буквой "о" на рисунке
..o... .ooo.. ooooo. .ooo.. ..o...
из-за среза правой границы получим
...... .oo... oooo.. .oo... ......
а если сдублировать границу вот так
..oo.. .oooo. oooooo .oooo. ..oo..
то будет еще хуже
..o... .ooo.. ooooo. .ooo.. ......

> Или эти причуды во что бы то ни стало должны быть одинаковыми?

Одинаковость причуд говорит о возможной одинаковости алгоритмов.

>> Граничная точка, как и любая другая, должна входить только в один регион.
> Кому это она должна? Это смотря в какой задаче.

Это да.

Если мы выводим на экран сформированное в многоугольниках изображение, нам будет приятно сознавать, что на экране не будет дыр и избражения не перекрываются. Тут подходит, например, алгоритм совместимый с PtInRegion.

А если мы показываем на однотонном фоне какой-нибудь геометрический объект, например, пирамиду, то имеет смысл отрисовать его четкие границы.
Приведенный алгоритм может быть легко модифицирован для этой задачи

> Sha © (25.04.10 13:01) [58]

Написано:

> Обычно лучевой алгоритм проверки вхождения точки в регион проверяет,
> что точка находится строго левее линии.
> Поэтому вся левая граница не принадлежит региону.
> Если заменить равенство на нестрогое, то лучше не станет - тогда пропадет правая граница.

Читать так:

Обычно лучевой алгоритм проверки вхождения точки в регион проверяет,
что точка находится строго левее линии.
Поэтому вся правая граница не принадлежит региону.
Если заменить равенство на нестрогое, то лучше не станет - тогда пропадет левая граница.

> Sha (25.04.2010 13:09:59) [59]

Насколько я знаю, правая координата не указывается, а то что кажется координатой, на самом деле является длиной.
Поеэтому прямоугольник на 0, 32 - это не прямоугольник на 33 пикселя. Это обсуждали в Борландовских конференциях лет 10 назад.

> Одинаковость причуд говорит о возможной одинаковости алгоритмов.

Едва ли... Для этого необходимо чтобы регион Windows хранил информацию о своих исходных данных, в данном случае - о том, что это многоугольник с такими-то вершинами. Насколько я знаю, такие данные он не хранит, он хранит массив прямоугольников, которые являются приближением к этому полигону. А выпадение правой и нижней границы объясняется особенностями работы с прямоугольниками.

> Ins © (25.04.10 19:17) [62]
> Для этого необходимо чтобы регион Windows хранил информацию о своих исходных данных...

Нет, не необходимо.

> Насколько я знаю, такие данные он не хранит, он хранит массив прямоугольников...

Эти самые прямоугольники вполне могли быть построены по лучевому алгоритму.

> А выпадение правой и нижней границы объясняется особенностями работы с прямоугольниками.

Интересно, какими особенностями работы с прямоугольниками можно объяснить различия (о которых я писал) в выпадении правой и нижней границы?
Лучевой алгоритм их прекрасно объясняет.

Хотя, наверно, и другие алгоритмы могут приводить к тем же особенностям.
Ну, это только к лучшему.

Попадает ли точка в замкнутый многоугольник Найти похожие ветки