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

Мне нужно определить невыпуклый контур области, заданной несколькими отрезками.

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

---

Как указал @Jean-FrançoisCorbett, бывают случаи, когда существует несколько решений. Мне явно нужно больше думать о моем определении.

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

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

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

---

Постановка задачи:

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

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

---

Примеры:

В качестве примера у меня есть что-то вроде этого:

И я хотел бы очертить следующую область:

Это также должно работать для непересекающихся сегментов. Например.

Я думаю (?), что в любом случае есть единственное решение, в соответствии с изложенными ранее критериями. (Редактировать: в целом не существует уникального решения, как указал @Jean-FrançoisCorbett. Однако меня все еще интересует алгоритм, который либо генерировал бы одно из приемлемых решений.)

Тестовые случаи

В качестве тестового случая вот код для создания приведенных выше рисунков. Я использую здесь 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масштабируется и вращается вдоль главных осей, определяемых разбросом точек. Это делает задачу более «круговой».) Однако во многих случаях это дает решения, в которых контур пересекает отрезки прямой.Это достаточно легко обнаружить и переборщить оттуда, но наверняка есть лучший способ?