Сортировка массива точек по часовой стрелке

Question

Есть ли такой алгоритм для сортировки массива трехмерных точек по часовой стрелке? Я имею дело с правым треугольником в моем случае, так что всего 3 балла. (для сборной сетки)

Answer 1

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

Только пучок точек не может по часовой стрелке или против часовой стрелки сам по себе. Вам нужна плоскость и сторона для ссылки на эту точку.

edit: На самом деле то, что я раньше говорил, немного неточно. То, что вам действительно нужно, - это положение и направление ссылки, а не плоскость

Answer 2

Предположим, у вас есть два ребра, соединяющие ваши три вершины.

E1 = V2 - V1 
E2 = V1 - V3 

Они охватывают треугольник. Вы можете вычислить треугольник нормаль N так:

N = cross(E1, E2) 

Это говорит о том, в каком направлении треугольник сталкивается. Вы можете рассчитать, обращен ли треугольник в сторону или от определенной точки зрения P, проецируя N на расстояние от вашего треугольника от P.

D = V1 - P 
d = dot(N, D) 

Если d положителен, то треугольник смотрит в стороне от P, если она отрицательна, она сталкивается с P.

Теперь вы можете судить о каждом наборе (V1, V2, V3), правильно ли они отсортированы или нет. Если нет, просто замените V2 и V3, и они будут.

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