Поиск прямоугольника с выравниванием по оси внутри многоугольника

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

Многоугольник также может иметь отверстия, но также могут быть полезны любые указатели на алгоритмы, которые работают только для выпуклых или простых многоугольников.

В моей реализации тестирование пересечений для сторон довольно дешево, но тесты "точка в полигоне" дороги, поэтому идеально следует минимизировать.

Ответы

Ответ 2

Одним из решений является разбиение вогнутого многоугольника на выпуклые сегменты, а затем использование cobbal link.

Поскольку у вас действительно есть две разные фундаментальные проблемы, рассмотрели ли вы другие альтернативы проблеме теста попадания, например, используя дерево BSP? Вы можете ускорить это, уложив сетку поверх поли и построив дерево BSP для каждого квадрата сетки. Или kd-дерево с не более чем одним ребром в каждом листе?

Изменить: я буду работать на kd-дереве (из-за скуки, даже если это может быть полезно любому):

kd-деревья обладают следующими свойствами:

  • Они двоичные
  • Каждый нелистный node разбивает пространство вдоль плоскости, перпендикулярной оси, с одной стороны на каждого ребенка. Например. корень разбивает пространство на x < x0 и x >= x0
  • Уровни деревьев разворачиваются по разным осям, например. уровень 0 (корень) разделяет перпендикулярно X, уровень 1 → Y и т.д.

Чтобы использовать это для обнаружения многоугольника, постройте дерево следующим образом:

  • Выберите вершину для разделения. (Предпочтительно где-то близко к середине для сбалансированного дерева).
  • Разделите другие вершины на два набора, по одному для каждой стороны раскола. Вышеупомянутая вершина не входит в любой набор.
  • Поместите ребра в множества. Любое ребро, пересекающее разделительную линию, переходит в оба набора.
  • Построить рекурсивные объекты из указанных групп.

Если разделенная вершина выбрана соответствующим образом, дерево должно иметь глубину, близкую к log (N), где N - число вершин. Каждый лист node будет иметь не более одного края, проходящего через него. Чтобы выполнить обнаружение попадания:

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

Ответ 3

Просто для справки, пока все, что у меня есть, это грубая сила: сделайте сетку, а для точек на сетке, если они находятся внутри многоугольника, сделайте серию прямоугольников, разворачивая каждый угол или сторону по очереди, пока она не попадет в стороне. Затем просто выберите самый большой.

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

По понятным причинам это довольно медленно и неточно, не говоря уже о неэлегантном:)

Ответ 4

Как насчет использования обрезки ушей? В каждом треугольнике можно найти максимальный прямоугольник, выровненный по оси. Затем вы можете попытаться присоединиться к треугольникам и пересчитать свои прямоугольники.