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

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

0 голосов
/ 16 февраля 2019

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

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

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

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

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

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

Может кто-то, кто имеет практическийопыт работы с Клиппером ( @ angus-johnson ?) разрешает эту путаницу?

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

Примечание: PolyTree все еще требуется проверить EVERY путь, чтобы определить, в какой 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;
}

1 Ответ

0 голосов
/ 29 августа 2019

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

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

В любом случае, я вижу 2 решения (псевдокод ниже):

1: при условии, что пути не пересекаются:

bool PointInPolygonA(paths, pt) outerPaths = GetClockwisePaths(paths); innerPaths = GetAntiClockwisePaths(paths); int level = 0; foreach p in outerPaths if PointInPolygon(p) level++; foreach p in innerPaths if PointInPolygon(p) level--; return level > 0;

Функция, которая не использует PointInPolygon

bool PointInPolygonB(paths, pt){ struct edge { bottomPt, topPt, windingDir } //windingDir -> +1 or -1; //ignoring horizontal edges... List< edge > edgeList = CreateEdgeListFromPaths(paths); int winding = 0; for each e in edgeList if (pt >= e.bottomPt and pt <= e.topPt and IsClockwise(e.bottomPt, e.topPt, pt)) winding += e.WindingDir; return winding != 0;

Надеюсь, что поможет.

...