Given a segment of two points A and B (each point has coordinates).

An ellipse is given (for now I set the upper left point, the length and width, but if necessary, these parameters can be replaced with any other).

Task: find out if a segment intersects with an ellipse. The case in which the segment is completely in an ellipse does not satisfy the condition.

Help, please, and then nothing comes to mind. If possible, then you need code in java, if not - give a solution, and I will write the code myself.

  • 3
    it is necessary to check whether the system of equations has a solution (if it has something to intersect), in which the first is the equation of a straight line at two points, the second is the equation of the ellipse - ampawd

3 answers 3

UPD (based on the @AnT comment):

Perhaps such an arrangement of points and an ellipse, in which both points will lie outside the ellipse, but the intersection will be (one, in the case where the line passing through the given points will be tangent to the ellipse and two otherwise). This case is not considered in this decision. In general, it is necessary to solve the system of equations.

The variant, with the help of which you do not need to solve equations (without using numerical methods):

Let an ellipse be given:

(x-x0)^2/a^2 + (y-y0)^2/b^2 = 1

where:

  • (x0;y0) - coordinates of the center of the ellipse;
  • a and b are the lengths of the major and minor axes, respectively.

and segment AB , where A(x1;y1) and B(x2;y2) .

In order for the segment AB intersect a given ellipse, it is necessary and sufficient that one of the inequality systems be true:

 (x1-x0)^2/a^2 + (y1-y0)^2/b^2 < 1 (x2-x0)^2/a^2 + (y2-y0)^2/b^2 > 1

(the case when the point A lies inside the ellipse, and B - outside it);

 (x1-x0)^2/a^2 + (y1-y0)^2/b^2 > 1 (x2-x0)^2/a^2 + (y2-y0)^2/b^2 < 1

(the case when the point A lies outside the ellipse, and B - inside it).

If the case of the points belonging to the arc of an ellipse is of interest, then in the above systems the inequalities will be weak.

  • "In order for the segment AB to intersect a given ellipse, it is necessary and sufficient that one of the systems of inequalities be true." Is it? But what about the case when both points lie outside the ellipse, but at the same time, the segment still intersects the ellipse (at two points)? - AnT
  • @AnT, I have not considered this case. You're right. - post_zeew

From geometry - two lines intersect, if for the system of equations describing these lines, there is a solution

create a system of equations of 2x
straight line = (x-xa)/(xb-xa)=(y-ya)/(yb-ya)
the equation of the ellipse is necessary to choose the most suitable for you, after which in both equations you express y and solve the system

for the canonical equation of an ellipse (the axes of the ellipse coincide with the axes of coordinates) ( x^2/a^2+y^2/b^2=1 )
line y=((x-xa)*(yb-ya))/(xb-xa)+ya ellipse y=+-sqrt((1/b^2)-(x^2/a^2*b^2))

then we substitute all known data and get or not get a point, if received - there is an intersection, not received = no

  • What line is your last equation? - post_zeew
  • @post_zeew y = sqrt ((1 / b ^ 2) - (x ^ 2 / a ^ 2 * b ^ 2)) is the expressed y from the canonical equation of the ellipse - x ^ 2 / a ^ 2 + y ^ 2 / b ^ 2 = 1 - Tr1nks
  • one
    I understand it. But these two expressions are not equivalent. What you have expressed is the part of the arc of the ellipse that lies in the upper half-plane. In general, +/- there should be. - post_zeew
  • @post_zeew Exactly, in the same place from under the root under the module ..., I agree with your remark, thanks! - Tr1nks

Any ellipse is nothing more than a "stretched" (or, if you like, "oblate") circle. It is enough to construct a coordinate transformation that will transform the original ellipse into an arbitrary circle of nonzero radius, and the task will be reduced to determining the fact of intersection of the segment with the circle. (It is clear that such a coordinate transformation will translate a segment into a segment.)

From the above condition we can implicitly conclude that this is not an arbitrary ellipse, but an ellipse whose axes are parallel to the axes of coordinates. (By the way, why is this not explicitly stated in the condition?). In such a situation, the required transformation is constructed elementarily - it is just a multiplication of one of the coordinates by the coefficient a/b - the ratio of the lengths of the axes of the ellipse.

Thus, we reduce the problem to the problem of the intersection of a segment and a circle.

The task of suppressing a segment with a circle is simply solved. It suffices to calculate the coordinates of the ends of the chord, the “cut off” line that contains our segment (if such a chord exists). The position of the ends of the segment relative to the ends of the chord will immediately tell us whether our segment intersects the given circle (and, if necessary, gives us the coordinates of the intersection points).

The inverse coordinate transformation will give us the coordinates of the points of intersection with the original ellipse (if we are interested).