Этот вопрос немного запутан. Я написал алгоритм разбиения простого многоугольника на выпуклые подполигоны, но теперь у меня возникают проблемы с доказательством того, что он не оптимальный (т. Е. Минимальное количество выпуклых многоугольников с использованием Steiner точки (добавленные вершины)). Мой профессор непреклонен, что этого нельзя сделать с помощью жадного алгоритма, такого как этот, но я не могу придумать контрпример.
Итак, если кто-то может доказать, что мой алгоритм неоптимален (или оптимален), я был бы признателен.
Самый простой способ объяснить мой алгоритм с помощью картинок (это из более старой неоптимальной версии)
То, что делает мой алгоритм, это расширяет отрезки линии вокруг точки i, пока она не достигнет точки на противоположном краю.
Если в этом диапазоне нет вершины, она создает новую (красную точку) и соединяется с ней:
Если равно одной или нескольким вершинам в диапазоне, он подключается к ближайшей. Это обычно производит разложение с наименьшим количеством выпуклых многоугольников:
Однако в некоторых случаях это может дать сбой - на следующем рисунке, если случится сначала соединить среднюю зеленую линию, это создаст дополнительный ненужный многоугольник. Для этого я предлагаю дважды проверить все ребра (диагонали), которые мы добавили, и убедиться, что они все еще необходимы. Если нет, удалите его:
В некоторых случаях, однако, этого недостаточно. Смотрите этот рисунок:
Замена a-b и c-d на a-c даст лучшее решение. В этом случае, однако, нет ребер для удаления, поэтому это создает проблему. В этом случае я предлагаю порядок предпочтения: при решении, к какой вершине подключить рефлекторную вершину, она должна выбрать вершину с наивысшим приоритетом:
низшая) ближайшая вершина
мед) ближайшая рефлекторная вершина
наивысший) ближайший рефлекс, который также находится в диапазоне при работе в обратном направлении (трудно объяснить) -
На этой фигуре мы можем видеть, что рефлекторная вершина 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), если я правильно его оптимизирую.
Я собрал веб-сайт , который в общих чертах описывает мои выводы. Я склонен что-то передвигать, так что бери его пока жарко.