Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Игры";
Текущий архив: 2004.08.01;
Скачать: [xml.tar.bz2];

Вниз

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

 
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);


 
ViK ©   (2004-04-17 21:42) [14]

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


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

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

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

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

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


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

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


 
Morfey ©   (2004-04-17 23:54) [17]

вроде так
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. Извеняюсь, раньше не мог ответить



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

Форум: "Игры";
Текущий архив: 2004.08.01;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.49 MB
Время: 0.05 c
1-1089893971
Владимир
2004-07-15 16:19
2004.08.01
Ограничение объёма при копировании из TMemo в Clipboard


14-1089884465
slaga
2004-07-15 13:41
2004.08.01
Общие "resource"


3-1089200786
stud
2004-07-07 15:46
2004.08.01
программное добавление юзеров и прав


1-1090424383
Василий
2004-07-21 19:39
2004.08.01
Проблемы с регистрацией типов файлов


1-1090406223
Dm_S
2004-07-21 14:37
2004.08.01
xl_1:=CreateOLEObject( Excel.Application в консольном приложении





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский