Алгоритм упорядочения ребер вокруг вершины в 3D против часовой стрелки

Question

Как упорядочить отрезки (ребра в сетке) вокруг вершины против часовой стрелки относительно вершины?

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

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

Я не заинтересован в каком-либо пакете, библиотеке или программном обеспечении.Я буду реализовывать это самостоятельно.Меня интересует только рабочий алгоритм.

РЕДАКТИРОВАТЬ: Чтобы прояснить вопрос, я добавляю, что для каждой вершины у меня уже есть список соединительных ребер (и так вершин), уже.Цель состоит в том, чтобы упорядочить список окружающих вершин таким образом, чтобы их последовательное соединение создало многоугольник (кольцо), не являющийся самопересекающимся и «общим» против часовой стрелки.

введите описание изображения здесь

Answer 1

В общем случае вы не можете.(Подумайте о центре тетраэдра и четырех ребрах вершин.)

Для сетчатой ​​поверхности мы можем предположить, что вы знаете нормаль в каждой вершине.Затем вы можете спроецировать ребра на касательную плоскость (используя локальную рамку) и решить проблему упорядочения в 2D.

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