У меня есть проблема с вычислительной геометрией, которая, как мне кажется, должна иметь относительно простое решение, но я не могу это понять.
Мне нужно определить невыпуклый контур области, определенной несколькими отрезками линии.
Я знаю различные невыпуклые алгоритмы оболочки (например, альфа-формы), но мне не нужен полностью общий алгоритм, так как сегменты линий в большинстве случаев определяют уникальное решение.
Как отметил Жан-Франсуа Корбетт, бывают случаи, когда есть несколько решений. Мне явно нужно больше думать о моем определении.
Однако то, что я пытаюсь сделать, - это обратный инженер и использовать проприетарный формат файла, чтобы я мог выполнять базовый анализ данных, собранных мной и другими. Формат файла достаточно прост, но определение алгоритма, который они используют для определения границы, значительно сложнее.
Включение во многие из крайних случаев, которые приведут к неединственному решению, заставляет рассматриваемое программное обеспечение либо сбой без предупреждения, либо молча прочитать файл.
Поэтому, когда существует несколько решений, приемлемым может быть либо создание одного из приемлемых решений, либо возможность определить, что существует несколько решений.
Определение проблемы:
Контур многоугольника никогда не должен пересекать ни один из сегментов и должен быть образован из линий, соединяющих все конечные точки сегментов. Все сегменты должны лежать целиком внутри или вдоль границы многоугольника. Никакая конечная точка не может использоваться более одного раза в контуре (игнорируя "закрытие" многоугольника, добавляя первую точку в конец для программных библиотек, для которых требуется закрыть многоугольники.)
В тех случаях, когда существует несколько решений, отвечающих этим критериям, любое из этих решений будет приемлемым. (Было бы неплохо иметь возможность определить, когда решение не является уникальным, но это не является абсолютно необходимым.)
Примеры:
В качестве примера у меня есть что-то в этом роде:
И я хотел бы выделить следующую область:
Он также должен работать для непересекающихся сегментов. Например.
Я думаю, что (?) есть уникальное решение в любом случае, с учетом критериев выше. (Edit: В целом нет уникального решения, как отметил Жан-Франсуа Корбетт. Однако меня все еще интересует алгоритм, который либо генерирует одно из приемлемых решений.)
Контрольные случаи
Для тестового примера здесь приведен код для создания вышеуказанных цифр. Я использую 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 масштабируется и вращается по главным осям, определяемым разбросом точек, что делает проблему более "круговой".) Однако это создает решения, в которых контур во многих случаях пересекает отрезки. Достаточно легко обнаружить эту и грубую силу оттуда, но, конечно же, лучший способ?
