Dato un elenco di cerchi (ognuno con parametri (x, y, raggio)) Voglio posizionare un altro cerchio con un raggio fisso in modo tale che si sovrapponga alle cerchie massime possibili dall'elenco di cerchi.
Finché il cerchio inserito si sovrappone alla quantità ottimale di cerchi, non mi interessa il posizionamento esatto (cioè se ci sono più posizionamenti possibili con lo stesso numero di sovrapposizioni, non mi interessa quale viene restituito) .
Per semplificare un po ', vediamo che ho già un modo rapido (struttura dati di partizionamento spaziale o qualcosa di simile) per determinare circle < - > il cerchio si sovrappone in generale (cioè trova in quale cerchio si sovrappone un altro cerchio).
Come posso calcolare (x, y) [dal momento che il raggio è fissato] del cerchio del posizionamento?
Domanda bonus:
- Come posso calcolare più rapidamente?
Domanda bonus bonus:
- Diciamo che sono felice con una risposta approssimativa. Non deve essere il valore ottimale esatto finché è abbastanza vicino e la soluzione non è ovviamente sbagliata (ad esempio su 10 cerchi nell'elenco, il posizionamento ottimale sarebbe 9 cerchi e la soluzione approssimativa trova solo il posizionamento per 2 sovrapposizioni). Posso migliorare ulteriormente la velocità di calcolo con questa restrizione sollevata? Potrei forse farlo con campionamento casuale, scegliere il miglior risultato e scegliere la distribuzione dei campioni in un modo che garantisca un risultato decente?