Point et de l'ellipse (rotation) de la position d'essai: algorithme

Comment faire pour tester si un point P = [xp,yp] est à l'intérieur/à l'extérieur de certains rotation de l'ellipse donnée par le centre C=[x,y], a, b, et phi ( angle de rotation)?

En ce moment, je suis en utilisant la solution suivante: rotation de l'ellipse et de point par l'angle -phi et puis le test commun pour une position du point et de la "non tourné" ellipse.

Mais il y a beaucoup de testé points (en milliers) et je trouve cette solution plus lent. Est-il direct et de manière plus efficace pour obtenir une position de la rotation de l'ellipse et de point?

Je n'ai pas besoin d'un code, mais l'algorithme. Merci pour votre aide.

  • Montrez-nous ce que vous avez fait jusqu'à présent. Quelque chose que nous pouvons vous aider.
InformationsquelleAutor justik | 2011-10-30
  1. 27

    Une autre option est de simplement jeter le tout dans l'équation du 2D rotation de l'ellipse et de voir si le résultat est inférieur à un.

    Si un point est à l'intérieur de l'ellipse si l'inégalité suivante est vraie

    Point et de l'ellipse (rotation) de la position d'essai: algorithme

    Où (xp,yp) sont les coordonnées d'un point et (x0, y0) est le centre de l'ellipse.

    J'ai mis en place un petit Mathematica programme démontrant que cela fonctionne:
    Point et de l'ellipse (rotation) de la position d'essai: algorithme

    Ici, il est en action:

    Point et de l'ellipse (rotation) de la position d'essai: algorithme

    Et voici le code:

    ellipse[x_, y_, a_, b_, \[Alpha]_, x0_: 0, y0_: 0] := 
     (((x - x0)*Cos[\[Alpha]] + (y - y0)*Sin[\[Alpha]])/a)^2
   + (((x - x0)*Sin[\[Alpha]] - (y - y0)*Cos[\[Alpha]])/b)^2;

Manipulate[
 RegionPlot[
  ellipse[x, y, a, b, \[Alpha] \[Degree], Sequence @@ pos] < 1, {x, -5, 5}, {y, -5, 5}, 
  PlotStyle -> If[ellipse[Sequence @@ p, a, b, \[Alpha] \[Degree], Sequence @@ pos] <= 1, Orange, LightBlue], 
  PlotPoints -> 25]
{{a, 2}, 1, 5, Appearance -> "Labeled"}
{{b, 4}, 2, 5, Appearance -> "Labeled"}
{\[Alpha], 0, 180,  Appearance -> "Labeled"}
{{p, {3, 1}}, Automatic, ControlType -> Locator}
{{pos, {0, 0}}, Automatic, ControlType -> Locator}]
    InformationsquelleAutor Ajasja
  2. 10

    Vous pouvez simplement les nourrir vos données dans la formule énoncée ci-dessus. Voici un python de mise en œuvre que j'ai faite sur Ajasja recommandations:

    def pointInEllipse(x,y,xp,yp,d,D,angle):
    #tests if a point[xp,yp] is within
    #boundaries defined by the ellipse
    #of center[x,y], diameter d D, and tilted at angle

    cosa=math.cos(angle)
    sina=math.sin(angle)
    dd=d/2*d/2
    DD=D/2*D/2

    a =math.pow(cosa*(xp-x)+sina*(yp-y),2)
    b =math.pow(sina*(xp-x)-cosa*(yp-y),2)
    ellipse=(a/dd)+(b/DD)

    if ellipse <= 1:
        return True
    else:
        return False
    • Merci pour la correction!
    • N'utilisez pas de math.pow(val, 2) à carré quelque chose. C'est vraiment lent. (L'affecter à une variable et la multiplier par lui-même).
    InformationsquelleAutor Raoul
  3. 6

    De traiter avec des points de suspension, je préfère transformer en un autre système de coordonnées où l'ellipse est un cercle unité centré à l'origine.

    Si vous voyez l'ellipse comme une unité de cercle (de rayon 1), mis à l'échelle par (a,b), tourné par phi et transformé par (x,y), alors la vie devient beaucoup plus facile.
    Si vous avez cette matrice de transformation, vous pouvez l'utiliser pour faire un plus facile de confinement de la requête. Si vous transformez le point d'être dans le système de coordonnées où l'ellipse est un cercle unité, tout ce que vous avez à faire, c'est un point dans l'unité de test de cercle qui est trivial.
    Si "transformer" est une matrice qui transforme un cercle unité dans votre ellipse que décrit, puis

    transformedPoint = transform.Invert().Transform(point);
pointInEllipse = transformedPoint.DistanceTo(0,0) < 1.0;
    InformationsquelleAutor Anders Forsgren
  4. 1

    Voici l'algorithme, je vous laisse développer le code:

    1. Déterminer le vecteur v1 entre le centre de l'ellipse et de votre point
    2. Déterminer l'angle a1 entre le vecteur v1 et de l'axe x dans les coordonnées du monde
    3. Soustraire phi de a1 à obtenir a2, notre vecteur d'angle en coordonnées locales
    4. Déterminer le point P2 de l'ellipse à l'angle a2 en coordonnées locales, non compensée par (x, y)
    5. De calcul de la L1 et de la L2, la longueur du vecteur de a1 et a2

    Évaluation:

    1. Si L1 < L2 le point est à l'intérieur de
    2. Si L1 = L2 (plus/moins une petite tolérance) le point est sur l'ellipse
    3. Si L2 > L2 le point est à l'extérieur

    Ellipse paramétrique formule:

    x = a*cos(u)

    y = b*sin(u)

    valable pour u entre-pi et +pi. Ajouter phi à u pour faire pivoter votre ellipse.

    L'algorithme ci-dessus peut être simplifiée et optimisée de l'ellipse équations.

    Bonne chance!

    InformationsquelleAutor rjobidon
  5. 0

    Matplotlib est une Ellipse de la méthode dans les patchs de classe, qui vous permet de vous poser la question de savoir si un point est à l'intérieur ou à l'extérieur de la pièce. Vérifier ici et de regarder pour la méthode contains_point(). Vous aurez besoin de créer de l'ellipse avec l'Ellipse de la classe, et puis comme si il ya un point à l'intérieur.
    BTW, matplotlib est un package python.

    InformationsquelleAutor Jose Sergio Hleap