Алгоритм попадания точки

← →
AlexNx (2004-04-17 17:15) [0]

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

← →
TUser © (2004-04-17 17:22) [1]

var точка:ТТочка
Мн:ЕМногоугольник
begin
точка:=ТТочка.Create;
Мн:=ТМногоугольник.Create;
точка.попасть(Мн)
end;
:)

← →
AlexNx (2004-04-17 17:32) [2]

Не смешно

← →
TUser © (2004-04-17 17:40) [3]

А что имелось в виду под сабжем-то. Я честно говоря ничего не понял, коме того, что надо точкой попасть в многоугольник. А что сие означение - лишь тебе одному известно.

← →
Viktor (2004-04-17 17:47) [4]

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

← →
TUser © (2004-04-17 17:54) [5]

А почему Сети?

← →
TUser © (2004-04-17 17:55) [6]

Точнее Игры?

← →
AlexXn (2004-04-17 17:55) [7]

> Модератор
За что перенесли-то??? Не пишу я игр!!!

← →
Viktor (2004-04-17 17:56) [8]

Кстати этот самый октантный тест подходит и для выпуклых полигонов.

← →
AlexXn (2004-04-17 17:58) [9]

>TUser
Есть координаты точки и координаты вершин многоугольника и нужно определить, попадает точка в многоугольник или нет
>Viktor
Слишком сложно. По-моему есть проще алгоритм.

← →
Viktor (2004-04-17 18:05) [10]

может и есть по-проще. Радианный, например. Но он не такой резвый, в смысле быстрый. Есть ещё габаритный тест, но он не даст 100% результат. А других я не знаю :)

← →
Viktor (2004-04-17 18:10) [11]

Если хочешь, могу блок-схему прислать. Дай e-mail

← →
aldor © (2004-04-17 21:18) [12]

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

Если многоугольник выпуклый, тогда просто интерпретируйте стороны многоугольника как вектора, причем так, чтобы общее направление было против часовой стрелки. Затем для каждого вектора проверяйте, лежит ли точка "слева" от него. Если хотя бы для одного вектора это условие не выполняется, значит точка вне многоугольника.
Выяснить, лежит ли точка "слева" очень просто: постройте новый вектор, начало которого совпадает с началом веткора-грани, а конец - с данной точкой. Если знак векторного произведения положителен, значит точка находится "слева". Вычилслить знак векторного произведения (точнее его z-координаты) также очень просто: sign(x1 * y1 - x2 * y2), если координаты векторов соответственно (x1, x2) и (y1, y2).

Если же многоугольник невыпуклый, то алгоритм следующий:

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

← →
Aldor © (2004-04-17 21:32) [13]

Извиняюсь, выражения для вычисления знака z-координаты векторного произведения читать как sign(x1 * y2 - x2 * y1);

Где-то у меня был пример столкновения всяких фигур, если найду могу выслать на мыло

← →
Viktor (2004-04-17 21:50) [15]

> aldor
Этот метод при помощи луча с первой попытки может не дать правильный результат. Ну сами посудите

1. Выбирать произвольное направление из данной точки.

Вывод: нужно повторить операцию несколько раз (чем больше, тем лучше), каждый раз выбирая новый направляющий вектор. Но даже так 100% результата вы никогда не получите.

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

← →
Viktor (2004-04-17 22:09) [16]

Ups. Я должен забрать свои слова обратно. Был не прав. Извините.

вроде так
Rgn := CreatePolygonRgn(Points, PointsCount,...); Result := PtInRgn(Point,Rgn); CloseHandle(Rgn);

← →
MrAngel (2004-04-18 04:37) [18]

Посмотри вот это...

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,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}40; PG[3].Y := 110; PG[4].X := 170; PG[4].Y := 40; PG[5].X := 50; PG[5].Y := 70; end; procedure TForm1.FormPaint(Sender: TObject); begin Canvas.Polygon(PG); end; procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X, Y: Integer); var i: Integer; Result : Boolean; begin Result := False; for i := 0 to Length(PG) - 2 do begin if (Y > PG[i].Y) <> (Y <= PG[i+1].Y) then Continue; if (X - PG[i].X) < (Y - PG[i].Y)*(PG[i+1].X - PG[i].X)/(PG[i+1].Y - PG[i].Y) then Result := not Result; end; if Result then Caption := "TRUE" else Caption := "FALSE"; end; end.

← →
AlexXn (2004-04-22 12:33) [19]

Всем спасибо!

Спасибо огромное MrAngel. Извеняюсь, раньше не мог ответить

Алгоритм попадания точки Найти похожие ветки