Posiziona il cerchio in modo tale che si sovrapponga alla maggior parte degli altri cerchi

2

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?
posta heishe 10.07.2016 - 22:27
fonte

1 risposta

2

Ecco un suggerimento. Presumo che tu voglia che il massimo disk- area si sovrapponga, ma questa idea funziona anche se vuoi massimizzare il numero di cerchi parzialmente coperti.

Lascia che r sia il raggio del disco di copertura di cui cerchi il centro. Aumenta i raggi di tutti gli altri dischi r . Chiama l'insieme risultante di cerchi / dischi ingranditi C . Calcola ora la profondità di sovrapposizione della disposizione determinata da C . Posiziona il centro del disco di copertura in una cella con la disposizione della massima profondità.

Non è facile calcolare le celle di disposizione delle cerchie , ma può essere fatto. Si potrebbe approssimare questo usando una griglia, essenzialmente pixelizzando i dischi.

    
risposta data 11.07.2016 - 16:57
fonte

Leggi altre domande sui tag