Ricerca di tutti i punti che si trovano su una riga nel sistema di coordinate 2D

0

Ho una serie di punti. Ogni punto ha due membri - x e y

Voglio ottenere 3 punti e controllare, si trovano nella linea singola nel sistema di coordinate 2D.

Ad esempio: 1x2, 2x3, 5x6:

Se sì, voglio cercare un altro punto nel mio array che si trova in quella linea (la linea non ha inizio né fine). E così via, mentre non ho controllato tutti i punti rimasti.

Quindi, voglio controllare la prossima combinazione di 3 punti e ripetere mentre tutte le permutazioni a 3 punti non sono spuntate. Per ognuna di queste permutazioni voglio dire quanti punti si trovano nella linea singola (0 - se questi 3 punti non si trovano nella linea singola, 3 - se sono, 4 - se sono e questo è l'altro punto che si trova anche in quella linea, ecc.). Esiste un algoritmo efficace in grado di farlo in complessità uguale o inferiore a O (n 3 )?

    
posta user99295 11.08.2013 - 19:03
fonte

1 risposta

2

Per due punti è possibile calcolare la pendenza e l'intercetta y. Se due segmenti diversi fanno parte della stessa linea, avranno la stessa pendenza e la stessa intercettazione. Se hanno la stessa pendenza, ma interconnessioni diverse, sono parallele.

L'unico problema è quando la linea è verticale, la pendenza è infinita e non c'è intercetta, a meno che non sia la linea x = 0.

Calcola tutte le coppie di punti, quindi raggruppali per inclinazione e intercetta.

    
risposta data 11.08.2013 - 19:37
fonte

Leggi altre domande sui tag