| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

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

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

Xerx ©   (2005-02-26 13:40:00) 

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

---

Xerx   (2005-03-29 13:46:00) [1]

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

---

марсианин   (2005-03-02 20:00:00) [2]

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

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

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

---

XProger   (2005-03-02 00:22:00) [3]

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

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

---

MrAngel   (2005-03-01 13:05:00) [4]

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

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.

---

Xerx   (2005-03-01 11:32:00) [5]

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

---

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

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

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

---

Fedia   (2005-02-28 00:17:00) [7]

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

---

XProger   (2005-02-27 01:40:00) [8]


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

Так правильнее будет ;)

---

XProger   (2005-02-27 01:39:00) [9]


//Положение точки 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 переписать.

---

Xerx   (2005-02-26 22:43:00) [10]

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

---

Fedia   (2005-02-26 14:14:00) [11]

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

---

Наверх