Точка в алгоритме проверки попадания полигона

Question

Мне нужно проверить, попадает ли точка в многоугольник с отверстиями и островками. Я хотел бы понять, как я должен это сделать. Это не задокументировано, и я не могу найти никаких объяснений или примеров.

Что я делаю, так это считаю +1 для каждого внешнего удара многоугольника и -1 за каждый внутренний удар полигона. Итоговая сумма:

• > 0: хит;
• <= 0: пропустить (снаружи или в яме).

HitData класс разделяет пути на основе числа обмоток, чтобы избежать ненужного пересчета orientation, С Clipper.PointInPolygon() Применительно к каждому пути сумма легко вычисляется.

Но есть два основных недостатка:

1. Я должен подать заявку Clipper.PointInPolygon() на КАЖДОЙ путь;
2. Я не могу использовать иерархию PolyTree,

Может ли кто-то, кто имеет практический опыт работы с Clipper ( Angus Johnson?), Разобраться в этой путанице?

Опять же, мой вопрос: как я должен это реализовать? Я заново изобретаю колесо, в то время как в Библиотеке Clipper есть реальное решение?

Примечание: PolyTree все еще требует проверить КАЖДЫЙ путь, чтобы определить, какой PolyNode дело в том. нет Clipper.PointInPolyTree() метод и, таким образом, AFAIK PolyTree не помогает

Структура, разделяющая внешние и внутренние многоугольники:

public class HitData
{
    public List<List<IntPoint>> Outer, Inner;

    public HitData(List<List<IntPoint>> paths)
    {
        Outer = new List<List<IntPoint>>();
        Inner = new List<List<IntPoint>>();

        foreach (List<IntPoint> path in paths)
        {
            if (Clipper.Orientation(path))
            {
                Outer.Add(path);
            } else {
                Inner.Add(path);
            }
        }
    }
}

И это алгоритм, который проверяет точку:

public static bool IsHit(HitData data, IntPoint point)
{
    int hits;

    hits = 0;

    foreach (List<IntPoint> path in data.Outer)
    {
        if (Clipper.PointInPolygon(point, path) != 0)
        {
            hits++;
        }
    }

    foreach (List<IntPoint> path in data.Inner)
    {
        if (Clipper.PointInPolygon(point, path) != 0)
        {
            hits--;
        }
    }

    return hits > 0;
}

Answer 1

Может ли кто-нибудь, имеющий практический опыт работы с Clipper (@angus-johnson?), Прояснить эту путаницу?

Мне не ясно, в чем ваше замешательство. Как вы правильно заметили, библиотека Clipper не предоставляет функции для определения, находится ли точка внутри нескольких путей.

Изменить (13 сентября 2019 г.):

Хорошо, теперь я создал PointInPathsфункция (в Delphi Pascal), которая определяет, находится ли точка внутри нескольких путей. Обратите внимание, что эта функция учитывает различные правила заливки многоугольника.

функция CrossProduct(const pt1, pt2, pt3: TPointD): double;
вар
  x1,x2,y1,y2: двойной;
начать
  x1: = pt2.X - pt1.X;
  y1: = pt2.Y - pt1.Y;
  x2: = pt3.X - pt2.X;
  y2: = pt3.Y - pt2.Y;
  результат:= (x1 * y2 - y1 * x2);
конец;


функция PointInPathsWindingCount(const pt: TPointD;
  константные пути: TArrayOfArrayOfPointD): целое число;
вар
  i,j, len: целое число;
  p: TArrayOfPointD;
  prevPt: TPointD;
  isAbove: Boolean;
  crossProd: двойной;
начать
  //nb: возвращает MaxInt ((2^32)-1), когда pt находится в строке
  Результат:= 0;
  для i: = от 0 до High(пути) делаем
  начать
    j:= 0;
    p: = пути [i];
    len: = Длина (p);
    если len < 3, то продолжить;
    prevPt: = p[len-1];
    while (j 
    если j = len, тогда продолжить;
    isAbove: = (prevPt.Y 
    пока (j 
    начать
      если выше, то
      начать
        while (j 
        если j = len, то перерыв
        иначе, если j > 0, то prevPt: = p[j -1];
        crossProd: = CrossProduct(prevPt, p[j], pt);
        если crossProd = 0, то
        начать
          результат:= MaxInt;
          Выход;
        конец
        иначе, если crossProd < 0, то dec(Результат);
      конец еще
      начать
        while (j  pt.Y) do inc(j);
        если j = len, то перерыв
        иначе, если j > 0, то prevPt: = p[j -1];
        crossProd: = CrossProduct(prevPt, p[j], pt);
        если crossProd = 0, то
        начать
          результат:= MaxInt;
          Выход;
        конец
        иначе, если crossProd > 0, то inc(Результат);
      конец;
      inc(j);
      isAbove: = не isAbove;
    конец;
  конец;
конец;

функция PointInPaths(const pt: TPointD;
  константные пути: TArrayOfArrayOfPointD; fillRule: TFillRule): Boolean;
вар
  туалет: целое число;
начать
  wc: = PointInPathsWindingCount(точка, пути);
  case fill Правило
    frEvenOdd: результат: = Нечетное (wc);
    frNonZero: результат:= (wc <> 0);
  конец;
конец;

Что касается использования структуры PolyTree:

верхние узлы в PolyTree - это внешние узлы, которые вместе содержат каждый (вложенный) многоугольник. Так что вам нужно только выполнитьPointInPolygonна этих верхних узлах, пока не будет обнаружен положительный результат. Затем повторитеPointInPolygonна этих узлах вложенные пути (если есть) ищут там положительное совпадение. Очевидно, когда внешний узел выходит из строяPointInPolygontest, то его вложенные узлы (полигоны) также не пройдут. Внешние узлы увеличивают количество намоток, а внутренние отверстия уменьшают количество намоток.