У меня есть проблема вычислительной геометрии, которая, как мне кажется, должна иметь относительно простое решение, но я не могу ее понять.
Мне нужно определить невыпуклый контур области, определенной несколькими отрезками.
Мне известны различные алгоритмы невыпуклой оболочки (например, альфа-формы), но мне не нужен полностью общий алгоритм, поскольку отрезки линий в большинстве случаев определяют уникальное решение.
Как отметил @ Жан-Франсуа Корбетт, бывают случаи, когда существует несколько решений. Мне явно нужно больше думать о своем определении.
Однако я пытаюсь провести обратный инжиниринг и использовать собственный формат файла, чтобы я мог проводить базовый анализ данных, собранных мной и другими. Формат файла достаточно прост, но определить алгоритм, который они используют для определения границы, значительно сложнее.
Если во многих крайних случаях это приведет к неуникальному решению, то соответствующее программное обеспечение либо аварийно завершит работу, либо не прочитает файл по умолчанию.
Следовательно, при наличии нескольких решений приемлемо либо генерирование одного из приемлемых решений, либо возможность определить, что существует несколько решений.
Определение проблемы:
Контур многоугольника никогда не должен пересекать ни один из сегментов и должен состоять из линий, соединяющих все конечные точки сегментов. Все сегменты должны лежать полностью внутри или вдоль границы многоугольника. Ни одна конечная точка не может использоваться более одного раза в контуре (игнорирование «закрытия» многоугольника путем добавления первой точки в конце для библиотек программного обеспечения, для которых требуется закрытие многоугольников.).
В тех случаях, когда существует несколько решений, которые удовлетворяют этому критерию, любое из этих решений будет приемлемым. (Было бы неплохо иметь возможность определить, когда решение не является уникальным, но это не является строго обязательным.)
Примеры:
Например, у меня есть что-то вроде этого:
И я хотел бы выделить следующую область:
Это также должно работать для непересекающихся сегментов. Э.Г.
Я думаю (?) В любом случае есть уникальное решение, в соответствии с критериями, изложенными ранее. (Правка: в общем-то, как отметил Жан-Франсуа Корбетт, единственного решения не существует. Однако мне все еще интересен алгоритм, который либо сгенерировал бы одно из приемлемых решений.)
Контрольные примеры
Для тестового примера вот код для генерации приведенных выше цифр. Я использую здесь Python, но вопрос не зависит от языка.
import matplotlib.pyplot as plt
def main():
test1()
test2()
plt.show()
def test1():
"""Intersecting segments."""
segments = [[(1, 1), (1, 3)],
[(3.7, 1), (2, 4)],
[(2, 0), (3.7, 3)],
[(4, 0), (4, 4)],
[(4.3, 1), (4.3, 3)],
[(0, 2), (6, 3)]]
desired_outline = [segments[0][0], segments[5][0], segments[0][1],
segments[1][1], segments[2][1], segments[3][1],
segments[4][1], segments[5][1], segments[4][0],
segments[3][0], segments[1][0], segments[2][0],
segments[0][0]]
plot(segments, desired_outline)
def test2():
"""Non-intersecting segments."""
segments = [[(0, 1), (0, 3)],
[(1, 0), (1, 4)],
[(2, 1), (2, 3)],
[(3, 0), (3, 4)]]
desired_outline = [segments[0][0], segments[0][1], segments[1][1],
segments[2][1], segments[3][1], segments[3][0],
segments[2][0], segments[1][0], segments[0][0]]
plot(segments, desired_outline)
def plot(segments, desired_outline):
fig, ax = plt.subplots()
plot_segments(ax, segments)
ax.set_title('Segments')
fig, ax = plt.subplots()
ax.fill(*zip(*desired_outline), facecolor='gray')
plot_segments(ax, segments)
ax.set_title('Desired Outline')
def plot_segments(ax, segments):
for segment in segments:
ax.plot(*zip(*segment), marker='o', linestyle='-')
xmin, xmax, ymin, ymax = ax.axis()
ax.axis([xmin - 0.5, xmax + 0.5, ymin - 0.5, ymax + 0.5])
if __name__ == '__main__':
main()
Есть идеи?
Я начинаю подозревать, что программное обеспечение, результаты которого я пытаюсь воспроизвести, использует алгоритм радиальной развертки в некоторой «внутренней» системе координат (например, система координат с масштабированием x-prime и y-prime и повернутый вдоль главных осей, определяемых разбросом точек. Это делает проблему более «круглой».) Однако это дает решения, когда контур во многих случаях пересекает отрезки. Это достаточно легко обнаружить и отобрать оттуда, но наверняка есть лучший способ?