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

Delphi , Графика и Игры , Графика

Оформил: DeeCo
Автор: http://www.swissdelphicenter.ch

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;

   {Prufen ob das Polygon geschlossen ist}
   {tests if the polygon is closed}

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

   {Tests fur jedes Paar der Punkte, um zu sehen wenn die Seite zwischen 
   ihnen, die horizontale Linie schneidet, die TestPoint durchlauft}
   {tests for each couple of points to see if the side between them 
   crosses the horizontal line going through TestPoint}

   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))
       {Wenn es so ist}    {if it does}
       then
     begin
       {berechnet die x Koordinate des Schnitts}
       {computes the x coordinate of the intersection}

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

       {Zahler entsprechend verringern}
       {increments appropriate counter}
       if XIntersection < P.X then Inc(ToTheLeftofPoint);
       if XIntersection > P.X then Inc(ToTheRightofPoint);
     end;

   {Falls das Polygon offen ist, die letzte Seite testen}
   {if the polygon is open, test for the last side}

   if OpenPolygon then
   begin
     np := High(TestPolygon);  {Thanks to William Boyd - 03/06/2001}
     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; {PtInRgn}

Функция Delphi PtInRgn, которая определяет, лежит ли точка P внутри многоугольника, определенного массивом точек TestPolygon. Функция возвращает True, если точка находится внутри многоугольника, и False в противном случае.

Обзор функции:

1. Сначала она проверяет, является ли многоугольник открытым или закрытым. Если он не закрыт (то есть первая и последняя точки не равны), она устанавливает флаг OpenPolygon в True.
2. Затем она проходит по каждой паре смежных точек в многоугольнике (np варьируется от 1 до High(TestPolygon), что является числом элементов массива минус 1).
3. Для каждой пары точек она проверяет, пересекается ли сторона между ними горизонтальной линией, проходящей через точку P. Если это так, она вычисляет координату x точки пересечения с помощью простого линейного интерполирования.
4. Затем она увеличивает два счетчика: ToTheLeftofPoint и ToTheRightofPoint, в зависимости от того, находится ли точка пересечения слева или справа от точки P.
5. Если многоугольник открыт, она также проверяет последнюю сторону многоугольника (то есть соединяющую последнюю точку с первой).
6. Наконец, функция возвращает True, если оба счетчика имеют нечетные значения (значение, означающее, что точка пересекает четное количество сторон), и False в противном случае.

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

Один из потенциальных проблем этой функции заключается в том, что она предполагает, что точки в многоугольнике уникальны и не лежат на одной вертикали (то есть имеют разные координаты y). Если эти предположения не выполняются, функция может производить неправильные результаты. Кроме того, функция не обрабатывает дегенеративные случаи, такие как многоугольник с нулевым или одним сторонами.

В качестве альтернативных решений есть несколько других алгоритмов для определения, лежит ли точка внутри многоугольника, включая:

1. Алгоритм луча: этот алгоритм работает путем кастинга луча от точки до бесконечности и счета количества раз, когда он пересекает границы многоугольника.
2. Алгоритм Бентли-Оттмана: это более эффективный алгоритм, использующий подход с линией, чтобы определить, лежит ли точка внутри многоугольника.
3. Библиотека Clipper: это C++ библиотека, которая предоставляет широкий спектр алгоритмов для обрезки и столкновения форм, включая многоугольники.

Важно отметить, что функция PtInRgn, предоставленная в этом коде, имеет некоторые ограничения и может не быть подходящей для всех случаев использования. Если вам нужно более robust или эффективное решение, вы можете хотеть рассмотреть одну из этих альтернативных подходов.

Функция PtInRgn проверяет, находится ли точка P внутри многоугольника TestPolygon.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Графика ::