Trova il modello più adatto per il cerchio

Questa non è una soluzione generale, poiché ci sono diverse situazioni in cui non fornirà la posizione del cerchio blu con la distanza più breve dal punto bianco. Ad esempio, se hai 100 palle rosse raggruppate insieme e il punto bianco è lontano da questo gruppo di palline rosse, nessuna delle palle rosse avrà alcuna influenza sulla posizione del cerchio blu che può essere centrata solo sul punto bianco . Né mostrerà tutti i dettagli dei calcoli. Ad ogni modo, per un sottoinsieme di configurazioni, dove la soluzione (cerchio blu) è tangente a due cerchi rossi, dovrebbe funzionare quanto segue:
1) sia R il raggio del cerchio blu
2) fai un loop su tutte le coppie di cerchi rossi, sì, lo so che è O (n2).
3) per ogni coppia di cerchi i, j con centri a (xi, yi) e (xj, yj) con il rispettivo raggio ri e rj, calcola il quadrato della distanza tra la coppia di cerchi

d_ij^2=(xi-xj)^2+(yi-yj)^2  

4) metti tutte le coppie di cerchi che

dij^2<R^2

in una lista.

5) attraversa la lista, trovando le 2 soluzioni di cerchi di raggio R tangente a entrambi i cerchi i e j. Per fare questo usa queste equazioni insieme a questa immagine

a = R+ri  
b = R+rj  
c = dij  
α = arccos((b^2+c^2-a^2)/(2bc)  

con le informazioni di cui sopra puoi trovare (X1ij, Y1ij) e (X2ij, Y2ij) i centri dei 2 cerchi tangenti ai cerchi i e j. Per ogni candidato cerchi un cerchio blu su tutte le altre cerchie rosse e vedi se non si sovrappongono. Se lo fanno scartare se non controllano la distanza dal cerchio bianco. Se mantieni quello a distanza ridotta penso che avrai la soluzione quando finisci di percorrere l'elenco di coppie di cerchi. L'algoritmo sembra O (n3).

Il posizionamento più vicino al punto sarà sul punto o toccando un cerchio.

quindi, prima controlla il punto, quindi tira il nuovo cerchio attorno al bordo di ogni cerchio esistente, calcolando la distanza dal punto e se ti sovrapponi mentre stai andando e tenendo traccia del punto di distanza minimo. Fermati quando hai attraversato ogni cerchio.

es. controlla tutti i punti sulle linee verdi, più il cerchio bianco. dove la linea verde è un cerchio con raggio del rosso più il blu

devicontrollarel'interalineaverde,nonsololeintersezioniinmododacoprirequesticasilimite.

Ovviamente la dimensione del tuo attraversamento sarà importante in termini di prestazioni. Tuttavia, quando affermi che le prestazioni non sono un problema, scegli il valore corrispondente alla risoluzione del tuo valore di output. cioè float, long?

Chiarimento:

il mio suggerimento è di forzare la forza bruta su tutti i punti attorno ai ogni test del cerchio per sovrapporsi a tutti gli altri cerchi in ogni punto. nessuna intelligenza.

Se l'immagine di esempio è indicativa del numero di cerchi e risoluzione, non dovrebbe essere un problema per un PC standard

abbiamo 20 cerchi di raggio medio 200 quindi questo è approssimativamente 20 * 2 π * 200 punti * 20 test di intersezione = 4800000 iterazioni

Nota:

Approcci iterativi come questo sono viziati dal fatto che le dimensioni del tuo passo, in questo caso la risoluzione del tuo output, possono influenzare notevolmente il risultato.

Supponiamo di avere due cerchi rossi separati da 2 pixel e un cerchio blu con raggio di 1 pixel tra loro. Chiaramente con uno dei due pixel come il centro del cerchio blu si sovrapporrà a uno dei rossi. ma ovviamente c'è spazio per il cerchio se il centro si trova tra i due pixel.

Da qui il mio commento che chiede la risoluzione dell'output. che hai detto potrebbe essere qualsiasi cosa.

puoi anche risolvere l'equazione simultanea per ogni coppia di cerchi con raggio aumentato del raggio del cerchio blu.

questo ti darà i punti in cui il cerchio blu toccherà entrambi i cerchi rossi in modo più preciso rispetto all'iterazione.

Tuttavia. ci sono diverse condizioni in cui, se fai questo, ottieni la risposta sbagliata o assente. vale a dire.

1 o nessuna cerchi

2 o più cerchi ma con il punto di mira lontano e al di fuori di essi.

molti cerchi ma con il punto di mira vicino alla superficie

Questo plunk contiene codice funzionante,

Concetto

I cerchi dati sono C1, C2 .... Cn

e le coordinate del cerchio Cn sono Cnx, Cny e il raggio è Cr

e il raggio del cerchio richiesto è R

se il cerchio blu è in posizione X, Y e se non è in conflitto con nessun altro cerchio, le seguenti equazioni sono vere

(C1x - X)^2 + (C1y - Y)^2 > (C1r + R)^2
(C2x - X)^2 + (C2y - Y)^2 > (C2r + R)^2
....
(Cnx - X)^2 + (Cny - Y)^2 > (Cnr + R)^2

Modifica della prima equazione,

C1x^2 - 2C1x*X + X^2 + C1y^2 - 2C1y*Y + Y^2 > C1r^2 + 2C1r*R + R^2
X^2 + Y^2 - 2C1x*X - 2C1y*Y > C1r^2 + 2C1r*R + R^2 - C1x^2 - C1y^2

così le equazioni possono riscrivere come,

X^2 + Y^2 - 2C1x*X - 2C1y*Y > C1r^2 + 2C1r*R + R^2 - C1x^2 - C1y^2
X^2 + Y^2 - 2C2x*X - 2C2y*Y > C2r^2 + 2C2r*R + R^2 - C2x^2 - C2y^2
....
X^2 + Y^2 - 2Cnx*X - 2Cny*Y > Cnr^2 + 2Cnr*R + R^2 - Cnx^2 - Cny^2

Implementazione

inizia dalla coordinata del punto bianco (Xw, Yw),

    var isValidLocation = function(x,y,r){
       var valid = true;
       for (var i = 0; i< circles.length; i++){
          var circle = circles[i];
          valid = valid && ((x*x + y*y - 2*circle.x*x - 2*circle.y*y) > (circle.radius*circle.radius + 2*circle.radius*r + r*r - circle.x*circle.x - circle.y*circle.y));
       }
       return valid;
      };

      var find = function(Xw,Yw,Rw){
        var radius = 0;
        while(true){
          for (var x=-1 * radius ;x <= radius; x++) {
            for (var y=-1 * radius;y <= radius; y++) {
               if (isValidLocation(Xw + x,Yw + y, Rw)){
                 drawCircle(Xw + x,Yw + y,Rw,"#0000FF");
                 return;
               }
            }   
          } 
          radius++;
        }
     }; 

la prima coordinata trovata per soddisfare tutte le equazioni è la posizione del cerchio blu

• O è il punto che stai cercando di essere vicino a
• P è il punto che stai cercando (il centro del cerchio blu
• r è il raggio del cerchio blu
• C0 .. Cn è il centro di tutti i cerchi che limitano il posizionamento del blu su

• Cerchio esteso è uno dei cerchi con raggio esteso da r

  C'è qualche lavoro in più se O non si trova in un centro del cerchio. Quindi adesso supponiamo O == C0

Calcola tutte le intersezioni di tutte le cerchie con C0, utilizzando i rispettivi raggi più il r , cioè intersecano i cerchi estesi con C0 esteso. Se non ci sono intersezioni, il punto che stai cercando è ovunque su C0, se ci sono intersezioni, per ogni controllo di intersezione se si trova all'interno di un altro cerchio esteso (puoi limitarti ai cerchi che avevano intersezioni con C0). Prendi la prima intersezione che non è in un altro cerchio esteso come P, potrebbero essercene altri.

Se non ci sono intersezioni tra i cerchi estesi e C0 che non si trovano all'interno di un altro cerchio esteso, calcola le intersezioni tra tutti i cerchi estesi l'una con l'altra. Quindi controlla queste intersezioni in ordine di distanza a O, sempre che nessuna delle intersezioni si trovi all'interno di un altro cerchio esteso, se sì scarta, se non è questo il tuo risultato.

Se immagini di disegnare una linea attorno a tutti i cerchi che indicano una possibile posizione per il tuo cerchio blu, prendendo l'unione di tutti i cerchi estesi indicherà l'area che il tuo cerchio blu non può essere. Il punto che stai cercando è il punto più vicino che non è in quella unione. Se c'è un punto su C0 che non è in quella unione è la soluzione, se C0 è completamente coperto allora P deve trovarsi su un'intersezione tra altri due cerchi estesi, e deve essere in un'area che non è coperta da questa unione (cioè non in una cerchia estesa ).

Questo è O (n ^ 2), ci sono alcuni modi per migliorare questo, però griglia può essere usato per ridurre lo sforzo della ricerca saggia di coppia, inoltre penso che l'ordinamento dei cerchi per la loro vicinanza a O, (la distanza tra i due cerchi ridotti dalla radio) aiuterebbe a limitare lo spazio di ricerca per la ricerca di copertura e intersezione

Possibili soluzioni ricerca

1. Controlla se il punto bianco è la soluzione da solo. Copre caso con 0 cerchi rossi e caso banale quando i cerchi rossi sono lontani dal punto bianco.
2. Un cerchio rosso.
   1. Il punto bianco è il centro del cerchio. Le possibili soluzioni sono un numero infinito di punti sul cerchio con il suo centro nel punto bianco e il raggio essendo la somma del raggio dei cerchi blu e il diametro del cerchio rosso. Chiamiamolo the green circle .
   2. Il punto bianco è da qualche altra parte. C'è solo una soluzione possibile sulla linea che collega il punto bianco e il centro del cerchio rosso, è il raggio del cerchio blu lontano dal punto in cui il cerchio rosso attraversa la linea verso il punto bianco.
3. Due o più cerchi rossi.
   1. Prendiamo le cerchie rosse una per una e cerchiamo la possibile soluzione per ognuna di esse individualmente in base al punto 2 (un cerchio).
   2. Per ogni coppia di cerchi rossi controlliamo se è possibile disegnare il cerchio blu toccando entrambi quelli rossi. Cioè se la distanza tra i loro centri è uguale o inferiore alla somma dei loro raggi più il diametro del cerchio blu. Se puoi, allora ne hai due (o uno se i cerchi rossi hanno esattamente un diametro di cerchio blu) possibili soluzioni .

Ricerca di soluzioni effettive tra possibili soluzioni

Ora disponi di un insieme di punti che sono possibili soluzioni , esegui l'iterazione e controlla ciascuno di essi.

1. Se il punto è in realtà una soluzione. A questo punto, nessun cerchio rosso dovrebbe avere il centro più vicino del suo raggio.
2. Se è più vicino al punto di bianco rispetto alla soluzione trovata prima.
3. Se hai la cerchia verde (punto 2.1)
   • Se tra i singoli punti non esiste una soluzione che appartiene al cerchio verde, allora il cerchio verde è la risposta.
   • Se hai soluzioni individuali sul cerchio verde e hai bisogno di una soluzione qualsiasi, prendine solo una di quelle.
   • Se hai soluzioni individuali sul cerchio verde e hai bisogno di tutto il numero illimitato di soluzioni, allora devi risolvere un altro problema. Devi tagliare dal cerchio verde tutti gli archi definiti da una coppia di soluzioni individuali da ciascun cerchio rosso.

NB: Non sto dicendo che l'implementazione dell'algoritmo dovrebbe essere esattamente descritta. Puoi provare a migliorare le prestazioni utilizzando la programmazione dinamica o saltando le possibili soluzioni in cui è ovvio che non funzioneranno.