Abstand vom gegebenen Punkt zur gegebenen ellipse

Ich habe eine ellipse, definiert durch Mittelpunkt, radiusX und radiusY, und ich habe einen Punkt. Ich möchte finden den Punkt auf der ellipse, die am nächsten zu den gegebenen Punkt. In der Abbildung unten, das wäre S1.

Nun ich habe schon code, aber es ist ein logischer Fehler irgendwo, und ich scheinen nicht in der Lage sein, um es zu finden. Ich brach das problem auf die folgende code-Beispiel:

#include <vector>
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <math.h>

using namespace std;

void dostuff();

int main()
{
    dostuff();
    return 0;
}

typedef std::vector<cv::Point> vectorOfCvPoints;

void dostuff()
{

    const double ellipseCenterX = 250;
    const double ellipseCenterY = 250;
    const double ellipseRadiusX = 150;
    const double ellipseRadiusY = 100;

    vectorOfCvPoints datapoints;

    for (int i = 0; i < 360; i+=5)
    {
        double angle = i / 180.0 * CV_PI;
        double x = ellipseRadiusX * cos(angle);
        double y = ellipseRadiusY * sin(angle);
        x *= 1.4;
        y *= 1.4;
        x += ellipseCenterX;
        y += ellipseCenterY;
        datapoints.push_back(cv::Point(x,y));
    }

    cv::Mat drawing = cv::Mat::zeros( 500, 500, CV_8UC1 );

    for (int i = 0; i < datapoints.size(); i++)
    {
        const cv::Point & curPoint = datapoints[i];
        const double curPointX = curPoint.x;
        const double curPointY = curPoint.y * -1; //transform from image coordinates to geometric coordinates

        double angleToEllipseCenter = atan2(curPointY - ellipseCenterY * -1, curPointX - ellipseCenterX); //ellipseCenterY * -1 for transformation to geometric coords (from image coords)

        double nearestEllipseX = ellipseCenterX + ellipseRadiusX * cos(angleToEllipseCenter);
        double nearestEllipseY = ellipseCenterY * -1 + ellipseRadiusY * sin(angleToEllipseCenter); //ellipseCenterY * -1 for transformation to geometric coords (from image coords)


        cv::Point center(ellipseCenterX, ellipseCenterY);
        cv::Size axes(ellipseRadiusX, ellipseRadiusY);
        cv::ellipse(drawing, center, axes, 0, 0, 360, cv::Scalar(255));
        cv::line(drawing, curPoint, cv::Point(nearestEllipseX,nearestEllipseY*-1), cv::Scalar(180));

    }
    cv::namedWindow( "ellipse", CV_WINDOW_AUTOSIZE );
    cv::imshow( "ellipse", drawing );
    cv::waitKey(0);
}

Es ergibt sich folgende Bild:

Abstand vom gegebenen Punkt zur gegebenen ellipse

Können Sie sehen, dass es tatsächlich findet "in der Nähe" der Punkte auf der ellipse, aber es sind nicht die "nächste" Punkte. Was ich bewusst will, ist diese: (entschuldigt meine schlechte Zeichnung)

Abstand vom gegebenen Punkt zur gegebenen ellipse

würden Sie, soweit Sie die Zeilen in dem letzten Bild, Sie würde durch die Mitte der ellipse, aber dies ist nicht der Fall für die Linien in der vorherigen Abbildung.

Ich hoffe, Sie bekommen das Bild. Kann mir jemand sagen was ich falsch mache?

es wird einfacher sein, wenn Sie nur beschreiben, Ihre Methode für die Suche nach dem Punkt, als der eigentliche code

InformationsquelleAutor user2950911 | 2014-04-09

c++ellipse math opencv

23

Betrachten einen umgebenden Kreis um den gegebenen Punkt (c, d), die Pässe, über den nächsten Punkt auf der ellipse. Aus dem Diagramm ist es klar, dass der nächste Punkt ist, so dass eine Linie zum angegebenen Punkt muss senkrecht auf der gemeinsamen Tangente der ellipse und Kreis. Andere Punkte außerhalb des Kreises und so muss weiter Weg von dem gegebenen Punkt.

Also den Punkt, den Sie suchen, ist nicht der Schnittpunkt zwischen der Linie und der ellipse, der Punkt (x, y) im Diagramm.

Steigung der Tangente:

Steigung von Zeile:

Bedingung für perpedicular Linien - Produkt der Steigungen = -1:

Wenn neu angeordnet und ersetzt, in die Gleichung der ellipse...

...diese zwei fiesen quartic (4. Grad-Polynom-Gleichungen im Sinne von entweder x oder y. AFAIK gibt es keine Allgemeinen analytische (exakte algebraische) Methoden, Sie zu lösen. Sie könnten versuchen, eine iterative Methode - look-up-die Newton-Raphson iterativen root-finding-Algorithmus.

Werfen Sie einen Blick auf diese sehr gute Arbeit über das Thema:
http://www.spaceroots.org/documents/distance/distance-to-ellipse.pdf

Sorry für die unvollständige Antwort - ich völlig die Schuld in die Gesetze der Mathematik und der Natur...

EDIT: UPS, ich scheine a und b falsch herum in das Diagramm xD
- Hölle, Sie haben Recht. Das löst das problem meiner fehlerhaften Umsetzung wird nicht durch das finden der Fehler, sondern daß meine Vorgehensweise als fehlerhaft in den ersten Platz. Dank
- Gerne helfen
- würde Folgendes auch funktionieren? Erstellen einer Transformationsmatrix, die Skalen der ellipse zu einem Kreis, während das Zentrum das gleiche. Anwendung der Transformationsmatrix auf den Punkt p1. Berechnen Sie den Schnittpunkt s1 der Punkt, um den Mittelpunkt des Kreises. Die Umwandlung p1 und s1 zurück und die Berechnung Ihrer Entfernung.
- Ich mag Ihr denken, aber Nein. Die Transformationsmatrix, die Sie denken, ist eine Skalierung der matrix, die eine lineare transformation. Für einen Kreis, der nächste Punkt wäre in der Tat der Kreuzung nahm er an - aber wenn die inverse transformation angewendet wird, werden alle Punkte auf dieser Linie würde skaliert werden, um den gleichen Betrag führt zu der falschen Antwort, die er erhielt auch.
- Quartic Polynome haben exakte Lösungen (Sie sind im höchsten Grad zu haben, siehe Galois-Theorie). Sie sind nicht trivial, obwohl, so könnte es eine Untersuchung Wert, wenn die polynomial reduzierbar.
- du hast Recht, aber wenn man das tut, ist nicht Wert, den Rechenaufwand im Vergleich zu iterativen Annäherung
InformationsquelleAutor
5

Gibt es eine relativ einfache numerische Methode, mit der eine bessere Konvergenz als die Newton-Methode. Ich habe einen blog-Beitrag darüber, warum es funktioniert http://wet-robots.ghost.io/simple-method-for-distance-to-ellipse/

Diese Implementierung funktioniert, ohne trigonometrische Funktionen:
```
def solve(semi_major, semi_minor, p):  
    px = abs(p[0])
    py = abs(p[1])

    tx = 0.707
    ty = 0.707

    a = semi_major
    b = semi_minor

    for x in range(0, 3):
        x = a * tx
        y = b * ty

        ex = (a*a - b*b) * tx**3 / a
        ey = (b*b - a*a) * ty**3 / b

        rx = x - ex
        ry = y - ey

        qx = px - ex
        qy = py - ey

        r = math.hypot(ry, rx)
        q = math.hypot(qy, qx)

        tx = min(1, max(0, (qx * r / q + ex) / a))
        ty = min(1, max(0, (qy * r / q + ey) / b))
        t = math.hypot(ty, tx)
        tx /= t 
        ty /= t 

    return (math.copysign(a * tx, p[0]), math.copysign(b * ty, p[1]))
```
Kredit Adrian Stephens für die Trig-Free-Optimierung.
- Dieser Ansatz ist hervorragend. Eine Optimierung vorgenommen werden kann, die vollständig vermieden werden trigonometrische Funktionen (alle Kredit, um das Problem auf der github-repo für dieses blog post: github.com/0xfaded/ellipse_demo/issues/1 ). Ich machte eine Implementierung, die verwendet diese Optimierung in C# für Unity3D: gist.github.com/JohannesMP/777bdc8e84df6ddfeaa4f0ddb1c7adb3
- Code scheint nicht vollständig zu sein, nach deinem edit. E. g. tx ist nicht definiert, die vor dem ersten Einsatz.
- Whoops, wusste nicht, kopieren Sie die Optimierung korrekt. Vielen Dank für die überprüfung @JHBonarius
InformationsquelleAutor user364952

Hier ist der code übersetzt, in C# implementiert, aus diesem Papier zu lösen, für die ellipse:
http://www.geometrictools.com/Documentation/DistancePointEllipseEllipsoid.pdf

Beachten Sie, dass dieser code ist ungetestet - wenn Sie einen Fehler finden lasst es mich wissen.

    //Pseudocode for robustly computing the closest ellipse point and distance to a query point. It
    //is required that e0 >= e1 > 0, y0 >= 0, and y1 >= 0.
    //e0,e1 = ellipse dimension 0 and 1, where 0 is greater and both are positive.
    //y0,y1 = initial point on ellipse axis (center of ellipse is 0,0)
    //x0,x1 = intersection point

    double GetRoot ( double r0 , double z0 , double z1 , double g )
    {
        double n0 = r0*z0;
        double s0 = z1 - 1; 
        double s1 = ( g < 0 ? 0 : Math.Sqrt(n0*n0+z1*z1) - 1 ) ;
        double s = 0;
        for ( int i = 0; i < maxIter; ++i ){
            s = ( s0 + s1 ) / 2 ;
            if ( s == s0 || s == s1 ) {break; }
            double ratio0 = n0 /( s + r0 );
            double ratio1 = z1 /( s + 1 );
            g = ratio0*ratio0 + ratio1*ratio1 - 1 ;
            if (g > 0) {s0 = s;} else if (g < 0) {s1 = s ;} else {break ;}
        }
        return s;
    }
    double DistancePointEllipse( double e0 , double e1 , double y0 , double y1 , out double x0 , out double x1)
    {
        double distance;
        if ( y1 > 0){
            if ( y0 > 0){
                double z0 = y0 / e0; 
                double z1 = y1 / e1; 
                double g = z0*z0+z1*z1 - 1;
                if ( g != 0){
                    double r0 = (e0/e1)*(e0/e1);
                    double sbar = GetRoot(r0 , z0 , z1 , g);
                    x0 = r0 * y0 /( sbar + r0 );
                    x1 = y1 /( sbar + 1 );
                    distance = Math.Sqrt( (x0-y0)*(x0-y0) + (x1-y1)*(x1-y1) );
                    }else{
                        x0 = y0; 
                        x1 = y1;
                        distance = 0;
                    }
                }
                else //y0 == 0
                    x0 = 0 ; x1 = e1 ; distance = Math.Abs( y1 - e1 );
        }else{ //y1 == 0
            double numer0 = e0*y0 , denom0 = e0*e0 - e1*e1;
            if ( numer0 < denom0 ){
                    double xde0 = numer0/denom0;
                    x0 = e0*xde0 ; x1 = e1*Math.Sqrt(1 - xde0*xde0 );
                    distance = Math.Sqrt( (x0-y0)*(x0-y0) + x1*x1 );
                }else{
                    x0 = e0; 
                    x1 = 0; 
                    distance = Math.Abs( y0 - e0 );
            }
        }
        return distance;
    }

InformationsquelleAutor johnml1135

Den folgenden python-code implementiert die Gleichungen beschrieben unter "Abstand von einem Punkt zu einer Ellipse" und verwendet die newtonsche Methode, um die Wurzeln und damit den nächsten Punkt auf der ellipse zum Punkt.

Leider, wie Sie sehen können aus dem Beispiel, es scheint nur genau außerhalb der ellipse. Innerhalb der ellipse seltsame Dinge passieren.

from math import sin, cos, atan2, pi, fabs


def ellipe_tan_dot(rx, ry, px, py, theta):
    '''Dot product of the equation of the line formed by the point
    with another point on the ellipse's boundary and the tangent of the ellipse
    at that point on the boundary.
    '''
    return ((rx ** 2 - ry ** 2) * cos(theta) * sin(theta) -
            px * rx * sin(theta) + py * ry * cos(theta))


def ellipe_tan_dot_derivative(rx, ry, px, py, theta):
    '''The derivative of ellipe_tan_dot.
    '''
    return ((rx ** 2 - ry ** 2) * (cos(theta) ** 2 - sin(theta) ** 2) -
            px * rx * cos(theta) - py * ry * sin(theta))


def estimate_distance(x, y, rx, ry, x0=0, y0=0, angle=0, error=1e-5):
    '''Given a point (x, y), and an ellipse with major - minor axis (rx, ry),
    its center at (x0, y0), and with a counter clockwise rotation of
    `angle` degrees, will return the distance between the ellipse and the
    closest point on the ellipses boundary.
    '''
    x -= x0
    y -= y0
    if angle:
        # rotate the points onto an ellipse whose rx, and ry lay on the x, y
        # axis
        angle = -pi / 180. * angle
        x, y = x * cos(angle) - y * sin(angle), x * sin(angle) + y * cos(angle)

    theta = atan2(rx * y, ry * x)
    while fabs(ellipe_tan_dot(rx, ry, x, y, theta)) > error:
        theta -= ellipe_tan_dot(
            rx, ry, x, y, theta) / \
            ellipe_tan_dot_derivative(rx, ry, x, y, theta)

    px, py = rx * cos(theta), ry * sin(theta)
    return ((x - px) ** 2 + (y - py) ** 2) ** .5

Hier ein Beispiel:

rx, ry = 12, 35  # major, minor ellipse axis
x0 = y0 = 50  # center point of the ellipse
angle = 45  # ellipse's rotation counter clockwise
sx, sy = s = 100, 100  # size of the canvas background

dist = np.zeros(s)
for x in range(sx):
    for y in range(sy):
        dist[x, y] = estimate_distance(x, y, rx, ry, x0, y0, angle)

plt.imshow(dist.T, extent=(0, sx, 0, sy), origin="lower")
plt.colorbar()
ax = plt.gca()
ellipse = Ellipse(xy=(x0, y0), width=2 * rx, height=2 * ry, angle=angle,
                  edgecolor='r', fc='None', linestyle='dashed')
ax.add_patch(ellipse)
plt.show()

Generiert Abstand vom gegebenen Punkt zur gegebenen ellipse einer ellipse und der Abstand von der Grenze der ellipse als heat-map. Wie gesehen werden kann, an der Grenze der Entfernung ist null (deep blue).

Seien Sie gewarnt, dass das Papier hat einige Fehler. Speziell in der 3D-Sektion, die angegebene Formel für P (- X) dot dX/dtheta ist falsch. Ich überprüft mit der hand und wieder mit Mathematica. Es scheint auch Faktoren der "r" fehlt in verschiedenen Orten-vielleicht weniger ein problem, da Sie festlegen können, r 1 ohne Verlust von Allgemeingültigkeit.
Der code oben ist für 2D, das ist korrekt. Auch für nicht-1-r.
Hinsichtlich der 2D-Fall, das Papier verbindet "- Lösung (delta-dot-Tangente)==0" mit "closest point". Es gibt 4 Lösungen innerhalb der ellipse. Was dein Bild zeigt ist, dass das Papier den Vorschlag zur ersten theta führt manchmal zu der falschen root. Es wäre wahrscheinlich interessant, um den Verlauf der Richtung der Lösung des Falles eher als die Entfernung.
Aber außerhalb der ellipse, und ist gültig, richtig? Ich denke, das ist wirklich das, was ich brauchte, es für.

InformationsquelleAutor Matt

1

Brauchen Sie nur berechnen Sie den Schnittpunkt der Linie [P1,P0] zu Ihrem elipse, die S1.

Wenn die Linie equeation ist:

und die elipse equesion ist:

als die Werte der S1 werden:

Nun müssen Sie nur berechnen Sie die Entfernung zwischen S1 zu P1 die Formel (für A,B Punkte) ist:
- Wie kann die 2D-Koordinaten der Punkte haben einen unbestimmten Vorzeichen? Die 4 möglichen Punkten. Ich kann nicht ganz Folgen, wie Sie abgeleitet haben, die S2-Koordinate Gleichungen, scheint es auch, den Sie eingefügt haben das falsche Bild für das line-Gleichung, die ich annehmen, ist so etwas wie y=mx+t oder y=((y1-y0)/(x1-x0)) * (x-x0) + y0
- geändert img...
- Als user3235832 zeigte, das ist falsch, weil es nicht zu liegen, auf einer geraden Linie vom Punkt.
- Diese Lösung funktioniert für mich
InformationsquelleAutor idanuda

Gegeben eine ellipse E in der parametrischen form und einen Punkt P

Abstand vom gegebenen Punkt zur gegebenen ellipse

dem Quadrat der Entfernung zwischen P und E(t) ist

Abstand vom gegebenen Punkt zur gegebenen ellipse

Minimum erfüllen muss,

Abstand vom gegebenen Punkt zur gegebenen ellipse

Mithilfe der trigonometrischen Identitäten

Abstand vom gegebenen Punkt zur gegebenen ellipse

und ersetzen

Abstand vom gegebenen Punkt zur gegebenen ellipse

ergibt sich die folgende quartic equation:

Abstand vom gegebenen Punkt zur gegebenen ellipse

Hier ist ein Beispiel für die C-Funktion, die löst das quartic direkt und berechnet sin(t) und cos(t) für den nächsten Punkt auf der ellipse:

void nearest(double a, double b, double x, double y, double *ecos_ret, double *esin_ret) {
    double ax = fabs(a*x);
    double by = fabs(b*y);
    double r  = b*b - a*a;
    double c, d;
    int switched = 0;

    if (ax <= by) {
        if (by == 0) {
            if (r >= 0) { *ecos_ret = 1; *esin_ret = 0; }
            else        { *ecos_ret = 0; *esin_ret = 1; }
            return;
        }
        c = (ax - r) / by;
        d = (ax + r) / by;
    } else {
        c = (by + r) / ax;
        d = (by - r) / ax;
        switched = 1;
    }

    double cc = c*c;
    double D0 = 12*(c*d + 1);      //*-4
    double D1 = 54*(d*d - cc);     //*4
    double D  = D1*D1 + D0*D0*D0;  //*16

    double St;
    if (D < 0) {
        double t = sqrt(-D0);             //*2
        double phi = acos(D1 / (t*t*t));
        St = 2*t*cos((1.0/3)*phi);        //*2
    } else {
        double Q = cbrt(D1 + sqrt(D));    //*2
        St = Q - D0 / Q;                  //*2
    }

    double p    = 3*cc;                          //*-2
    double SS   = (1.0/3)*(p + St);              //*4
    double S    = sqrt(SS);                      //*2
    double q    = 2*cc*c + 4*d;                  //*2
    double l    = sqrt(p - SS + q / S) - S - c;  //*2
    double ll   = l*l;                           //*4
    double ll4  = ll + 4;                        //*4
    double esin = (4*l)    / ll4;
    double ecos = (4 - ll) / ll4;

    if (switched) {
        double t = esin;
        esin = ecos;
        ecos = t;
    }

    *ecos_ret = copysign(ecos, a*x);
    *esin_ret = copysign(esin, b*y);
}

Versuchen Sie es online!

Gibt es keine inhärenten Grenzen die Werte, auf die es nehmen kann? check_dist(4.0, 2.0, 0, 6); Ergebnisse in nur nan zum Beispiel.
Habe ich wohl vergessen ein besonderer Fall für x = 0.
Zurück NaN für (1.0, 0.75, -0.128053, -0.743808)
Richtig, in manchen Fällen mein code wählt die falsche Lösung der quartic.

InformationsquelleAutor nwellnhof

0

Hab ich gelöst der Distanz Problem über Schwerpunkte.

Für jeden Punkt auf der ellipse

r1 + r2 = 2*a0

wo

r1 - euklidischen Abstand vom gegebenen Punkt zum Brennpunkt 1

r2 - euklidischen Abstand vom gegebenen Punkt zum Brennpunkt 2

a0 - semimajor axis Länge

Kann ich auch die Berechnung der r1 und r2 für einen gegebenen Punkt, die gibt mir eine weitere ellipse, dass dieser Punkt liegt auf, der konzentrisch zu der gegebenen ellipse. Also der Abstand ist

d = Abs((r1 + r2) /2 - a0)
- Dieser post deutet darauf hin, dass Ihre Antwort nicht geben das richtige Ergebnis: math.stackexchange.com/questions/1897587/...
InformationsquelleAutor Robert Hudjakov

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.