Помогите реализовать алгоритм

← →
Xerx © (2005-02-26 13:40) [0]

Кто знает реализацию алгоритма проверки пренадлежности точки полигону при помощи СУММИРОВАНИЯ УГЛОВ? Именно этот алгоритм, никаких подсчетов пересечений линий со сторонами полигона и т.д.

← →
Fedia © (2005-02-26 14:14) [1]

Разве не алгоритм проецирования отрезков на ось в этом случае является самым быстрым? Вся суть его реализации сводится к операциям сравнения. Если нужен, то завтра попробую пример скинуть.

← →
Xerx © (2005-02-26 22:43) [2]

Fedia > Не знаю о таком алгоритме. Мненужен не САМЫЙ, САМЫЙ, САМЫЙ, а именно этот!!! Но если можешь - скинь, вдруг нечто похожее.

← →
XProger © (2005-02-27 01:39) [3]

//Положение точки p относительно прямой (p1, p2) function Side(p, p1, p2: TPoint): boolean; var a, b: TPoint; begin a.X := p2.X - p1.X; a.Y := p2.Y - p1.Y; b.X := p.X - p1.X; b.Y := p.Y - p1.Y; Result := (a.X * b.Y - a.Y * b.X) >= 0; end; cur := Point(X, Y); if Side(cur, p[1], p[2]) and //обход по часовой стрелке Side(cur, p[2], p[3]) and Side(cur, p[3], p[1]) then Caption := "В яблочко!!!" //соответственно =) else Caption := "Неа!"; //Не попал =)

Что-то в этому духе... без проблем можно под 3d переписать.

← →
XProger © (2005-02-27 01:40) [4]

if Side(cur, p[1], p[2]) = //обход по/против часовой стрелки Side(cur, p[2], p[3]) = Side(cur, p[3], p[1]) then
Так правильнее будет ;)

← →
Fedia © (2005-02-28 00:17) [5]

>Xerx © (26.02.05 22:43) [2]
>а именно этот!!!
>вдруг нечто похожее.
Нет, совершенно не похожее. Об углах там речи нет вообще.

← →
марсианин © (2005-02-28 00:45) [6]

[4] XProger © (27.02.05 01:40)
ну как? работает? последняя версия вроде должна.. в чем проблема-то?

только
> без проблем можно под 3d переписать.
это врядли..

← →
Xerx © (2005-03-01 11:32) [7]

Отвечаю сам(нашел), может кому интересно.
Из точки вычисляются вектора ко всем вершинам полигона(произвольного). Суммируются центральные углы. Если сума равна 360гр, то точка внутри, если нет, то точка вне полигона.

← →
MrAngel (2005-03-01 13:05) [8]

Не знаю - по методам углов это или нет - но работает как надо.

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.

марсианин, всё работает. А чтобы проверить принадлежность в 3д достаточно написать уравнение плоскости для этого треугольника и проверить принадлежит ли точка этой плоскости. И всего-то, а этот 3д треугольник можно спроецировать на одну из координатных плоскостей (переход к 2д координатам).

Xerx, ты там наверное ещё и арксинусы/арккосинусы считаешь? ;)

[9] XProger ©
черт я тебя с Xerx перепутал:) думал чей-то он сам на свой ворпос ответил :)

я думал имеется ввиду принадлежит ли точка 3Д многограннику.. там по другому

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

> марсианин
Я сам и ответил (ранише).
Метод подсчета кол-ва точек пересечения хорош, да мне нужно было реализовать определенный метод забив на скорость, ets.
> XProger
А арккосинусы можно и не считать. Можно быстрее..

Помогите реализовать алгоритм Найти похожие ветки