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

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

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

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

AlexNx © (2004-04-17 17:15:00)
Народ, где можно подсмотреть алгоритм попадания точки в произвольный многоугольник

AlexXn (2004-04-22 12:33:00) [1]
Всем спасибо!

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

MrAngel (2004-04-18 04:37:00) [2]
Посмотри вот это...

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.

Morfey (2004-04-17 23:54:00) [3]
вроде так
Rgn := CreatePolygonRgn(Points, PointsCount,...); Result := PtInRgn(Point,Rgn); CloseHandle(Rgn);

Viktor (2004-04-17 22:09:00) [4]
Ups. Я должен забрать свои слова обратно. Был не прав. Извините.

Viktor (2004-04-17 21:50:00) [5]
> aldor
Этот метод при помощи луча с первой попытки может не дать правильный результат. Ну сами посудите

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

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

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

ViK (2004-04-17 21:42:00) [6]
Где-то у меня был пример столкновения всяких фигур, если найду могу выслать на мыло

Aldor (2004-04-17 21:32:00) [7]
Извиняюсь, выражения для вычисления знака z-координаты векторного произведения читать как sign(x1 * y2- x2 * y1);

aldor (2004-04-17 21:18:00) [8]
Здесь два существенно разных случая: многоугольник выпуклый, и невыпуклый.

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

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

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

Viktor (2004-04-17 18:10:00) [9]
Если хочешь, могу блок-схему прислать. Дай e-mail

Viktor (2004-04-17 18:05:00) [10]
может и есть по-проще. Радианный, например. Но он не такой резвый, в смысле быстрый. Есть ещё габаритный тест, но он не даст 100% результат. А других я не знаю :)

AlexXn (2004-04-17 17:58:00) [11]
>TUser
Есть координаты точки и координаты вершин многоугольника и нужно определить, попадает точка в многоугольник или нет
>Viktor
Слишком сложно. По-моему есть проще алгоритм.

Viktor (2004-04-17 17:56:00) [12]
Кстати этот самый октантный тест подходит и для выпуклых полигонов.

AlexXn (2004-04-17 17:55:00) [13]
> Модератор
За что перенесли-то??? Не пишу я игр!!!

TUser (2004-04-17 17:55:00) [14]
Точнее Игры?

TUser (2004-04-17 17:54:00) [15]
А почему Сети?

Viktor (2004-04-17 17:47:00) [16]
Триангулируй свой полигон (разбей его на треугольники), а потом проверяй принадлежность точки каждому треугольнику. Конечно это пройдёт если полигон заведомо выпуклый, его легко триангулировать. К невыпуклому полигону лучше применить октантный тест.

TUser (2004-04-17 17:40:00) [17]
А что имелось в виду под сабжем-то. Я честно говоря ничего не понял, коме того, что надо точкой попасть в многоугольник. А что сие означение - лишь тебе одному известно.

AlexNx (2004-04-17 17:32:00) [18]
Не смешно

TUser (2004-04-17 17:22:00) [19]
var точка:ТТочка
Мн:ЕМногоугольник
begin
точка:=ТТочка.Create;
Мн:=ТМногоугольник.Create;
точка.попасть(Мн)
end;
:)

Наверх

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