Невыпуклый многоугольник - препроцесс для использования алгоритма выпуклой оболочки

Я использовал алгоритм выпуклого Халла, чтобы найти контур какой-то ... неправильной формы. Но этого недостаточно ...

Вполне возможно, потому что я не могу гарантировать, что форма у меня выпуклая ...

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

введите описание изображения здесь

Алгоритм выпуклой оболочки работает отлично, но он работает как пример справа, поэтому я теряю некоторую информацию о контурах.

Я хочу что-то, что работает ближе к версии слева, сохраняя внешние углы и удаляя только точки внутри ...

Есть такой алгоритм?

Или есть ли способ разбить такую ​​фигуру (многоугольник) на выпуклые формы, чтобы алгоритм выпуклой оболочки мог правильно ее обработать?

От ссылки к ссылке я пытался выяснить, как настроить какой-то алгоритм, такой как алгоритм Гертеля-Мельхорна, но я не знаю, как использовать пересекающиеся линии в этой ситуации ...

Спасибо за любое предложение.


algorithm geometry convex-hull non-convex graph-drawing
person Thalia    schedule 20.02.2013    source источник
comment
Как хранятся ваши данные? У вас есть набор пикселей (или дискретная сетка, в которой хранятся значения)? У вас есть набор координат квадратов? У вас есть информация о смежности (полуребра и т. Д.)? ...   -  person nbonneel    schedule 20.02.2013
comment
Какой формат ввода в вашей проблеме? Это набор прямоугольников 1x1?   -  person songlj    schedule 20.02.2013

Ответы (1)


arrow_upward
4
arrow_downward

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

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

edge_list = {}
for (i = all elements in mesh)
for (j = all edges in element(i))
    edge_list <- push jth edge of ith element
endfor
endfor
edge_list <- sort
edge_list <- remove_duplicates

Оставшиеся уникальные ребра образуют внешний контур вашего многоугольника. Этот простой алгоритм выполняется за O(N*log(N)) раз.

Вы можете улучшить сложность, используя подходящую хеш-таблицу для сравнения краев, уменьшив сложность до O(N).

person Darren Engwirda    schedule 20.02.2013
comment
Я попробую - это действительно заменит выпуклый корпус, верно? - person Thalia; 20.02.2013
comment
Да, в самом деле. Выпуклая оболочка вычисляться не будет. - person Darren Engwirda; 20.02.2013
comment
Я спросил, есть ли какая-либо информация о смежности, потому что, глядя на данные, это скорее похоже на суп из многоугольников: некоторые квадраты находятся рядом друг с другом, не касаясь друг друга, в то время как ожидаемый результат, похоже, предполагает, что они связаны ...! - person nbonneel; 20.02.2013
comment
да ... извините за мой набросок! (Реальность примерно такая же, я в основном использую эпсилон на всякий случай. - person Thalia; 20.02.2013