Как вычислить сглаженное смещение многоугольника, используя его Прямой скелет

Question

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

I видел несколько работ, предлагающих такой компенсаторный подход, к сожалению, ни одна из них не содержит конкретной информации о том, как этого добиться. Среди них:

• CGAL-реализация прямого скелета простого 2D-многоугольника с отверстиями

С самого определения Прямой скелет основан на непрерывном волновом фронте или распространении краев при пожаре, он особенно подходит для смещения полигонов. В частности, его можно использовать для получения так называемого «сглаженного» смещения, где углы остаются как таковые в смещенном многоугольнике

• Скелеты и смещение: топологическая точка зрения

Если каркас P уже известен, то вычисление кривой с одним смещением для любого заданного радиуса r является простым, эффективным (линейное время) и численно устойчивым. Все, что нужно сделать, это пройти через скелет определенным образом и вставить элемент за элементом кривой смещения.

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

(более высокое качество здесь )

Вопрос : Что такое правильный способ вычисления смещенного смещения многоугольника с использованием его прямого скелета?

Answer 1

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

Каждое ar c скелета можно рассматривать как линейный сегмент (или луч) в трехмерном пространстве, причем 3-й координатой является время. То есть он начинается в некоторый момент времени t_s (когда он был создан в событии или в качестве начальной вершины волнового фронта, который падает в точку входа) и заканчивается в некоторый момент времени t_v (если это ограниченный край) в некотором событии волнового фронта.

Теперь, чтобы найти кривую смещения расстояния t, выполните итерацию по всем дугам, и для каждого ar c, который вы еще не посетили, который существует в момент времени t (т. Е. T_s

Вопрос, конечно, тогда в том, где заканчивается этот сегмент. Чтобы найти его конечную точку, идите вдоль прямой грани скелета, первоначально двигаясь вдоль направления распространения волнового фронта. То есть следующий ar c, на который вы смотрите, относится к точке t_e элемента a. Идите вдоль лица, пока не найдете другой ар c, а ', который жив во время t. Это где ваш сегмент останавливается. Если вы не видели «раньше», то с другой стороны от «есть еще один смещенный сегмент, который вы можете найти таким же образом.

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

Это может быть то, что вы пытаетесь сделать, но это не совсем ясно из вашей анимации.

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

Также см. P. и проведено: вычисление кривых смещенных смещений на основе прямых скелетов (CADA, 12 (4), 2015) .