Quelle est la méthode la plus efficace pour calculer les intersections de deux cercles?

Question

J'essaie de trouver le moyen le plus rapide et le plus simple dans un programme C# de calculer les intersections de deux cercles. D'après ce que je peux dire il y a deux méthodes possibles, et vous devrez me pardonner de ne pas connaître les noms officiels pour eux.

Nous supposons que vous connaissez les points centraux des deux cercles et leurs rayons exacts, à partir desquels vous pouvez calculer la distance entre eux, tout ce qui manque est le (s) point (s) d'intersection. Ceci se déroule sur une parcelle x-y standard.

Le premier est un type de méthode de substitution telle que celle décrite here où l'on combine les deux formules de cercle et d'isoler soit x ou y, puis le sous-le dans une formule originale pour aboutir à une équation du second degré qui peut être résolu pour deux (ou éventuellement une ou aucune) coordonnées pour un axe, ce qui vous permet ensuite de trouver les coordonnées correspondantes sur l'autre axe. La seconde à laquelle j'ai vu une référence est l'utilisation d'une méthode de loi des cosinus pour déterminer les angles, ce qui permettrait ensuite de tracer une ligne pour chaque côté de la grille, et mettre dans votre rayon pour trouver le point d'intersection réel .

J'ai écrit les étapes pour la première méthode, et cela semble plutôt long. La seconde va prendre quelques recherches/apprendre à écrire mais semble plus simple. Ce que je n'ai jamais fait, c'est traduire des processus comme celui-ci en code, donc je ne sais pas finalement lequel sera le plus facile pour cette application. Quelqu'un a-t-il des conseils à ce sujet? Ou est-ce que je vais peut-être aller dans le mauvais sens? Y a-t-il déjà une bibliothèque que je peux utiliser pour réinventer la roue?

Quelque contexte: Je suis principalement préoccupé par le coût pour le CPU pour faire ces calculs. Je prévois sur l'application faire un bon nombre d'entre eux à la fois, à plusieurs reprises, d'où la raison pour laquelle je veux le moyen le plus simple pour l'accomplir.

Answer 1

La géométrie de calcul est presque toujours une douleur à mettre en œuvre. C'est aussi presque toujours un processeur intensif. Cela dit, ce problème n'est que de l'algèbre si vous le configurez correctement.

Calculez d = hypot(x2-x1, y2-y1), la distance entre les deux centres. Si r1 + r2 < d, il n'y a pas d'intersection. Si r1+r2 == d, l'intersection est à (x1, y1) + r1/(r1+r2) * (x2-x1,y2-y1). Si d < abs(r1-r2), un cercle est contenu dans l'autre et il n'y a pas d'intersection. Vous pouvez déterminer le cas où les deux cercles sont tangents et l'un est contenu dans l'autre. Je ne traiterai que le cas restant.

Vous voulez trouver des distances h orthogonales à (x2-x1,y2-y1) et p parallèle à (x2-x1,y2-y1) de telle sorte que p^2 + h^2 = r1^2 et (d-p)^2 + h^2 = r2^2. Soustrayez les deux équations pour obtenir une équation linéaire en p: d^2-2dp = r2^2-r1^2. Résolvez cette équation linéaire pour p. Puis h = sqrt(r1^2 - p^2).

Les coordonnées des deux points sont (x1,y1) + p (x2-x1,y2-y1)/d +/- h (y2-y1, x1-x2)/d. Si vous travaillez à travers la dérivation ci-dessus et résolvez pour p/d et h/d à la place, vous pouvez obtenir quelque chose qui fait moins d'opérations.