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

← →
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 - вопрос об этом?

>> 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 будет выполнен, если точка лежит под/над отрезком.

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

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

Спасибо :)

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

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

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

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

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

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

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

--
Regards, LVT.

Все ранее приведенные функции на границах региона дают результат, отличающийся от 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;

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

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

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

Например я :)

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

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

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

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

> Игорь Шевченко © (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]

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

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