Ordinare una serie di punti 3D in senso orario/antiorario.

Question

Nello spazio 3-D ho un insieme non ordinato di, diciamo, 6 punti; qualcosa di simile:

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

        (D)* 

I punti formano un contorno 3-D ma sono non ordinati. Per non ordinata voglio dire che sono memorizzati in un

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

Voglio solo di riorganizzare questa lista a partire da una posizione arbitraria (diciamo punto A) e attraversa i punti in senso orario o antiorario. Qualcosa di simile a questo:

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

o

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

Sto cercando di implementare un algoritmo più semplice possibile, dal momento che l'insieme dei punti di menzione corrisponde ad un quartiere di N-ring di ogni vertice su una maglia di ~ 420000 punti, e devo farlo per ogni punto della maglia.

Qualche tempo fa c'era un similar discussion per quanto riguarda i punti in 2-D, ma per ora non è chiaro per me come passare da questo approccio al mio scenario 3D.

Answer 1

La nozione di "in senso orario" o "in senso antiorario" non è ben definita senza un asse e un orientamento! (prova: cosa succede se hai guardato quei punti dall'altro lato dello schermo del monitor, o li hai ruotati, ad esempio!)

È necessario definire un asse e un orientamento e specificarlo come input aggiuntivo. Modi per specificare che includono:

• una linea (1x=2y=3z), utilizzando la regola della mano destra
• un (unità) vettore (A_x, A_y, A_z), utilizzando la regola della mano destra; questo è il modo preferito per farlo

Per determinare l'orientamento, è necessario approfondire il problema: è necessario definire una dimensione "in alto" e "in basso" della mesh. Quindi per ogni serie di punti, devi prendere il centroide (o un altro punto "interno") e costruire un vettore unitario che punta "su" che è normale alla superficie. (Un modo per farlo sarebbe quello di trovare il piano dei minimi quadrati-fit, quindi trovare i due vettori perpendicolari per quel punto, raccogliendo l'uno in direzione "up".)

---

Sarà necessario utilizzare uno dei suggerimenti sopra riportati per determinare l'asse. Questo vi permetterà di riformulare il problema nel modo seguente:

Ingressi:

• l'insieme dei punti {p_i}
• un asse, che chiameremo "l'asse z" e trattare come vettore unitario centrato sul centroide (o da qualche parte "dentro") dei punti
• un orientamento (ad es.antiorario) scelto da uno dei metodi sopra

Setup:

• Per tutti i punti, selezionare due versori mutuamente ortogonali all'asse, che chiameremo "y" e " l'asse x ". (Basta ruotare l'asse z versori 90 gradi in due direzioni, http://en.wikipedia.org/wiki/Rotation_matrix#Basic_rotations)

Algoritmo:

• Per ogni punto P, progetto P sul asse xe asse y (usando il prodotto punto), quindi utilizzare http://en.wikipedia.org/wiki/Atan2

Una volta ottenuti gli angoli, è possibile ordinarli.

Answer 2

Non riesco a certificare l'efficienza di questo codice, ma funziona, ed è possibile ottimizzare parti di esso in base alle esigenze, non sono bravo a farlo.
Il codice è in C#, utilizzando le classi di raccolta del sistema e linq.
Vector3 è una classe con le funzioni matematiche vettoriale di float x, y, z e static.
nodo è una classe con la variabile Vector3 chiamato 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; 
}