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

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

Попадает ли точка в замкнутый многоугольник


Страницы:   1 2 3 4

kudatsky ©   (2010-04-22 11:54:00) 

На экране находится не выпуклый многоугольник, заданный координатами X1,Y1,X2,Y2,X3,Y3 и т.д. Задана точка X,Y. Как определить, находится ли точка внутри фигуры ? Нет ли для этого системной функции ?

Sha   (2010-04-23 01:09:00) [41]

Если требуется совместимость с алгоритмом [14]
(границы с меньшими абсциссами/ординатами включаются, с большими - исключаются),
то можно использовать такую модификацию алгоритма:

function ShaIsPointInPolygon3(Pt: PPoint; Poly: PPoint; Count: integer): boolean;
type
 TPointArray  = array[0..$6ffffff] of TPoint;
 PPointArray = ^TPointArray;
var
 Last: PPoint;
 Cross, dxLine, dxPoint, xOld, yOld: integer;
begin;
 Last:=@PPointArray(Poly)[Count-1];
 with Last^ do begin;
   xOld:=x;
   yOld:=y;
   end;
 Cross:=0;
 repeat;
   dxPoint:=Poly.x - Pt.x;
   xOld:=xOld - Pt.x;
   if dxPoint xor xOld<0 then begin;
     dxLine:=xOld - dxPoint;
     yOld:=(yOld - Poly.y) * dxPoint
         + (Pt.y - Poly.y) * dxLine;
     if yOld<>0 then Cross:=Cross xor yOld xor dxLine;
     end;
   xOld:=Poly.x;
   yOld:=Poly.y;
   inc(Poly);
   until dword(Poly)>dword(Last);
 Result:=boolean(Cross shr 31);
 end;

Sha   (2010-04-23 00:30:00) [42]

Кстати, можно в несколько раз повысить скорость вычислений алгоритма [14].
если изменить объявление параметров функции следующим образом:

function ShaIsPointInPolygon(X, Y: integer; varTepmPolyLine: TDAPoint): boolean;


Можно ускорить функцию еще примерно в полтора раза,
но уже ценой ухудшения читаемости кода:

function ShaIsPointInPolygon2(Pt: PPoint; Poly: PPoint; Count: integer): boolean;
type
 TPointArray  = array[0..$6ffffff] of TPoint;
 PPointArray = ^TPointArray;
var
 Last: PPoint;
 Cross, dxLine, dxPoint, xOld, yOld: integer;
 Internal: boolean;
begin;
 Last:=@PPointArray(Poly)[Count-1];
 with Last^ do begin;
   xOld:=x;
   yOld:=y;
   end;
 Cross:=0;
 Internal:=true;
 repeat;
   dxPoint:=Poly.x - Pt.x;
   xOld:=xOld - Pt.x;
   if dxPoint xor xOld<0 then begin;
     dxLine:=dxPoint - xOld;
     yOld:=(yOld - Poly.y) * dxPoint
         + (Poly.y - Pt.y) * dxLine;
     if yOld=0
     then Internal:=not Internal
     else Cross:=Cross xor yOld xor dxLine;
     end;
   xOld:=Poly.x;
   yOld:=Poly.y;
   inc(Poly);
   until dword(Poly)>dword(Last);
 Result:=boolean(Cross shr 31) and Internal;
 end;


В последнем варианте функции передаются три параметра:
указатель на проверяемую точку,
указатель на первую вершину многоугольника,
количество вершин многоугольника.

Для точек, лежащих на границе многоугольника, поведение этой функции
единообразно: граничные точки не считаются внутренними.
Это отличается от предыдущей функции, которая может возвращать произвольный результат.

Дмитрий Белькевич   (2010-04-22 19:31:00) [43]


> Очень похоже на костыль.


Возможно. Попробую [14].

Sha   (2010-04-22 17:05:00) [44]

Sha ©   (22.04.10 17:00) [20]

Хотя нет, не подумал, это не поможет.

Sha   (2010-04-22 17:00:00) [45]

Еще у этого алгоритма есть одно слабое место:
он дает разные ответы, в случаях когда точка лежит на левом или правом отрезке.
Имеет смысл включить границы, заменив неравенство на нестрогое в последнем if

Sha   (2010-04-22 16:59:00) [46]

> Дмитрий Белькевич   (22.04.10 16:45) [16]
> За [14] спасибо. Проверю.

Надо иметь в виду, что в нем массив не замыкается.

Sha   (2010-04-22 16:57:00) [47]

> Омлет ©   (22.04.10 16:41) [15]
> Если замкнуть точки (т.е. чтобы последняя была равна первой), то работает.

Очень похоже на костыль.

Дмитрий Белькевич   (2010-04-22 16:49:00) [48]


> Если замкнуть точки (т.е. чтобы последняя была равна первой),
>  то работает.


+1. У меня замыкается.

Дмитрий Белькевич   (2010-04-22 16:45:00) [49]


> [8] относится к [2]


Алгоритм рабочий. N - количетво точек минус одну, да. Что бы лишних телодвижений не делать в цикле.

За [14] спасибо. Проверю.

Омлет   (2010-04-22 16:41:00) [50]

> Sha ©   (22.04.10 15:59) [14]
> Алгоритм [2] не работает, если точка лежит левее последнего отрезка

Если замкнуть точки (т.е. чтобы последняя была равна первой), то работает.

Sha   (2010-04-22 15:59:00) [51]

Алгоритм [2] не работает, если точка лежит левее последнего отрезка  
и ее ордината лежит между ординатами последнего отрезка.

Например, для квадрата
 a[0].y:=0; a[0].x:=2;
 a[1].y:=0; a[1].x:=0;
 a[2].y:=2; a[2].x:=0;
 a[3].y:=2; a[3].x:=2;


Подправить можно так:

function ShaIsPointInPolygon(X, Y: integer; TepmPolyLine: TDAPoint): boolean;
var
 i1, i2: integer;
begin
 Result:=false;
 i2:=0;
 i1:=Length(TepmPolyLine)-1;
 while i1>=0 do begin;
   if not ((TepmPolyLine[i1].x < x) xor (x <= TepmPolyLine[i2].x))
   then if y - TepmPolyLine[i1].y
        < (x - TepmPolyLine[i1].x)
        * (TepmPolyLine[i2].y - TepmPolyLine[i1].y)
        / (TepmPolyLine[i2].x - TepmPolyLine[i1].x)
       then Result:=not Result;
   i2:=i1;
   i1:=i1-1;
   end;
 end;

procedure TForm1.Button2Click(Sender: TObject);
var
 a: TDAPoint;
 x, y: integer;
begin;
 SetLength(a,4);
 a[0].y:=0; a[0].x:=2;
 a[1].y:=0; a[1].x:=0;
 a[2].y:=2; a[2].x:=0;
 a[3].y:=2; a[3].x:=2;  
 x:=1; y:=1;
 Memo1.Lines.Add(IntToStr(Ord(IsPointInPolygon(x, y, a))));
 Memo1.Lines.Add(IntToStr(Ord(ShaIsPointInPolygon(x, y, a))));
 end;

Sha   (2010-04-22 14:53:00) [52]

> Ins ©   (22.04.10 14:39) [11]

Да, точно. По инерции считал, что n - количество точек.

Ins   (2010-04-22 14:42:00) [53]


> Зато скорость выполнения

Времявыполнения, оговорился...

Ins   (2010-04-22 14:39:00) [54]


> А ничего, что за границу массива выходит?


Не выходит:

> i := i + 1;  
>until i >= n;



> Омлет ©   (22.04.10 14:09) [7]
> Если использовать PtInRegion, то можно не замыкать точки.
>


Зато скорость выполнения в сотни раз может быть больше. Регион - это множество непересекающихся прямоугольников. Если их сотни, то и сотни раз проверить на вхождение (в каждый) нужно.

kudatsky   (2010-04-22 14:15:00) [55]

Всё прекрасно работает.
Всем спасибо ;-)))

Sha   (2010-04-22 14:11:00) [56]

[8] относится к [2]

Sha   (2010-04-22 14:10:00) [57]

А ничего, что за границу массива выходит?

Омлет   (2010-04-22 14:09:00) [58]

Если использовать PtInRegion, то можно не замыкать точки.

function IsPointInPolygon(X, Y: integer; Points: TDAPoint): boolean;
var
  Rgn : HRGN;
begin
  Result := False;
  Rgn := CreatePolygonRgn(Pointer(@Points[0])^, Length(Points), WINDING);
  if Rgn <> 0 then
  begin
    Result := PtInRegion(Rgn, X, Y);
    DeleteObject(Rgn);
  end;
end;

Омлет   (2010-04-22 14:02:00) [59]

Пардон. Работает верно, но если последняя точка в массиве совпадает с первой.

Омлет   (2010-04-22 13:53:00) [60]

> Дмитрий Белькевич   (22.04.10 12:14) [2]

Работает неверно.

Страницы:   1 2 3 4

Наверх

Титульная страница Поиск, карта сайта Написать письмо