Найти координаты точки внутри полигона.

← →
MrAngel (2003-12-21 17:10) [0]

Ребята где то на форуме видел этот вопрос но так его и не нашёл.

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

Задана координата мыши на экране. Мне надо узнать попадает ли мышь в этот полигон и если попадает, то по каким координатам полигона. Ясно дело координаты будут расчитываться по 2D BoundingBox"у этого полигона.

Может кто знает какой нибудь API или OGL функцию или комманду пожалуйсто напишите.

← →
MBo © (2003-12-21 17:20) [1]

либо CreatePolygonRgn+PtInRegion, либо математика - например, луч, проведенный из точки в любую сторону, пересекает нечетное количество сторон, если точка внутри.

← →
MrAngel (2003-12-22 17:41) [2]

CreatePolygonRgn+PtInRegion - не подходят так как это для работы с регионами виндовс окон. А мне именно нужно для полигонов. Может есть какие нибудь ресурсы в сети описывающие алгоритмы по этому поводу ?

← →
MBo © (2003-12-22 17:58) [3]

:)
Кто мешает создать регион (который никак не связан с окнами) по точкам полигона - но это для того случая, если лень самому считать.

А алгоритм самостоятельного расчета я написал

← →
MrAngel (2003-12-24 20:14) [4]

Можно и так. Но всётаки хотелось бы это делать через алгоритмы а не регионные маски.

← →
Stalker_23b (2003-12-25 09:34) [5]

А как проверять пересечения луча? По уравнению прямой, ручками, или есть более быстрый метод?

← →
MrAngel (2003-12-25 15:42) [6]

Пересечение луча с чем ? Если с плоскостью то надо использовать уравнение плоскости. Если с линией... то здесь я пока не знаю :-)

← →
hexone © (2003-12-25 16:39) [7]

> Если с линией... то
с уравнением прямой

← →
hexone © (2003-12-25 16:47) [8]

http://www.sources.ru/NonCGI/Forum2/HTML/000871.html

← →
Rem © (2003-12-25 17:28) [9]

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

- определяемая точка имеет координаты X, Y;

Проводим из определяемой точки горизонтальную линию. Координаты линии (-бесконечность, Y):(+бесконечность, Y)

Определяем пересечение этой линии с одной из сторон многоугольника (отрезок)
- координаты начальной точки отрезка: X1, Y1;
- координаты конечной точки отрезка: X2, Y2;

Признак пересечения:

Cross := ((Y - Y1)*(Y - Y2) < 0);

← →
olden69 (2003-12-25 17:36) [10]

если из точки провести лучи ко всем вержинам многоугольника, то сумма углов (с учетом направления обхода "+" или "-") между соседними лучами = 360 для точки внутри многоугольника и = "чему угодно но не 360" если точка не внутри. Полные 3D координаты по всего одной проекции фиг найдешь

← →
olden69 (2003-12-25 17:40) [11]

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

← →
MrAngel (2003-12-25 21:32) [12]

> если из точки провести лучи ко всем вержинам многоугольника,
> то сумма углов (с учетом направления обхода "+" или "-")
> между соседними лучами = 360 для точки внутри многоугольника
> и = "чему угодно но не 360" если точка не внутри. Полные
> 3D координаты по всего одной проекции фиг найдешь

Всё верно... такой метод я тоже нашёл в сети. Однако он для выпуклого многоугольника.

Есть ещё кое-что.
Для обоих случаев (для выпуклого и вогнутого) нашел такой метод, кстати достаточно логичный. Из точки, которая нам задана, мы проводим луч. Если есть пересечения луча с рёбрами многоугольника то считаем их количество.
И наконец сам ответ: если количество пересечений - четное число, то точка за пределами многоугольника, иначе... внутри него.

Всё просто. Теперь ищу как определить факт пересечения :-)

PS/Ребята, я конечно извеняюсь за своё не знание, но я учусь ;-)

← →
romeo © (2003-12-25 22:54) [13]

// предполагается, что последняя точка полигона совпадает с первой function PointInside(Pt: TPoint; PG: array of TPoint): Boolean; var Loop: Integer; begin Result := False; for Loop := 0 to Length(PG) - 2 do begin if (Pt.y > PG[Loop].y) <> (Pt.y <= PG[Loop + 1].y) then Continue; if (Pt.x - PG[Loop].x) < (Pt.y - PG[Loop].y)*(PG[Loop + 1].x - PG[Loop].x)/(PG[Loop + 1].y - PG[Loop].y) then Result := not Result; end; end;

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

← →
Chapy (2003-12-26 01:25) [14]

Дурацкий метод, но действует:
Canvas.Polygon(...) закрашивает замкнутую область текущей Brush.

var ControlColor : TColor; procedure DrawPolygon; var tmpColor : TColor; begin ..... tmpColor:=Canvas.Brush.Color; ControlColor:=tmpColor-1; Canvas.Brush.Color:=ControlColor; Canvas.Polygon(....); canvas.Brush.Color:=tmpColor; ... end; function MouseInPolygon(x,y:integer):boolean; begin result:=canvas.Pixels[x,y]=ControlColor; end;

← →
olden69 (2003-12-26 11:46) [15]

2 MrAngel

> Всё верно... такой метод я тоже нашёл в сети.
> Однако он для выпуклого многоугольника

Вот тут Вы, батенька, ошибаетесь.
Этот метод работает для ЛЮБОГО многоугольника.
Поскольку для вогнутого некоторые углы между соседними лучами будут со знаком "-", но они ПОЛНОСТЬЮ компенсируются положительными углами.
Не верите - проверьте. Возьмите бумажку, нарисуйте какой-нибудь замысловатый многоугольник (например в фоме сосиски или звезды), поставьте внутрь точку, проведите лучи.
А теперь внизу сделайте шкалу и откладывайте по ней величины углов (с учетом знака).
Уверяю - работает ИДЕАЛЬНО.

← →
sdn (2003-12-26 12:04) [16]

Добренького всем... :-)

Эта задача решается достаточно просто, если на полигон посмотреть как на граф. Решений графов в инете много и они достаточно простые... посмотри на algolist.manual.ru ищи "граф".

← →
MrAngel (2003-12-26 16:36) [17]

To sdn (26.12.03 12:04) [16] - я на сайте поискал там мне выдало только прохождение пути графа.

2 olden69 (26.12.03 11:46) [15] - Возможно. Сам я этот метод не проверял.

romeo © (25.12.03 22:54) [13]
Chapy (26.12.03 01:25) [14]

Слепил из ваших кодов одно и вот что получилось:

unit Unit1; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs; type TForm1 = class(TForm) procedure FormCreate(Sender: TObject); procedure FormPaint(Sender: TObject); procedure FormMouseMove(Sender: TObject; Shift: TShiftState; X, Y: Integer); private PG: array of TPoint; public { Public declarations } end; var Form1: TForm1; implementation {$R *.DFM} procedure TForm1.FormCreate(Sender: TObject); begin SetLength(PG,5); PG[0].X := 50; PG[0].Y := 70; PG[1].X := 60; PG[1].Y := 160; PG[2].X := 160; PG[2].Y := 170; PG[3].X := 150; PG[3].Y := 110; PG[4].X := 170; PG[4].Y := 40; end; procedure TForm1.FormPaint(Sender: TObject); begin Canvas.Polygon(PG); end; procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X, Y: Integer); var Loop: Integer; Result : Boolean; Pt : TPoint; begin Pt.x := X; Pt.Y := Y; Result := False; for Loop := 0 to Length(PG) - 2 do begin if (Pt.y > PG[Loop].y) <> (Pt.y <= PG[Loop + 1].y) then Continue; if (Pt.x - PG[Loop].x) < (Pt.y - PG[Loop].y)*(PG[Loop + 1].x - PG[Loop].x)/(PG[Loop + 1].y - PG[Loop].y) then Result := not Result; end; if Result then Caption := "TRUE" else Caption := "FALSE"; end; end.

Можете скопировать этот код в чистом виде в юнит вашей формы и посмотреть. Точкой являются координаты мыши на форме. Подвигайте мышью по полигону.

В общем то там всё работает, НО !!! для верхней грани полигона не верно определяет принадлежность точки.

romeo © - посмотри всё-таки по точнее пожалуйста. Уж очень мне твой код подходит. Я конечно сам попытаюсь разобраться, но тем не менее.

← →
MrAngel (2003-12-27 01:41) [18]

romeo © - Всё не надо.... я нашёл причину.. оказывается элементы массива первый и последний должны указывать на одну точку.

В коде надо сделать следующие изменения
procedure TForm1.FormCreate(Sender: TObject); begin SetLength(PG,6); PG[0].X := 50; PG[0].Y := 70; PG[1].X := 60; PG[1].Y := 160; PG[2].X := 160; PG[2].Y := 170; PG[3].X := 150; PG[3].Y := 110; PG[4].X := 170; PG[4].Y := 40; PG[5].X := 50; PG[5].Y := 70; end;

← →
MrAngel (2003-12-27 01:42) [19]

Всё всем спасибо - проблема решена с честью !!! :-)

Попробуй так, сделай Image на форме Image1.Visible = False, и в нем отрисуй точно такой полигон только с закраской, допустим синим, и проверяй какого цвета пиксел Image под мышкой, так просто работать с любым сложным объектом, или объектами.

← →
MrAngel (2003-12-27 16:20) [21]

Найти координаты точки внутри полигона. Найти похожие ветки