Comment détecter si une ellipse coupe(entre en collision avec) un cercle de

Réponse courte: Résoudre exactement pour savoir si les deux objets se croisent est assez compliqué d'être infaisable pour le but de la détection de collision. Discrétiser votre ellipse comme un n-sided polygone pour n (selon le degré de précision que vous devez être) et de faire de la détection de collision avec ce polygone.

Réponse longue: Si vous insistez pour déterminer si la douceur de l'ellipse et le cercle se croisent, il y a deux approches principales. Les deux impliquent la résolution de la première pour les le point le plus proche vers le centre du cercle à l'ellipse, puis en comparant la distance sur le cercle de rayon.

Approche 1: Utiliser un paramétrage de l'ellipse. Transformer vos coordonnées afin que l'ellipse est à l'origine, avec ses axes alignés pour les axes x-y. Qui est:

• Centre de l'ellipse: (0,0)
• Centre du cercle: c = (cx, cy)
• Rayon du cercle: r
• Rayon de x aligné à l'axe de l'ellipse: un
• Rayon de y aligné à l'axe de l'ellipse: b.

L'équation de l'ellipse est alors donnée par a cos(t), b sin(t). Pour trouver le point le plus proche, nous voulons minimiser le carré de la distance
|| (a cos t, b sin t) - c ||^2. Comme Jean le souligne, c'est "juste calcul": prendre un dérivé, et définissez égal à 0. À moins que je me manque quelque chose, cependant, la résolution de l'résultant (très méchant) l'équation pour t n'est pas possible analytiquement, et doit être approchée en utilisant par exemple la Méthode de Newton.
Branchez le t vous trouvez dans l'équation paramétrique pour obtenir le point le plus proche.

• Pro: Numérique résoudre est seulement dans une variable, t.
• Con: Vous devez être en mesure d'écrire une paramétrisation de l'ellipse, de transformation ou de coordonnées, de sorte que vous pouvez. Cela ne devrait pas être trop difficile pour tout être raisonnable représentation que vous avez de l'ellipse. Cependant, je vais vous montrer une deuxième méthode, qui est beaucoup plus générale et peut être utile si vous avez de généraliser votre problème, disons, 3D.

Approche 2: Utilisation multidimensionnelle de calcul. Pas de changement de coordonnées est nécessaire.

• Centre du cercle: c = (cx, cy)
• Rayon de cirlce: r
• Ellipse est donnée par g(x, y) = 0 pour une fonction g. Par exemple, pour le lait Caillé est la réponse, vous pouvez utiliser g(x,y) = distance de (x,y) de l'objectif 1 + distance de (x,y) de l'axe 2 - e.

Trouver le point sur l'ellipse la plus proche du centre de le cercle peut alors être formulé comme un contrainte du problème de minimisation:

Minimize ||(x,y) - c||^2 subject to g(x,y) = 0

(Minimisation du carré de la distance est équivalente à la minimisation de la distance, et beaucoup plus agréable à aborder car c'est un polynôme quadratique en x,y.)

Pour résoudre la contrainte du problème de minimisation, nous introduisons des multiplicateurs de Lagrange lambda, et de résoudre le système d'équations

2 * [ (x,y) -c ] + lambda * Jg(x,y) = 0
g(x,y) = 0

Ici Jg est le gradient de g. C'est un système de trois (non-linéaire) équations à trois inconnues: x, y, et lambda. On peut résoudre ce système à l'aide de la Méthode de Newton, et l' (x,y) on en est au point le plus proche vers le centre du cercle.

• Pro: Pas de paramétrage doit être trouvé
• Pro: Méthode est très générale, et fonctionne bien, chaque fois que l'écriture de g est plus facile que de trouver une équation paramétrique (comme en 3D)
• Con: Nécessite un multivariable Newton résoudre, ce qui est très poilu si vous n'avez pas accès à une méthode numérique paquet.

Mise en garde: ces deux approches techniquement résoudre pour le point qui extremizes la distance vers le centre du cercle. Ainsi, le point peut-être le point le plus éloigné du cercle, et pas le plus proche. Pour les deux méthodes, l'ensemencement de votre aide pour régler une bonne estimation initiale (le centre du cercle fonctionne bien pour la Méthode 2; vous êtes sur votre propre pour la Méthode 1) permettra de réduire ce danger.

Potentiel Troisième Approche?: Il peut être possible de résoudre directement les racines de la système de deux équations quadratiques à deux variables représentant le cercle et de l'ellipse. Si une racine réelle existe, les objets se croisent. La façon la plus directe de la résolution de ce système, de nouveau à l'aide d'un algorithme numérique, comme la Méthode de Newton, n'aidera pas car le manque de convergence n'est pas nécessaire implique la non-existence d'une racine réelle. Pour les deux équations quadratiques à deux variables, cependant, il peut exister une méthode spécialisée qui est garanti de trouver de vraies racines, si elles existent. Moi je ne peux pas penser à une façon de le faire, mais vous souhaitez peut-être à la recherche de vous-même (ou voir si quelqu'un sur stackoverflow peut élaborer.)

OriginalL'auteur user168715

Agrandir l'ellipse de la majeure et la mineure rayons par le rayon du cercle. Puis tester si le centre du cercle est à l'intérieur de cette nouvelle grande ellipse en faisant la somme des distances aux foyers de la grande ellipse.

Cet algorithme est très efficace. Vous pouvez précoce-si le cercle n'a pas d'intersection d'un cercle qui circonscrit l'ellipse. C'est plus lent que d'une boîte englobante de test, mais la recherche de la boîte englobante d'un non-axe aligné ellipse est délicate.

OriginalL'auteur Danny Epstein

si un cercle et une ellipse entrent en collision, puis de leurs frontières se croisent 1, 2, 3, ou 4 fois(ou infiniment nombreuses dans le cas d'une circulaire de l'ellipse, qui coïncide avec le cercle), ou le cercle est à l'intérieur de l'ellipse ou vice versa.

Je suis en supposant que le cercle a une équation de (x - a)^2 + (y - b)^2 <= r^2 (1) et l'ellipse a une équation de [(x - c)^2]/[d^2] + [(y - e)^2]/[f^2] <= 1 (2)

Pour vérifier si l'un d'entre eux est à l'intérieur de l'autre, vous pouvez évaluer l'équation du cercle au les coordonnées du centre de l'ellipse(x=c, y=e), ou vice-versa, et de voir si l'inégalité est vraie.

de vérifier les autres cas dans lesquels leurs limites se croisent, vous avez pour vérifier si le système d'équations décrit par (1) et (2) n'ont pas de solutions.

vous pouvez le faire en ajoutant (1) et (2), vous donnant

(x - a)^2 + (y - b)^2 + [(x - c)^2]/[d^2] + [(y - e)^2]/[f^2] = r^2 + 1

ensuite, vous multipliez les termes, en donnant

x^2 - 2ax + a^2 + y^2 - 2by + b^2 + x^2/d^2 - 2cx/d^2 + c^2/d^2 + y^2/f^2 - 2ey/f^2 + e^2/f^2 = r^2 + 1

collectionner comme les termes, nous obtenons

(1 + 1/d^2)x^2 - (2a + 2c/d^2)x + (1 + 1/f^2)y^2 - (2b + 2e/f^2)y = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

maintenant, laissez - m = (1 + 1/d^2), n = -(2a + 2c/d^2), o = (1 + 1/f^2), and p = -(2b + 2e/f^2)

l'équation est maintenant mx^2 + nx + oy^2 + py = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

maintenant nous avons besoin de compléter les cases sur le côté gauche de la

m[x^2 + (n/m)x] + o[y^2 + (p/o)y] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

m[x^2 + (n/m)x + (n/2m)^2 - (n/2m)^2] + o[y^2 + (p/o)y + (p/2o)^2 - (p/2o)^2] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

m[(x + n/2m)^2 - (n/2m)^2] + o[(y + p/2o)^2 - (p/2o)^2] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

m(x + n/2m)^2 - m(n/2m)^2 + o(y + p/2o)^2 - o(p/2o)^2 = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

m(x + n/2m)^2 + o(y + p/2o)^2 = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 + m(n/2m)^2 + o(p/2o)^2

ce système a une solution iff 11 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 + m(n/2m)^2 + o(p/2o)^2 >= 0

Là vous l'avez, si je n'ai pas fait d'erreurs algébriques. Je ne sais pas combien vous pouvez vous simplifier l'expression qui en résulte, donc, cette solution peut être très gourmand en ressources, si vous allez vérifier de nombreux cercles/ellipses

OriginalL'auteur Bwmat

Ce n'est pas compliqué. user168715 la réponse est généralement droit, mais en faisant le calcul n'est pas nécessaire. Juste de la trigonométrie.

Trouver l'angle entre le centre des deux objets. En utilisant cela, vous pouvez trouver le point le plus proche vers le centre du cercle à l'ellipse à l'aide de la polaire-forme:

(Prises à partir de l'article de Wikipedia sur Ellipses)

Maintenant comparer la distance entre l'objet de deux centres, en soustrayant l'ellipse rayon et le rayon du cercle.

Peut-être que je suis absent quelque chose; peut-être ArcTan/Cos/Sin sont lents, mais je ne le pense pas, et il doit être rapide-approximations si nécessaire.

OriginalL'auteur phillipwei

En supposant:
l'ellipse centrée à l'origine et avec le demi-grand
de l'axe (de longueur) orientés le long de l'axe des x, et avec un semi-mineur
l'axe de la longueur de b; E2 est l'excentricité au carré, c'est à dire (una-bb)/(a*a);
le cercle est centré en X,Y et de rayon r.

Le cas faciles sont:
le centre du cercle est à l'intérieur de l'ellipse (c'est à dire hypot(X/a, Y/b) <= 1)
il y a donc une intersection;
le centre du cercle est à l'extérieur d'un cercle centré en 0 de rayon a+r
(c'est à dire hypot(X,Y) > a+r) donc il n'y a pas une intersection.

Une approche pour les autres cas, c'est pour calculer la géodésique
coordonnées (latitude, hauteur) du centre du cercle. Le cercle
coupe l'ellipse si et seulement si la hauteur est inférieure au rayon de.

Les géodésiques de la latitude d'un point sur une ellipse est l'angle
la normale à l'ellipse au point avec l'axe des x, et
la hauteur d'un point à l'extérieur de l'ellipse est la distance de la
point du point sur l'ellipse la plus proche. Remarque la latitude géodésique est pas le même que l'angle polaire de l'ellipse de centre le point, à moins que le
l'ellipse est en fait circulaire.

Dans les formules de conversion de coordonnées géodésiques lat,ht à
coordonnées cartésiennes X,Y est
X = (nu+ht)*cos(lat), Y = (nu * (1-E2) + ht)*sin(lat)
où nu = a/sqrt( 1 - E2*sin(lat)sin(lat)).
Le point sur l'ellipse la plus proche de X,Y) est le point de
avec la même latitude, mais la hauteur nulle, c'est à dire x = nucos(lat),
y = nu * (1-E2) * sin(lat).
Notez que nu est une fonction de la latitude.

Malheureusement, le processus de recherche lat,ht à partir de X,Y est un
itératif. Une approche consiste d'abord à trouver la latitude, puis
la hauteur.

Un peu d'algèbre montre que la latitude est satisfait
lat = atan2( Y+ E2*nusin(lat), X)
qui peut être utilisé pour calculer des approximations successives de la latitude,
départ au lat = atan2( Y, X(1.0-E2)), ou (plus efficace) peut être
résolu en utilisant la méthode de newton.

La plus grande E2 est, c'est à dire le flatter l'ellipse est, le plus
itérations seront nécessaires. Par exemple, si l'ellipse est presque
circulaire (disons E2<0.1), puis cinq itérations obtiendrez x,y ci-dessous
à l'intérieur d'un*1e-12, mais si l'ellipse est très plat, par exemple, E2=0.999
vous aurez besoin d'environ 300 itérations pour obtenir la même précision!

Enfin, compte tenu de la latitude, la hauteur peut être calculée
par le calcul de (x,y):
x = nucos(lat), y = nu(1-E2)*sin(lat)
et alors h est la distance de x,y du centre du cercle,
h = hypot( X-x, Y-Y)

OriginalL'auteur dmuir