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

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

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

• линия (1x=2y=3z), используя правило правой руки
• (единичный) вектор (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

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

Я не могу подтвердить эффективность этого кода, но он работает, и вы можете оптимизировать его части по мере необходимости, я просто не умею этого.
Код находится на C #, с использованием классов системной коллекции и 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;
}