3 차원 점 집합을 시계 방향/시계 반대 방향으로 정렬

Question

3 차원 공간에서 말하지 않은 집합은 6 점입니다.

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

        (D)* 

포인트는 3 차원 등고선을 형성하지만 순서는 없습니다. 순서가 들어 나는 그들이 그냥 임의의 위치에서 시작하는이 목록을 재구성하려는

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 차원에서 점에 관한 similar discussion이 있었지만, 지금은이 접근법을 내 3 차원 시나리오로 이동하는 방법이 명확하지 않습니다.

Answer 1

"시계 방향"또는 "반 시계 방향"이라는 개념은 축과 방향이 없으면 잘 정의되어 있지 않습니다! (증명 : 모니터 화면의 다른면에서이 지점을 보거나 뒤집 으면 어떻게됩니까?)

축 및 방향을 정의하고 추가 입력으로 지정해야합니다. 그것을 지정하는 방법이 포함

• 오른손 법칙을 사용하여 오른손 법칙
• A (부) (A_x, A_y, A_z) 벡터를 사용하여 라인 (1x=2y=3z); 이것이 바람직한 방법입니다.

방향을 결정하려면 문제를 자세히 살펴야합니다. 메시의 "위"및 "아래"크기를 정의해야합니다. 그런 다음 각 점 집합에 대해 중심 (또는 다른 "내부"점)을 가져 와서 표면에 수직 인 "위로"를 가리키는 단위 벡터를 구성해야합니다. (이 작업을 수행하는 한 가지 방법은 다음 "최대"방향을 따기, 그 시점을 통해 두 개의 수직 벡터를 발견, 최소 제곱 맞는면을 발견하는 것입니다.)

---

당신이 필요합니다 위의 제안 사항 중 하나를 사용하여 축을 결정하십시오. 이것은 다음과 같이 문제를 재구성 할 수 있습니다 :

입력 :

• 포인트 {P_i}
• 우리가 부르는 "z 축"과 같이 취급된다 축, 세트 단위 벡터는 중심점 (또는 어딘가에 "내부"라고 함)의 중심에 위치합니다.
• 반 시계 방향으로) 상기 방법
중 하나에 의해 선택

설치 모든 점

• 우리 통화 "Y 축"및 "한다 축에 두 개의 상호 직교 단위 벡터를 선택할 x 축 "으로 표시됩니다. 각 점 P 들어
  • , X 축 및 Y 축 상에 프로젝트 P (사용 :

  알고리즘 (다만, 두 방향으로 Z 축 단위 벡터를 http://en.wikipedia.org/wiki/Rotation_matrix#Basic_rotations을 90도 회전) 내적 제품)을 입력 한 다음 사용합니다. http://en.wikipedia.org/wiki/Atan2

각도를 지정하면 정렬 할 수 있습니다.

Answer 2

이 코드의 효율성을 증명할 수는 없지만 제대로 작동하고 필요에 따라 부분을 최적화 할 수 있습니다.
코드는 시스템 콜렉션 클래스 및 linq을 사용하여 C#에 있습니다.
Vector3는 float x, y, z 및 정적 벡터 연산 함수가있는 클래스입니다.
노드 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; 
}