Как найти "контур" (вогнутого) графа в 2D плоскости?
У меня есть связный граф в 2D плоскости, состоящей из нескольких вершин и некоторых ребер, определенных между ними. Общая форма графа не обязательно является выпуклой, то есть смежные вершины выпуклой оболочки не всегда связаны ребром. Есть ли существующий алгоритм, который находит "контур" этого графика? Больше всего меня беспокоит то, что этот многоугольник контуров может содержать вершины, которые не являются вершинами исходного графа, а скорее пересечением двух ребер, так что я не совсем уверен, как с этим справиться...
Спасибо!
Niko