Program til udregning af afstand fra punkt til elipse

Formlen for ellipsen er
x = x0 + a cos(alfa)cos(t) + b sin(alfa)sin(t)
y = y0 - a sin(alfa)cos(t) + b cos(alfa)sin(t)
Formlen for afstand er
d^2 = (x-x1)^2 + (y-y1)^2
-men hvilken afstand er der tale om ? Mindste afstand mellem punktet og et punkt på ellipsen?

Mindste afstand mellem punktet og et punkt på linien.

hov elipsen

Men korrekt
//  [x]  [cos(alpha)  -sin(alpha)] [a*cos(t)]  [xc]
//  [ ] = [                      ] [        ] + [  ]
//  [y]  [sin(alpha)  cos(alpha)] [b*sin(t)]  [yc]
//
//  is calculated. Where
//
//  alpha: Rotation of a - axis
//  xc,yc: Translation of ellipse
//  a,b  : Length og the two ellipse axis.
//

Den afstand du angiver er jo bare afstand fra punkt til punkt.

På understående adresse kan du hente kode til at beregne denne afstand samt mange andre geometriske problemstillinger...

http://www.magic-software.com/DistanceBody.html

Det er lidt besværligt, se nedenfor (fra Dr. Math).
Hvis det drejer sig om noget der resulterer i en tegning på skærmen, så er det nemmeste vel at finde et startpunkt på ellipsen, og løbe punkterne på ellipsen igennem, indtil man har fundet det nærmeste punkt, men hvis du skal bruge det i anden sammenhæng skal du lave en numerisk approksimation
-----
Distance from Point to Ellipse

Date: 05/19/97 at 18:28:41
From: Chuck Ingrum
Subject: Distance from point to an ellipse

I desire a method to find the (minimum) distance from a point to an
ellipse (point and ellipse both in the same plane). The point may be
inside or outside the ellipse. We have been trying to find the tangent
line to the ellipse that is perpendicular to the line drawn from the
point to the same tangent point. So far we have failed. Any thoughts
you have on the subject would be appreciated.

Chuck Ingrum


--------------------------------------------------------------------------------


Date: 05/20/97 at 08:40:03
From: Doctor Jerry
Subject: Re: Distance from point to an ellipse

Hi Chuck,

The slope of the ellipse x^2/a^2+y^2/b^2 = 1 at the pt (x,y) is
-b^2*x/(a^2*y).

If (X,Y) is a point outside, then the slope of line from (X,Y) to a
point (x,y) on the ellipse is (Y-y0)/(X-x0).

As you suggested, you want to choose (x0,y0) such that the slope of
the segment from (x0,y0) to (X,Y) is the negative reciprocal of the
slope of the ellipse at (x0,y0).  So:

  (Y-y0)/(X-x0) = a^2*y0/(b^2*x0)

Regarding (X,Y) as given, another equation is:

  x0^2/a^2+y0^2/b^2 = 1

You must solve these two equations for x0 and y0 in terms of a, b, X,
and Y. However, this is not so easy. You can solve the first equation
for x0 in terms of y0. Substituting into the second equation and
simplifying gives, after some effort, a fourth degree equation to
solve for y0. 

One could apply Ferrari's method, which solves quartics exactly, but I
think it would be a giant mess and probably would not simplify very
much.

So, my opinion is that though in specific cases a quick solution could
be found, there is no convenient formula for the general case.

-Doctor Jerry,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/

Jeg har været inden på denne side og har prøvet at få noget fornuftigt ud af koden der. Dette er ikke lykkes. Det er derfor jeg giver 200 point for at give min en kodet funktion.

Der er en bedre artikel på siden om problemet, nemlig:
http://mathforum.org/library/drmath/view/52082.html

jakob_madsen >> Enten arbejder du hurtigt ellers giver du hurtigt op!
Du kan da næppe have nået at forsøge at få koden til at virke...

Denne artikel har jeg også læst Men disse folk arbejder eksakt og ønsker at finde en funktion som er et udtryk for afstanden. Jeg arbejder i pixel space. Dette betyder at jeg ønsker en afstand i pixels og ikke en eksakt afstand. Derfor vil jeg mene at det er muligt at udregne en ca. afstand.

Jeg har været inden på denne side. Jeg har prøvet meget før jeg udlover 200 point. Hvis man søger på Google er der kun en begrænset antal sider som er intressante. Jeg har arbejder med problemet i et stykke tid og kender derfor koden.

Herudover kan man vel godt forvente hvis man udlover 200 point at få en funktion som kan indsættes direkte som feks.

double getDistFromPointToEllips(double a,double b, double alpha,double x,double y,double x1,double y2)
{
bla bla.....
...
..
.

return dist;

}

Hvis du har et bitmap af det:
Måske kunne en art floodfill gøre det for dig, ie. tag dit punkt og udfyld alle umiddelbare naboer, hvis en af dem røre er afstanden 1, udfyld så alle naboer til disse røre en er afstanden 2 osv.

segmose >> Hvis det kun er en enkelt gang det skul udføres og hvis det var en let løsning så okay, men personligt synes jeg ikke den virker specielt let.
Metoden virker heller robust da den forudsætter, at man ved nogle ting som vil gøre det hele ret statisk...
Rent performance-mæssigt så er den ubamhjertig overfor både CPU og memory.

jakob_madsen >> måske du skulle fortælle lidt mere om hvad du egentlig skal bruge det til.
Du skriver at du arbejder i pixel space og at du skal "udregne en ca. afstand", men signaturen på din metode forudsætter floating point numbers med double præcision!
Så er spørgsmålet: Hvor præcist skal det egentlig være?

Mit bud:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double elipsex(double a,double b, double alpha,double xc,double v)
{
  return a*cos(alpha)*cos(v) + b*sin(alpha)*sin(v) + xc;
}

double elipsey(double a,double b, double alpha,double yc,double v)
{
  return a*sin(alpha)*cos(v) + b*cos(alpha)*sin(v) + yc;
}

double calcdist(double a,double b, double alpha,double xc,double yc,double v,double x,double y)
{
  return sqrt(pow(elipsex(a,b,alpha,xc,v)-x,2) + pow(elipsey(a,b,alpha,xc,v)-y,2));
}

double difcalcdist(double a,double b, double alpha,double xc,double yc,double v,double x,double y,double delta)
{
  return (calcdist(a,b,alpha,xc,yc,v+delta,x,y)-calcdist(a,b,alpha,xc,yc,v,x,y))/delta;
}

double findminv(double a,double b, double alpha,double xc,double yc,double x,double y,double delta)
{
    double v,vlast;
    if(x>=xc && y>=yc)
    {
        v = 1;
    }
    else if(x>=xc && y<yc)
    {
        v = -1;
    }
    else if(x<xc && y>=yc)
    {
        v = 2;
    }
    else if(x<xc && y<yc)
    {
        v = -2;
    }
    do
    {
        vlast = v;
        v = v - 0.5*difcalcdist(a,b,alpha,xc,yc,v,x,y,delta)/calcdist(a,b,alpha,xc,yc,v,x,y);
    } while(fabs(v-vlast)>delta);
    return v;
}

double findmindist(double a,double b, double alpha,double xc,double yc,double x,double y)
{
    double v = findminv(a,b,alpha,xc,yc,x,y,0.0000001);
    return calcdist(a,b,alpha,xc,yc,v,x,y);
}

int main()
{
  printf("test: %f = %f\n",2*sqrt(2)-1,findmindist(1,1,0,0,0,2,2));
  printf("test: %f = %f\n",1.0,findmindist(2,1,0,2,0,2,2));
  return 0;
}

Den kan faktisk laves lidt bedre:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double elipsex(double a,double b, double alpha,double xc,double v)
{
  return a*cos(alpha)*cos(v) + b*sin(alpha)*sin(v) + xc;
}

double elipsey(double a,double b, double alpha,double yc,double v)
{
  return a*sin(alpha)*cos(v) + b*cos(alpha)*sin(v) + yc;
}

double calcdist(double a,double b, double alpha,double xc,double yc,double v,double x,double y)
{
  return sqrt(pow(elipsex(a,b,alpha,xc,v)-x,2) + pow(elipsey(a,b,alpha,xc,v)-y,2));
}

double difcalcdist(double a,double b, double alpha,double xc,double yc,double v,double x,double y,double delta)
{
  return (calcdist(a,b,alpha,xc,yc,v+delta,x,y)-calcdist(a,b,alpha,xc,yc,v,x,y))/delta;
}

double findminv(double a,double b, double alpha,double xc,double yc,double x,double y,double delta)
{
    int i;
    double v,vlast,dist,mindist;
    v = 0;
    mindist = calcdist(a,b,alpha,xc,yc,0,x,y);
    for(i=1;i<=25;i++)
    {
        dist = calcdist(a,b,alpha,xc,yc,0.25*i,x,y);
        if(dist < mindist)
        {
            mindist = dist;
            v = i;
        }
    }
    do
    {
        vlast = v;
        v = v - 0.5*difcalcdist(a,b,alpha,xc,yc,v,x,y,delta)/calcdist(a,b,alpha,xc,yc,v,x,y);
    } while(fabs(v-vlast)>delta);
    return v;
}

double findmindist(double a,double b, double alpha,double xc,double yc,double x,double y)
{
    double v = findminv(a,b,alpha,xc,yc,x,y,0.0000001);
    return calcdist(a,b,alpha,xc,yc,v,x,y);
}

int main()
{
  printf("test: %f = %f\n",2*sqrt(2)-1,findmindist(1,1,0,0,0,2,2));
  printf("test: %f = %f\n",1.0,findmindist(2,1,0,2,0,2,2));
  return 0;
}

En meget enkelt algoritme:
t er parameteren:
0) sæt t = 0
1) beregn et punkt på ellipsen som fkt. af t
2) beregn afstand til punkt, check om det er mindre en tidligere fundet afstand
3) t+=delta_t
4) forsæt ved 1
Dette kan optimeres, man behøver ikke løbe hele ellipsen igennem. Har fordelen af at være enkelt at afprøve og debugge og virker uanset om punktet er indeni, på eller udenfor ellipsen.

Tid at afslutte spørgsmålet ?

??