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

Question

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

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

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

Answer 1

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

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

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

Answer 2

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
Имеет алгоритм выпуклыми, ссылки могут быть стоит посмотреть.
не уверен, что он может быть расширен до невыпуклых.

Answer 3

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

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

Edit: Я ellaborate на кД дерева (от скуки, даже если это может быть полезным для тех, кто):

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

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

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

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

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

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

Answer 4

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