Определение положения точки относительно полигона

← →
Хинт © (2006-03-25 22:01) [0]

Определение положения точки относительно произвольного полигона. У кого-нибудь есть алгоритм?

← →
Sergey Masloff (2006-03-25 22:03) [1]

В смысле? Внутри-снаружи?

← →
Хинт © (2006-03-25 22:06) [2]

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

← →
palva © (2006-03-25 22:18) [3]

X1 ... Xn - вершины. O - точка.
Считаем угол (ориентированный) между OXi и OXi+1 обходя многоугольник по всем вершинам. Результаты суммируем. Если получился 0, то вне многоугольинка. Если 2пи, то многоугольник охватывает точку один раз, 4пи - два раза и т. д.

← →
Хинт © (2006-03-25 22:30) [4]

2palva
Спасибо. А этот алгоритм подходит для НЕ выпуклых многоугольников?

← →
palva © (2006-03-25 22:55) [5]

Подходит. Но, возможно, есть не такой дубовый алгоритм. Если Ox - x-координата точки O, то проведем прямую y=Ox и попробуем найти точки пересечения каждой из сторон (отрезка) с прямой. Если число пересечений слева от точки O четно, то точка вне многоугольника. На самом деле большинство сторон не надо обсчитывать, достаточно сравнить координаты и сделать вывод, что пересечения нет или оно будет лежать справа от точки O. Также следует отловить случаи, когда прямая проходит через вершину. Получается довольно сложный логически алгоритм, но он, наверно, самый эффективный. Может быть где-то в интернете есть.

← →
isasa © (2006-03-25 23:03) [6]

Очень изящно было для прямоугольника, но, по моему, пойдет и для полигонов
http://delphimaster.net/view/1-1143053545/
grisme © (23.03.06 17:37) [10]

← →
DiamondShark © (2006-03-25 23:08) [7]

А что значит "Определение положения точки" ? Внутри/Снаружи?

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

← →
wal © (2006-03-27 09:39) [8]

А что значит "внутри-снаружи" для самопересекающегося полигона? Например, классическая звездочка.

С уважением.

← →
Юрий Зотов © (2006-03-27 11:36) [9]

CreatePolygonRgn + PtInRegion.

← →
McSimm © (2006-03-27 11:39) [10]

> DiamondShark © (25.03.06 23:08) [7]

только через вершину проводить нежелательно

← →
ShaggyDoc (2006-03-27 13:56) [11]

http://algolist.manual.ru/maths/geom/belong/

← →
Хинт © (2006-03-27 15:45) [12]

> Считаем угол (ориентированный) между OXi и OXi+1

А как посчитать этот самый ориентированный угол? =)

← →
Хинт © (2006-03-27 16:38) [13]

2palva
Алгоритм в [3] работает только с выпуклыми многоугольниками :(
По крайней мере у меня получилось именно так

← →
isasa © (2006-03-27 16:53) [14]

Хинт © (27.03.06 16:38) [13]
Попробуй учесть знак.
Например, угол для стороны, разворачивается по часовой - "+", против - "-"

← →
oldman © (2006-03-27 17:01) [15]

Старый добрый баян:

1. красим фон белым.
2. красим полигон черным.
3. координаты точки есть (х, у)
4. проверяем цвет точки А(х,у)...

Старый, проверенный способ!!!

← →
Jeer © (2006-03-27 17:17) [16]

Просто красим полигон
Далее - 3, 4

← →
Хинт © (2006-03-27 18:34) [17]

В том-то и дело, что надо написать полноценный алгоритм. Иначе я бы воспользовался [9].

Хинт © (27.03.06 15:45) [12]
>> Считаем угол (ориентированный) между OXi и OXi+1
> А как посчитать этот самый ориентированный угол? =)

Ну как-нибудь из аналитической геометрии: Вычисляем сначала косинус из скалярного произведения, а затем величину угла от 0 до 2пи. Вычислим также ориентированную площадь параллелограмма, построенного на векторах OXi и OXi+1 (как определитель, составленный из координат). Нам понадобится только знак этой площади. Теперь, если угол меньше развернутого, то полагаем, что знак угла совпадает со знаком площади. Если величина угла больше пи, то полагаем его знак противоположным знаку площади. Если угол равен развернутому, то точка лежит на стороне многоугольника и задача теряет смысл.

Положительный угол означает, что вращение от OXi к Ox+1 по кратчайшему углу проиходит в ту же сторону, что и вращение от оси Ox к Oy.

Какую-то фигню я вчера написал. Вроде трезвым был...

Величина угла вычисляется как арккосинус поэтому всегда меньше развернутого. Таким образом его знак просто совпадает со знаком площади.

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

Вот что у меня на данный момент получилось:
http://msfu.net.ru/download/uploads/uploads/lab1.rar (172 kb)
(но работает только с выпуклыми контурами)
Координаты вершин хранятся в файле plg.txt в формате "N X1 Y1 ... Xn Yn", где N - количество вершин, XnYn - координаты n-ой вершины.

function GetAngle(p1,o,p2:TPoint):real; var x1,x2,y1,y2:integer; begin x1:=p1.X-o.X; y1:=p1.Y-o.Y; x2:=p2.X-o.X; y2:=p2.Y-o.Y; Result:=ArcCos((x1*x2+y1*y2)/(sqrt(x1*x1+y1*y1)*sqrt(x2*x2+y2*y2))); end; function PointInPlg:boolean; var r:real; i:integer; begin for i:=0 to Length(plg)-1 do begin if i<>Length(plg)-1 then r:=r+GetAngle(plg[i],SP,plg[i+1]) else r:=r+GetAngle(plg[i],SP,plg[0]); end; if Round(180*r/pi) mod 360=0 then result:=true else result:=false; end;

А знак присвоить? Вставить в конце функции GetAngle:
if x1*y2 - x2*y1 < 0.0 then Result := - Result;

Кроме того я не понял логику последних операторов. По идее
Round(180*r/pi) mod 360=0
будет выполняться всегда, потому что, если не учитывать погрешность, сумма будет либо 0 - (вне многоугольника) либо +/-360 градусов (внутри и многоугольник охватывает точку один раз) либо 720 (два раза) и т. д. Лучше проверить, будет ли сумма близка к нулю (по модулю меньше пи).

Кроме, того неэкономно вычислять два раза sqrt. Можно занести все под один радикал.

полностью рабочий код, работает в "мягком" real-time - обработчик WM_MOUSEMOVE....
реализация алгоритма "нечетных пересечений".....

inline TPoint __fastcall operator -(const TPoint &a, const TPoint &b) { TPoint result; result.x = a.x - b.x; result.y = a.y - b.y; return result; } inline int __fastcall operator &(const TPoint &a, const TPoint &b) { int result = (a.x * b.y) - (a.y * b.x); return result; } ///////// enum PtClass { pcNone = 0, pcLeft, pcRight, pcAt }; inline PtClass __fastcall ClassifyPtLine(const TPoint &pt, const TPoint &pt1, const TPoint &pt2) { PtClass result = pcNone; if(pt1.y != pt2.y){ // exclude horizontal const TPoint &p1 = pt1.y < pt2.y? pt1: pt2; // top point const TPoint &p2 = pt1.y < pt2.y? pt2: pt1; // bottom point if(pt.y >= p1.y && pt.y < p2.y){ // pt.y in [p1.y, p2.y) TPoint v = p1 - p2; TPoint w = pt - p2; int crossp = v & w; if(crossp > 0) result = pcLeft; else if(crossp < 0) result = pcRight; else result = pcAt; } } return result; } bool __fastcall PointInPoly(const TPoint &vis_pos, const vector<TPoint> &poly) { bool result = false; if(poly.size() > 1){ int edge_count = 0; PtClass pt_class = pcNone; const TPoint * pt1 = poly.begin(); const TPoint * end_pt = poly.end(); for(const TPoint * pt = pt1 + 1; !result && pt < end_pt; pt++){ pt_class = ClassifyPtLine(vis_pos, *pt1, *pt); if(pt_class == pcLeft) edge_count++; result = (pt_class == pcAt); pt1 = pt; } pt_class = ClassifyPtLine(vis_pos, poly.back(), poly.front()); if(pt_class == pcLeft) edge_count++; result = (pt_class == pcAt); if(!result) result = (edge_count & 1) != 0; } return result; }

ррррр........ куда делось моё форматирование?...... :(

Определение положения точки относительно полигона Найти похожие ветки