Trouver le meilleur ajustement le plus proche pour le cercle

Voici un exemple d'image, si j'ai un point du point blanc au milieu et que je veux trouver l'emplacement le plus proche possible pour le cercle bleu (qui est évidemment à l'endroit où je l'ai placé) si tous les cercles rouges existent déjà . Comment puis-je trouver cet emplacement?

La performance pour moi n'est pas une préoccupation majeure pour cette application.

Ce n'est pas une solution générale, car il existe plusieurs situations où il ne fournira pas la position du cercle bleu avec la distance la plus courte au point blanc. Par exemple, si vous avez 100 boules rouges regroupées et que le point blanc est loin de ce groupe de boules rouges, aucune des boules rouges n'aura aucune influence sur la position du cercle bleu qui peut simplement être centré sur le point blanc . Il ne montrera pas non plus tous les détails des calculs. Quoi qu'il en soit, pour un sous-ensemble de configurations, où la solution (cercle bleu) est tangente à deux cercles rouges, ce qui suit devrait fonctionner:
1) soit R le rayon du cercle bleu
2) faire une boucle sur toutes les paires de cercles rouges, oui Je sais que c'est O (n2).
3) pour chaque paire de cercles i, j de centre en (xi, yi) et (xj, yj) de rayon respectif ri et rj, calculer le carré de la distance entre la paire de cercles

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

4) mettez toutes les paires de cercles

dij^2<R^2

dans une liste.

5) parcourir la liste, trouver les 2 solutions de cercles de rayon R tangents aux deux cercles i et j. Pour ce faire, utilisez ces équations avec cette image

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

avec les informations ci-dessus, vous pouvez trouver (X1ij, Y1ij) et (X2ij, Y2ij) les centres des 2 cercles tangents aux cercles i et j. Pour chaque cercle bleu candidat, faites une boucle sur tous les autres cercles rouges et voyez s'il ne se chevauche pas. S'ils le jettent sinon vérifier la distance au cercle blanc. Si vous gardez celui avec une distance plus petite, je pense que vous aurez la solution lorsque vous aurez fini de parcourir la liste des paires de cercles. L'algorithme ressemble à O (n3).

Le placement le plus proche du point sera soit sur le point, soit en touchant un cercle.

par conséquent, vérifiez d'abord le point, puis faites rouler le nouveau cercle autour du bord de chaque cercle existant, calculez la distance à partir du point et si vous vous chevauchez au fur et à mesure et gardez une trace du point de distance minimale. Arrêtez-vous lorsque vous avez traversé chaque cercle.

c'est à dire. vérifiez tous les points sur les lignes vertes, plus le cercle blanc. où la ligne verte est un cercle de rayon rouge plus bleu

vous devez vérifier l'ensemble de la ligne verte, pas seulement les intersections, afin de couvrir ces cas de bord.

De toute évidence, la taille du pas de votre parcours va être importante en termes de performances. Mais comme vous déclarez que les performances ne sont pas un problème, choisissez la valeur correspondant à la résolution de votre valeur de sortie. c'est à dire flotter, longtemps?

clarification:

ma suggestion est de forcer brutalement tous les points autour de chaque cercle pour tester le chevauchement avec tous les autres cercles à chaque point. aucune intelligence.

Si l'exemple d'image est indicatif du nombre de cercles et de la résolution, cela ne devrait pas être un problème pour un PC standard

nous avons 20 cercles de rayon moyen 200, donc environ 20 * 2 π * 200 points * 20 tests d'intersection = 4800000 itérations

Remarque:

Les approches itératives comme celle-ci sont imparfaites en ce que la taille de votre pas, dans ce cas la résolution de votre sortie, peut grandement affecter le résultat.

Disons que j'ai deux cercles rouges distants de 2 pixels et un cercle bleu d'un rayon de 1 pixel à serrer entre eux. Clairement, avec l'un des deux pixels comme centre du cercle bleu, il chevauchera l'un des rouges. mais évidemment, il y a de la place pour le cercle si le centre se situe entre les deux pixels.

D'où mon commentaire concernant la résolution de la sortie. que vous avez dit pourrait être n'importe quoi.

vous pouvez également résoudre l'équation simultanée pour chaque paire de cercles avec une augmentation de rayon par le rayon du cercle bleu.

cela vous donnera les points où le cercle bleu touchera les deux cercles rouges plus précisément que l'itération.

Pourtant. il y a plusieurs conditions où si vous ne faites que cela, vous obtenez une mauvaise ou aucune réponse. c'est à dire.

1 ou aucun cercle

2 cercles ou plus mais avec un point cible loin et en dehors d'eux.

de nombreux cercles mais avec un point cible proche de la surface

Ce plunk contient du code de travail,

Concept

Les cercles donnés sont C1, C2 .... Cn

et les coordonnées du cercle Cn sont Cnx, Cny et le rayon est Cr

et le rayon du cercle requis est R

si le cercle bleu est à X, Y et s'il n'entre pas en conflit avec d'autres cercles, les équations suivantes sont vraies

(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

changer la première équation,

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

de sorte que les équations peuvent réécrire comme,

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

la mise en oeuvre

partir de la coordonnée du point blanc (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 première coordonnée trouvée pour satisfaire toutes les équations est l'emplacement du cercle bleu

• O étant le point que vous essayez d'être proche
• P étant le point que vous recherchez (le centre du cercle bleu
• r étant le rayon du cercle bleu
• C0 .. Cn étant les centres de tous les cercles qui restreignent le placement du bleu sur

• le cercle étendu est l'un des cercles avec son rayon étendu par r

  Il y a du travail supplémentaire si O n'est pas au centre d'un cercle. Supposons donc maintenant O == C0

Calculez toutes les intersections de tous les cercles avec C0, en utilisant leurs rayons respectifs plus les r , c'est-à-dire coupez les cercles étendus avec C0 étendu. S'il n'y a pas d'intersections, le point que vous recherchez se trouve n'importe où sur C0, s'il y a des intersections, pour chaque intersection, vérifiez s'il se trouve à l'intérieur d'un autre cercle étendu (vous pouvez vous limiter aux cercles qui avaient des intersections avec C0). Prenez la première intersection qui n'est pas dans un autre cercle étendu comme P, il pourrait y en avoir d'autres.

S'il n'y a pas d'intersections entre les cercles étendus et C0 qui ne se trouvent pas à l'intérieur d'un autre cercle étendu, calculez les intersections de tous les cercles étendus entre eux. Ensuite, vérifiez ces intersections par ordre de distance à O, encore une fois si l'une des intersections se trouve dans un autre cercle étendu, si oui, jetez-le, si non, c'est votre résultat.

Si vous envisagez cela, imaginez dessiner une ligne autour de tous les cercles qui indiquent un emplacement possible pour votre cercle bleu, en prenant l'union de tous les cercles étendus indiquera la zone que votre cercle bleu ne peut pas être. Le point que vous recherchez est le point le plus proche qui n'est pas dans cette union. S'il y a un point sur C0 qui n'est pas dans cette union qui est la solution, si C0 est entièrement couvert, alors P doit être sur une intersection entre deux autres cercles étendus, et il doit être dans une zone qui n'est pas couverte par cette union (c'est-à-dire pas dans un cercle étendu ).

Ceci est O (n ^ 2), il y a quelques façons d'améliorer cela cependant, une grille peut être utilisée pour réduire l'effort de la recherche par paire, je pense aussi que trier les cercles par leur proximité à O, (la distance entre le deux cercles réduits par la radio) aideraient à limiter l'espace de recherche pour la couverture et la recherche d'intersection

Solutions possibles lookup

1. Vérifiez si le point blanc est la solution en soi. Il couvre le cas avec 0 cercles rouges et le cas trivial lorsque les cercles rouges sont loin du point blanc.
2. Un cercle rouge.
   1. Le point blanc est le centre du cercle. Les solutions possibles sont un nombre infini de points sur le cercle avec son centre dans le point blanc et le rayon étant la somme du rayon des cercles bleus et du diamètre du cercle rouge. Appelons cela le cercle vert .
   2. Le point blanc est ailleurs. Il n'y a qu'une seule solution possible sur la ligne qui relie le point blanc et le centre du cercle rouge, c'est le rayon du cercle bleu loin du point où le cercle rouge traverse la ligne vers le point blanc.
3. Deux ou plusieurs cercles rouges.
   1. Prenons les cercles rouges un par un et cherchons une solution possible pour chacun d'eux individuellement selon le point 2 (un cercle).
   2. Pour chaque paire de cercles rouges, vérifions si vous pouvez dessiner le cercle bleu en touchant les deux rouges. C'est-à-dire si la distance entre leurs centres est égale ou inférieure à la somme de leurs rayons plus le diamètre du cercle bleu. Si vous le pouvez, vous avez deux (ou une si les cercles rouges sont exactement à un diamètre de cercle bleu) des solutions possibles .

Recherche de solution réelle parmi les solutions possibles

Vous avez maintenant un ensemble de points qui sont des solutions possibles , parcourez-les et vérifiez chacun.

1. Si le point est en fait une solution. Aucun cercle rouge ne doit avoir son centre plus proche que son rayon jusqu'à ce point.
2. S'il est plus proche du point blanc que la solution trouvée auparavant.
3. Si vous avez le cercle vert (point 2.1)
   • Si parmi les points individuels il n'y a pas de solution qui appartient au cercle vert, alors le cercle vert est la réponse.
   • Si vous avez des solutions individuelles sur le cercle vert et que vous avez besoin de n'importe quelle solution, prenez-en une.
   • Si vous avez des solutions individuelles sur le cercle vert et que vous avez besoin de tout le nombre illimité de solutions, vous devez résoudre un autre problème. Vous devez couper du cercle vert tous les arcs définis par une paire de solutions individuelles de chaque cercle rouge.

NB: Je ne dis pas que l'implémentation de l'algorithme doit être exactement décrite. Vous pouvez essayer d'améliorer les performances à l'aide de la programmation dynamique ou d'ignorer les solutions possibles lorsqu'il est évident qu'elles ne fonctionneront pas.