Su un piano 2D, ho 2 rettangoli. Voglio trovare la coppia più vicina di punti (uno su ciascun rettangolo), che sono più vicini l'uno all'altro. Per punti intendo gli angoli dei rettangoli. E no, non si sovrappongono.
C'è un modo per farlo oltre a controllare tutte le distanze tra tutte le combinazioni di punti e trovare quella più piccola?
Il modo in cui lo fai dipende da quali sono i tuoi requisiti di "business".
Se la semplicità del codice sorgente (manutenibilità) è la tua preoccupazione principale, allora il calcolo della forza bruta di tutte le distanze punto-punto sarà un metodo semplice ed efficace. Se è necessario ottimizzare la velocità di elaborazione, è possibile che si desideri trovare un algoritmo ottimizzato. Sospetto che la forza bruta sarà quasi ottimale in ogni caso, dal momento che ci sono solo 16 distanze da punto a punto da calcolare.
Potresti prendere la media del "centro di massa" di tutti gli angoli del piano (un nuovo punto che è in media x e la media y di tutti gli angoli), quindi prendi l'angolo di ogni rettangolo più vicino centro del punto di massa. Dopo il calcolo iniziale del centro di massa, è necessario eseguire un solo calcolo per ogni angolo.
Se i due rettangoli hanno più di un punto che sono ugualmente distanti dal centro di massa complessivo, allora dovresti assicurarti di scegliere tra i punti vincolati i due (uno per ciascun rettangolo) che sono più vicini tra loro , e in questo caso potresti semplicemente fare la cosa n ^ 2'ed (anche se se abbiamo a che fare con poligoni convessi, come i rettangoli, ci potrebbe essere solo un massimo di 2 legami per poligono, quindi in questa fase ci sarebbe sempre e solo essere un ulteriore 2 o 4 calcoli - a seconda se uno o entrambi i poligoni contenevano vincoli).
Questo algoritmo scalerebbe molto bene (O (n)) per ogni due poligoni convessi contenenti ciascuno un numero qualsiasi di angoli (e il loro centro di massa ugualmente distante da ogni angolo che contengono, come rettangoli e tutti i poligoni regolari), se quello conta.
In definitiva, se hai sempre a che fare con i rettangoli, devi decidere se il tempo di computazione ridotto vale la codifica e il test aggiuntivi di qualsiasi algoritmo ottimizzato.
Leggi altre domande sui tag algorithms geometry