Находится ли точка внутри многоугольника?

Другое   10 Октябрь 2010  Автор статьи: admin 

Достаточно сложный алгоритм определения того, находится ли точка внутри заданного многоугольника. Все вершины многоугольника надо задать в массиве TestPolygon : array of TPoint, а отдельную точку надо задать в P : TPoint. Использовать функцию достаточно просто, поэтому я не буду останавливаться на этом подробно.

 function PtInRgn(TestPolygon : array of TPoint; const P : TPoint): boolean;
 var
   ToTheLeftofPoint, ToTheRightofPoint : byte;
   np : integer;
   OpenPolygon : boolean;
   XIntersection : real;
 begin
   ToTheLeftofPoint := 0;
   ToTheRightofPoint := 0;
   OpenPolygon := False;

   if not ((TestPolygon[0].X = TestPolygon[High(TestPolygon)].X) and
     (TestPolygon[0].Y = TestPolygon[High(TestPolygon)].Y)) then
     OpenPolygon := True;

   for np := 1 to High(TestPolygon) do
     if ((TestPolygon[np - 1].Y <= P.Y) and
       (TestPolygon[np].Y > P.Y)) or
       ((TestPolygon[np - 1].Y > P.Y) and
       (TestPolygon[np].Y <= P.Y))
       then
     begin

       XIntersection := TestPolygon[np - 1].X +
         ((TestPolygon[np].X - TestPolygon[np - 1].X) /
         (TestPolygon[np].Y - TestPolygon[np - 1].Y)) * 
(P.Y - TestPolygon[np - 1].Y);

       if XIntersection < P.X then Inc(ToTheLeftofPoint);
       if XIntersection > P.X then Inc(ToTheRightofPoint);
     end;


   if OpenPolygon then
   begin
     np := High(TestPolygon);  
     if ((TestPolygon[np].Y <= P.Y) and
       (TestPolygon[0].Y > P.Y)) or
       ((TestPolygon[np].Y > P.Y) and
       (TestPolygon[0].Y <= P.Y)) then
     begin
       XIntersection := TestPolygon[np].X +
         ((TestPolygon[0].X - TestPolygon[np].X) /
         (TestPolygon[0].Y - TestPolygon[np].Y)) * 
(P.Y - TestPolygon[np].Y);

       if XIntersection < P.X then Inc(ToTheLeftofPoint);
       if XIntersection > P.X then Inc(ToTheRightofPoint);
     end;
   end;

   if (ToTheLeftofPoint mod 2 = 1) 
and (ToTheRightofPoint mod 2 = 1) then Result := True
   else
     Result := False;
 end;
  • Андрей

    СУПЕР! РАБОТАЕТ! ВСЕ ПРОСТО! Кому нужно — пишите sland@list.ru, дам работающий пример (рисуем фигуру, ставим точку, проверяем внутри или снаружи фигуры).

Научиться программировать

  • на Delphi

  • на Java

  • на C++