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?

Code:

``````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;
``````

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