The ellipse is actually a circle. I know all the coordinates of both things, I just need to know whether or not a line goes through an ellipse.
Is this built in anywhere? SPecifically I am using QGraphicsEllipseIem and QLine but i can convert them to any other type
thanks
Since you're using QGraphicsScene you should use its methods to determine if objects intersect or collide. From its documentation:
One of QGraphicsScene's greatest strengths is its ability to efficiently determine the location of items. Even with millions of items on the scene, the items() functions can determine the location of an item within few milliseconds. There are several overloads to items(): one that finds items at a certain position, one that finds items inside or intersecting with a polygon or a rectangle, and more. The list of returned items is sorted by stacking order, with the topmost item being the first item in the list. For convenience, there is also an itemAt() function that returns the topmost item at a given position.
See collidesWithItem() and collidingItems().
You say it's a circle. I assume you know the center (C) and the radius (r). So the circle is P == |P - C| = r, equivalent to <P-C, P-C> = r*r and finally <P-C, P-C> - r*r = 0.
You know the line, so you know two points (A and B). In parametric equations, it's P == A + t(B-A).
For points that are intersections, then, both equations hold true. So you can substitute the second equation in the first one, yielding <A+t(B-A)-C, A+t(B-A)-C> - r*r = 0. If you expand that dot product, you get a quadratic equation in t (that is, K1*t*t + K2*t + K3 = 0).
If you only need to know whether there are intersections, compute the determinant (K2*K2 - 4*K1*K3). If that's negative, the line and the circle don't intersect. If it's positive, there are two intersections. If it's zero, the line is tangent to the circle.
If you want to compute the coordinates of the intersection(s), compute the values of t, and plug them in the parametric line equation to get the coordinates.
The general procedure is to first form the parametric equation for the line using its endpoints:
x(t) = x1 + (x1 - x2) * t
y(t) = y1 + (y1 - y2) * t
Then plug the expressions for x(t) and y(t) into the equation of your ellipse, which will give you a quadratic equation in t. Use the quadratic formula to find the roots of this equation, which are the values of t such that the point is on the ellipse.
Finally, plug t into the equations for x(t) and y(t) to get the point or points or intersection. Note that in the case that there is no intersection, there will be no real roots of the quadratic equation.
Here's an article on Circle-Line Intersection.
It gives the formula for the intersection points, if any. If all you want to know is whether there is an intersection, calculating a discriminant will tell you whether there are two, one, or no points of intersection.