Сортировка набора трехмерных точек по часовой стрелке/против часовой стрелки

Ответ 1

Понятие "по часовой стрелке" или "против часовой стрелки" не определено без оси и ориентации! (доказательство: что, если вы посмотрели на эти точки с другой стороны экрана монитора или перевернули их, например!)

Вы должны определить ось и ориентацию и указать ее как дополнительный вход. Способы его указания включают:

• строка (1x=2y=3z), используя правое правило
• a (единичный) вектор (A_x, A_y, A_z), используя правое правило; это предпочтительный способ сделать это.

Чтобы определить ориентацию, вам нужно глубже изучить вашу проблему: вы должны определить размер "вверх" и "вниз" сетки. Затем для каждого набора точек вы должны взять центр тяжести (или другую "внутреннюю" точку) и построить единичный вектор, указывающий "вверх" , который является нормальным к поверхности. (Один из способов сделать это - найти плоскость с наименьшим квадратом, затем найти два перпендикулярных вектора через эту точку, выбрав один в направлении "вверх" .)

Вам нужно будет использовать любое из приведенных выше предложений для определения вашей оси. Это позволит вам переформулировать вашу проблему следующим образом:

Входы:

• множество точек {P_i}
• ось, которую мы будем называть "осью z" и рассматривать как единичный вектор, центрированный на центроиде (или где-то "внутри" ) точек
• ориентация (например, против часовой стрелки), выбранная одним из вышеуказанных способов

Настройка:

• Для всех точек выберите два взаимно ортогональных единичных вектора к оси, которые мы будем называть "осью y" и "осью x". (Просто поверните ось-вектора оси z на 90 градусов в двух направлениях, http://en.wikipedia.org/wiki/Rotation_matrix#Basic_rotations)

Алгоритм:

• Для каждой точки P проект P на ось x и ось y (с использованием точечного произведения), затем используйте http://en.wikipedia.org/wiki/Atan2

Как только у вас есть углы, вы можете просто отсортировать их.

Ответ 2

Я не могу подтвердить эффективность этого кода, но он работает, и вы можете оптимизировать его части по мере необходимости, я просто не очень хорош в этом. Код находится в С#, используя классы коллекций системы и linq.
Vector3 - класс с поплавками x, y, z и статические векторные математические функции.
Node - класс с переменной Vector3, называемый pos

//Sort nodes with positions in 3d space.
//Assuming the points form a convex shape.
//Assuming points are on a single plain (or close to it).

public List<Node> sortVerticies( Vector3 normal, List<Node> nodes ) {

    Vector3 first = nodes[0].pos;

    //Sort by distance from random point to get 2 adjacent points.
    List<Node> temp = nodes.OrderBy(n => Vector3.Distance(n.pos, first ) ).ToList();

    //Create a vector from the 2 adjacent points,
    //this will be used to sort all points, except the first, by the angle to this vector.
    //Since the shape is convex, angle will not exceed 180 degrees, resulting in a proper sort.
    Vector3 refrenceVec = (temp[1].pos - first);

    //Sort by angle to reference, but we are still missing the first one.
    List<Node> results = temp.Skip(1).OrderBy(n => Vector3.Angle(refrenceVec,n.pos - first)).ToList();

    //insert the first one, at index 0.
    results.Insert(0,nodes[0]);

    //Now that it is sorted, we check if we got the direction right, if we didn't we reverse the list.
    //We compare the given normal and the cross product of the first 3 point.
    //If the magnitude of the sum of the normal and cross product is less than Sqrt(2) then then there is more than 90 between them.
    if ( (Vector3.Cross( results[1].pos-results[0].pos, results[2].pos - results[0].pos ).normalized + normal.normalized).magnitude < 1.414f ) {
        results.Reverse();
    }

    return results;
}