Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2005.07.11;
Скачать: CL | DM;

Вниз

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

 
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.


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

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

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


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

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

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

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


 
Xerx ©   (2005-03-29 13:46) [11]

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



Страницы: 1 вся ветка

Текущий архив: 2005.07.11;
Скачать: CL | DM;

Наверх




Память: 0.49 MB
Время: 0.035 c
9-1111325628
Ландграф Павел
2005-03-20 16:33
2005.07.11
Предложение сделать вместе игру


4-1114082819
Style
2005-04-21 15:26
2005.07.11
Как программно создать Dial-Up соединение ?


4-1116013371
Kolan
2005-05-13 23:42
2005.07.11
Как получить Handle активного edit а (не моего).


14-1118085760
Gero
2005-06-06 23:22
2005.07.11
Ищу ветку


14-1118840546
Oyster
2005-06-15 17:02
2005.07.11
Windows XP выэтовается.