Dato n punti su un piano 2D, qual è il punto in cui la distanza da tutti i punti è ridotta al minimo? Questo punto non deve essere dal set di punti dati. È un centroide o qualcos'altro?Trovare il punto più vicino da una serie di punti sull'aereo
Come trovare tutti questi punti (se più di uno) con un algoritmo?
Questo è noto come "Centro di distanza" ed è diverso dal centroide.
In primo luogo è necessario definire quale misura della distanza si sta utilizzando. Se assumiamo che stai usando la metrica standard di d = sqrt ((x1-x2)^2 + (y1-y2)^2), allora non è univoco, e il problema sta minimizzando questa somma.
L'esempio più semplice per mostrare questa risposta non è univoco è l'esempio di linea retta. Qualsiasi punto tra i due punti ha una distanza totale uguale da tutti i punti.
In 1D, la risposta corretta sarà qualsiasi risposta che abbia lo stesso numero di punti a destra e a sinistra. Finché questo è vero, qualsiasi spostamento verso sinistra e verso destra aumenterà e diminuirà i lati sinistro e destro della stessa quantità, e quindi lascerà la distanza uguale. Ciò dimostra anche che il centroide non è necessariamente la risposta giusta.
Se estendiamo a 2D questo non è più il caso - poiché sqrt rende il problema ponderato. Sorprendentemente per me non sembra essere un algoritmo standard! La pagina here sembra utilizzare un metodo di forza bruta. Non l'ho mai saputo!
Se volessi utilizzare un algoritmo, troverei il punto mediano in X e Y come punto di partenza, quindi userei un gradient descent algorithm - questo otterrebbe la risposta abbastanza rapidamente. L'intera equazione finisce come quadratica, quindi sembra che dovrebbe esserci una soluzione esatta.
L'algoritmo di forza bruta nel primo collegamento non lo fa per punti su una sfera? –
No, ho detto discesa gradiente per n punti. Scrivi la tua funzione di punteggio in modo che calcolasse la distanza totale per tutti i n punti, quindi lascia che la tua funzione di discesa minimizzi questo valore. Non ho intenzione di aggiungere del codice nel caso in cui sia compito, dovrebbe essere facile da scrivere. –
@Matthijs, molto probabilmente, non mi sembrava troppo difficile. Grazie per la segnalazione. È una domanda interessante, no? –
Ci possono essere più di un punto. Considera un aereo con solo due punti su di esso. Questi punti descrivono un segmento di linea. Qualsiasi punto su quel segmento di linea avrà la stessa distanza totale dai due punti finali.
Quindi, come trovare tutti questi punti con un algoritmo? – nowonder
In effetti la risposta sarà un semplice poligono. Il motivo è che una somma di funzioni convesse (come la funzione di distanza) è anch'essa convessa. Probabilmente potresti trovare le sue coordinate esatte partendo da un triangolo e aggiungendo punti. Comunque facendolo in modo ingenuo sarebbe 'n^2'. –
Una forza bruta algo. potrebbe darti i migliori risultati In primo luogo, individuare un rettangolo/qualsiasi quadrilatero che delimita i punti di input. Infine, per ogni punto all'interno del rettangolo, calcola la distanza da altri punti. Sommare le distanze del punto dal set di input. Diciamo che questo è il "costo" del punto. Ripeti per ogni punto e seleziona il punto con min. costo.
L'intelligenza può anche essere aggiunta al algo. può eliminare aree in base al costo medio, ecc ...
Ecco come vorrei affrontare il problema almeno ... spero che sia d'aiuto.
Ma ha una complessità molto alta. Controllando ogni punto all'interno del rettangolo, come farlo, le coordinate del punto possono essere qualsiasi numero in virgola mobile. – nowonder
beh ovviamente hai bisogno di una certa dimensione, una distanza minima tra due punti consecutivi, un semplice esempio usando C potrebbe essere: per (riga int = minR; riga
Questo è discusso in dettaglio qui http://www.ddj.com/architect/184405252?pgno=1
Questo è stato interessante ma risolve un problema diverso. L'interrogante ha chiesto il punto che minimizza la distanza da tutti i punti. L'articolo DDJ trova i due punti più vicini l'uno all'altro. –
Non chiudere questa, algoritmi di geometria sono del tutto nell'ambito di overflow dello stack –
E 'compiti a casa? Inoltre, in che lingua stai cercando di implementarlo? – Piskvor
No, non è compito. Sto studiando algoritmi sulla geometria computazionale. Quindi ho un dubbio. Lo sto facendo in C. – nowonder