Этот вопрос немного связан. Я написал алгоритм для разбиения простого многоугольника на выпуклые субполигоны, но теперь у меня возникают проблемы с доказательством того, что он не оптимален (т.е. минимальное число выпуклых многоугольников с использованием точек Штейнера (добавлены вершины)). Мой профессор непреклонен, что это невозможно сделать с помощью жадного алгоритма, такого как этот, но я не могу придумать контрпример.
Итак, если кто-то может доказать, что мой алгоритм является субоптимальным (или оптимальным), я был бы признателен.
Самый простой способ объяснить мой алгоритм с картинками (это из более ранней субоптимальной версии)
То, что мой алгоритм делает, расширяет сегменты линии вокруг точки я до тех пор, пока не достигнет точки на противоположном краю.
Если в этом диапазоне нет вершины, он создает новую (красную точку) и соединяется с ней:
Если в диапазоне есть одна или несколько вершин, она соединяется с ближайшей. Обычно это приводит к разложению с наименьшим числом выпуклых многоугольников:
Однако в некоторых случаях он может выйти из строя - на следующем рисунке, если сначала произойдет подключение средней зеленой линии, это создаст дополнительный ненужный многоугольник. Для этого я предлагаю двойную проверку всех ребер (диагоналей), которые мы добавили, и убедитесь, что они все еще необходимы. Если нет, удалите его:
В некоторых случаях, однако, этого недостаточно. См. Этот рисунок:
Замена a-b и c-d на a-c даст лучшее решение. В этом случае, однако, нет ребер для удаления, поэтому это создает проблему. В этом случае я предлагаю порядок предпочтения: при выборе вершин для соединения рефлекторной вершины, он должен выбрать вершину с наивысшим приоритетом:
самая низкая) ближайшая вершина
med) ближайшая рефлекторная вершина
самый высокий) ближайший рефлекс, который также находится в зоне действия при работе назад (трудно объяснить) -
В этот рисунок, мы видим, что рефлекторная вершина 9 выбрала подключение к 12 (потому что она была самой близкой), когда она лучше соединиться с 5. Обе вершины 5 и 12 находятся в диапазоне, определенном расширенными сегментами линии 10-9 и 8-9, но вершине 5 следует отдать предпочтение, поскольку 9 находится в пределах диапазона, заданного 4-5 и 6-5, но НЕ в диапазоне, заданном 13-12 и 11-12. то есть край 9-12 устраняет рефлекторную вершину в точке 9, но НЕ удаляет рефлекторную вершину в точке 12, но может удалять рефлекторную вершину в точке 5, поэтому предпочтение следует отдавать 5.
Возможно, что ребро 5-12 будет по-прежнему существовать с этой модифицированной версией, но его можно удалить во время последующей обработки.
Есть ли случаи, которые я пропустил?
Псевдокод (по просьбе Джона Фэминеллы) - этого не хватает битов под рисунками 3 и 5
assume vertices in `poly` are given in CCW order
let 'good reflex' (better term??) mean that if poly[i] is being compared with poly[j], then poly[i] is in the range given by the rays poly[j-1], poly[j] and poly[j+1], poly[j]
for each vertex poly[i]
if poly[i] is reflex
find the closest point of intersection given by the ray starting at poly[i-1] and extending in the direction of poly[i] (call this lower bound)
repeat for the ray given by poly[i+1], poly[i] (call this upper bound)
if there are no vertices along boundary of the polygon in the range given by the upper and lower bounds
create a new vertex exactly half way between the lower and upper bound points (lower and upper will lie on the same edge)
connect poly[i] to this new point
else
iterate along the vertices in the range given by the lower and upper bounds, for each vertex poly[j]
if poly[j] is a 'good reflex'
if no other good reflexes have been found
save it (overwrite any other vertex found)
else
if it is closer then the other good reflexes vertices, save it
else
if no good reflexes have been found and it is closer than the other vertices found, save it
connect poly[i] to the best candidate
repeat entire algorithm for both halves of the polygon that was just split
// no reflex vertices found, then `poly` is convex
save poly
Оказывается, есть еще один случай, который я не ожидал: [Рисунок 5]
Мой алгоритм попытается подключить вершину 1 к 4, если я не добавлю еще одну проверку, чтобы убедиться, что она может. Поэтому я предлагаю набивать все "в диапазоне" в очередь приоритетов, используя указанную выше схему приоритетов, а затем принимать наивысший приоритет, проверить, может ли он подключиться, если нет, вытащить его и использовать следующий. Я думаю, что это делает мой алгоритм O (r n log n), если я его оптимизирую правильно.
Я собрал веб-сайт, который свободно описывает мои выводы. Я, как правило, перемещаю вещи вокруг, поэтому получаю его, пока он горячий.
