Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Страницы: < 1 2 3 4 >
kudatsky © (2010-04-22 11:54:00)
На экране находится не выпуклый многоугольник, заданный координатами X1,Y1,X2,Y2,X3,Y3 и т.д. Задана точка X,Y. Как определить, находится ли точка внутри фигуры ? Нет ли для этого системной функции ?

Ins (2010-04-25 00:56:00) [21]

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

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

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

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

Ins (2010-04-25 00:43:00) [23]

> Не скажет.

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

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

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

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

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

Дмитрий Белькевич (2010-04-25 00:18:00) [25]
Мне, например, не для хиттеста нужна. Забираю алгоритмом выделенный массив точек (векторный редактор). Если несколько потеряется по краям - то не критично, даже и не знал, что проблема существует.

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

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

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

Не скажет.

Ins (2010-04-24 23:56:00) [27]

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

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

Игорь Шевченко (2010-04-24 23:35:00) [28]

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

Например я :)

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

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

Ins (2010-04-24 23:22:00) [29]

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

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

Sha (2010-04-24 14:45:00) [30]
Все ранее приведенные функции на границах региона дают результат, отличающийся от 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;

Leonid Troyanovsky (2010-04-24 10:39:00) [31]

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

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

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

--
Regards, LVT.

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

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

Вася (2010-04-24 05:24:00) [33]
по тестам вроде создать регион и проверить попадание в него на winapi быстрее будет...=\

antonn (2010-04-23 22:14:00) [34]
Спасибо :)

Игорь Шевченко (2010-04-23 21:06:00) [35]
Sha © (23.04.10 19:10) [29]
MBo © (23.04.10 18:50) [28]

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

Sha (2010-04-23 19:10:00) [36]
>> 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 будет выполнен, если точка лежит под/над отрезком.

MBo (2010-04-23 18:50:00) [37]
>можно для бестолковых этот участок кода перевести ?
Это сравнение знаков dx1 и dx2 - вопрос об этом?

Игорь Шевченко (2010-04-23 18:24:00) [38]

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

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

Sha (2010-04-23 14:32:00) [39]
Можно заметить, что в выражениях для соседних отрезков имеется общая часть.
Это можно использовать для дополнительного ускорения функции:
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 01:27:00) [40]
Неплохо. Оптимизацию по скорости почти не делал - так только - убрал очевидное. Тоже как-то замечал, что const/var в параметрах может ускорить обработку - убирается косвенный доступ к массивам.

Страницы: < 1 2 3 4 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »