aleien aleien - 1 year ago 73
Java Question

How to find points of intersection between ellipse and line?

I'm completely stuck.
I have an ellipse, and a line. Line is set by two points, ellipse - by bottom-left and top-right corners. I have to find their points of intersection, using java.
I tried to solve an equation system:

(1) y = kx + m;
x^2/a^2 + y^2/b^2 = 1;

but I could't make things work properly. I assume it's because of java's coordinate system, but it also may be my own mistake somewherem beacuse I'm confused with it.

Is there any better way to find points of intersection and, if not, how can I get them properly?

Thank you in advance.


double r1 = in_y2-in_y;
double r2 = in_x2-in_x;
double k = r1/r2;
double m = in_y2 - k*in_x2;
double a = Math.abs((double)x2 - (double)x)/2;
double b = Math.abs((double)y2 - (double)y)/2;

double A1 = 1/(a*a) + (k*k)/(b*b);
double B1 = (2*k*m)/b*b;
double C1 = (m*m)/(b*b);
double D = Math.sqrt(B1*B1 - 4*A1*C1);
double ex1 = (-B1 + D/(2*A1));
double ey1 = k*ex1 + m;
double ex2 = (-B1 - D/(2*A1));
double ey2 = k*ex2 + m;

Answer Source

This is probably no longer relevant to the original problem owner, but since I encountered the same question, let me present my answer.

There are three mistakes in the original computation that I can see: (i) the one pointed out by @mprivat, (ii) the bracketing in the assignment to B1 which should instead be

double B1 = (2*k*m)/(b*b);

and (iii) a more fundamental one: the presented computation does not correct for the origin of the ellipse. Since the ellipse is defined by itse circumscribing bounds, there is no guarantee that it is centered on (0,0).

Let's call the center (cx,cy), then the equation for the ellipse becomes

(x-cx)^2/a^2 + (y-cy)^2/b^2 = 1

rather than the original

x^2/a^2 + y^2/b^2 = 1

The simple repair, I think, is to translate the line wrt (cx,cy) and translate the results back, like so:

double m = (in_y2-cy) - k*(in_x2-cx);
double ex1 = (-B1 + D/(2*A1)) + cx;
double ey1 = k*(ex1-cx) + m + cy;
double ex2 = (-B1 - D/(2*A1)) + cx;
double ey2 = k*(ex2-cx) + m + cy;

The more elegant repair is to solve the correct equation for the ellipse instead, but this results in even more impenetrable formulas for B1 and C1:

double B1 = (2*k*(m-cy))/(b*b) - (2*cx)/(a*a);
double C1 = (m-cy)*(m-cy)/(b*b) - 1 + (cx*cx)/(a*a);

As a final remark, note that this breaks down for vertical lines, as then r2 = 0 so k isn't defined.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download