Нахождение прямоугольника с выравниванием по оси внутри многоугольника

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

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

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


algorithm geometry polygon rectangles
person Joel in Gö    schedule 04.03.2009    source источник
comment
Считаете ли вы точку в полигональном тесте тяжелой? В большинстве случаев это просто тест больше и / или меньше всех ths точек, из которых состоит многоугольник, и только в некоторых случаях тест пересечения линий? Или...?   -  person Dan Byström    schedule 04.03.2009
comment
Не уверен, что вы имеете в виду ... Я использую тест на пересечение четно-нечетного пересечения для полупрямой (конечно, после проверки ограничивающего прямоугольника). Это заканчивается тестированием множества сторон, и если у многоугольника много сторон, это довольно медленно.   -  person Joel in Gö    schedule 04.03.2009
comment
Если вы свяжетесь с некоторыми наборами данных, это звучит как что-то, что может быть интересно попробовать.   -  person Jeremy French    schedule 04.03.2009
comment
«Не бойтесь, все, что у меня есть, - это база данных.   -  person Joel in Gö    schedule 04.03.2009
comment
Мне любопытно, для чего это? Вогнутый многоугольник вполне может иметь два или более таких прямоугольника одинаковой площади.   -  person TrayMan    schedule 10.03.2009
comment
Для ускорения проверки нажатия "точка в многоугольнике". Если у многоугольника есть охватывающий прямоугольник и связанный с ним закрытый прямоугольник, во многих случаях мы можем очень эффективно выполнить проверку на попадание, проведя первую проверку прямого попадания в прямоугольники. Дорогостоящее точное тестирование необходимо проводить только для точек, лежащих между двумя прямоугольниками.   -  person Joel in Gö    schedule 10.03.2009
comment
Мне он также нужен для отдельной задачи: найти место для надписи на стальной пластине с номером детали, где деталь может быть любой формы, иметь просверленные отверстия и т. Д.   -  person Joel in Gö    schedule 10.03.2009

Ответы (4)


arrow_upward
7
arrow_downward

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

person cobbal    schedule 04.03.2009
comment
Вау, хорошая ссылка, TNX - person anhoppe; 17.02.2017

arrow_upward
3
arrow_downward

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

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

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

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

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

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

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

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

  1. Найдите лист, на который попадает острие.
  2. Если на листе есть край, сравните с ним точку. Если нет, должно быть очевидно, находится ли точка внутри или снаружи (сохраните эту информацию в таких листьях при построении дерева).
person TrayMan    schedule 10.03.2009
comment
Пытался этого избежать ... знаете ли вы хорошее введение? Спасибо :) - person Joel in Gö; 10.03.2009
comment
Я не могу ничего дать, но вы можете легко найти в Google много всего, и то, что я только что написал, должно дать общее представление. - person TrayMan; 10.03.2009

arrow_upward
2
arrow_downward

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

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

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

person Joel in Gö    schedule 04.03.2009
comment
Прямо с макушки нарисуйте горизонтальные и вертикальные линии через каждую вершину вместо единой сетки. - person Agnel Kurian; 04.03.2009
comment
... при условии, что у многоугольника не так много маленьких сторон, аппроксимирующих кривые. - person Joel in Gö; 04.03.2009
comment
Я использовал вариант этого с хорошим эффектом. По сути, я разрезал многоугольник на 16 контрольных точек (4 в ширину и 4 в высоту в зависимости от размеров ограничивающего прямоугольника). Имея очень ограниченный список образцов, мне нужно было только расширить свой прямоугольник, проверив, создает ли новая точка прямоугольник полностью внутри геометрии. Это очень хорошо сработало для моих целей. - person Berin Loritsch; 22.02.2016

arrow_upward
0
arrow_downward

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

person Josh C.    schedule 30.04.2012