Punkt und ellipse (gedreht) position test: Algorithmus

Wie um zu testen, ob ein Punkt P = [xp,yp] innen/außen einige gedrehte ellipse gegeben durch das Zentrum C=[x,y], a, b und phi ( Drehwinkel)?

In diesem moment bin ich mit folgender Lösung: drehen Sie die ellipse und den Punkt durch die Winkel phi und dann der gemeinsame test für eine position von dem Punkt, und "nicht gedreht" ellipse.

Aber es gibt eine Menge der getesteten Punkte (in tausend) und ich finde diese Lösung so langsam. Ist es direkter und effizienter Weg, um eine position der gedrehten ellipse und Punkt?

Brauche ich keinen code, sondern der Algorithmus. Vielen Dank für Ihre Hilfe.

Zeigen Sie uns, was Sie bisher getan haben. Etwas, dass wir Ihnen helfen können.

InformationsquelleAutor justik | 2011-10-30

Andere Möglichkeit ist, nur werfen alles in die Gleichung für ein 2D gedrehte ellipse und sehen, ob das Ergebnis kleiner ist als eins.

Also ein Punkt im Innern der ellipse, wenn die folgende Ungleichung wahr ist

Punkt und ellipse (gedreht) position test: Algorithmus

Wobei (xp,yp) sind die Punktkoordinaten und (x0, y0) der Mittelpunkt der ellipse.

Implementiert habe ich eine kleine Mathematica Programm demonstriert, dass dies in der Tat funktioniert:
Punkt und ellipse (gedreht) position test: Algorithmus

Hier ist es in Aktion:

Punkt und ellipse (gedreht) position test: Algorithmus

Und hier ist der 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

Können Sie einfach füttern Sie Ihre Daten in die Formel oben angegeben. Hier ist eine python-Implementierung, die ich auf Ajasja Empfehlungen:

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

Thx für die Korrektur!
Verwenden Sie nicht math.pow(val, 2) zu Platz etwas. Das ist wirklich langsam. (Zuweisen an eine variable und multiplizieren Sie diese mit sich selbst).

InformationsquelleAutor Raoul

6

Umgang mit Ellipsen, die ich lieber umzuwandeln in ein anderes Koordinatensystem, wo die ellipse ist eine Einheit, Kreis zentriert am Ursprung.

Wenn Sie sehen, das die ellipse eines Einheitskreises (radius 1), skaliert durch (a,b), gedreht von phi und verwandelt durch (x,y), dann wird das Leben viel einfacher.
Wenn Sie, dass die Transformationsmatrix Sie können es verwenden, um einen einfacheren query containment. Wenn Sie transformieren der Punkt im Koordinatensystem, wo die ellipse ist eine Einheit, Kreis, alle Sie tun müssen ist, eine Punkt-in-unit-Kreis test-das ist trivial.
Wenn "transform" ist eine matrix, die es vermag, eine Einheit Kreises in die ellipse, wie beschrieben, dann
```
transformedPoint = transform.Invert().Transform(point);
pointInEllipse = transformedPoint.DistanceTo(0,0) < 1.0;
```
InformationsquelleAutor Anders Forsgren
1

Hier ist der Algorithmus, lasse ich Sie entwickeln code:
1. Bestimmen Sie den Vektor v1 zwischen dem Zentrum der ellipse und Ihren Standpunkt
2. Bestimmen Winkel a1 zwischen dem Vektor v1 und x-Achse in Weltkoordinaten
3. Subtrahieren phi von a1 bis a2 zu erhalten, unsere Vektor-Winkel-in lokalen Koordinaten
4. Bestimmen, Punkt P2 auf der ellipse in einem Winkel a2 in lokalen Koordinaten, nicht kompensiert durch (x, y)
5. Berechnen Sie L1 und L2, die Vektor-Länge von a1-und a2 -
Bewertung:
1. Wenn L1 < L2 ist der Punkt innerhalb
2. Wenn L1 = L2 (plus/minus einer kleinen Toleranz) der Punkt liegt auf der ellipse
3. Wenn L2 > L2 ist der Punkt ausserhalb
Ellipse parametrischen Formel:

x = a*cos(u)

y = b*sin(u)

gültig für u zwischen -pi und +pi. Hinzufügen phi nach u und drehen Sie Ihre ellipse.

Der obige Algorithmus kann vereinfacht und optimiert werden von ellipse Gleichungen.

Glück!

InformationsquelleAutor rjobidon
0

Matplotlib ist eine Ellipse-Methode innerhalb der patches der Klasse, der es Ihnen erlaubt, die Frage zu stellen, ob ein Punkt innerhalb oder außerhalb des patch. Überprüfen Sie hier und suchen Sie nach der Methode contains_point(). Erstellen Sie die ellipse mit dem Ellipse-Klasse, und dann, als ob es einen Punkt im inneren.
BTW, matplotlib ist ein Paket für python.

InformationsquelleAutor Jose Sergio Hleap

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.