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

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

10 голосов
/ 30 июля 2011

В трехмерном пространстве у меня есть неупорядоченный набор, скажем, 6 баллов;примерно так: 

           (A)*
                          (C)*
(E)*
                         (F)*
     (B)*

                  (D)*

Точки образуют трехмерный контур, но они неупорядочены.Для неупорядоченных я имею в виду, что они хранятся в 

unorderedList = [A - B - C - D - E - F]

. Я просто хочу реорганизовать этот список, начиная с произвольного местоположения (скажем, точка A) и проходя точки по часовой стрелке или против часовой стрелки.Примерно так: 

orderedList = [A - E - B - D - F - C]

или 

orderedList = [A - C - F - D - B - E]

Я пытаюсь реализовать алгоритм настолько простым, насколько это возможно, поскольку упомянутое множество точек соответствует окрестности N-кольцакаждой вершины на сетке ~ 420000 точек, и я должен сделать это для каждой точки на сетке.

Некоторое время назад было подобное обсуждение относительно точек в 2-D, но пока мне не ясно, как перейти от этого подхода к моему трехмерному сценарию.

Ответы [ 2 ]

7 голосов
/ 30 июля 2011

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

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

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

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

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

Входы:

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

Установка:

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

Алгоритм:

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

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

1 голос
/ 25 февраля 2017

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