   Collision detection question...
  Well, I'm working on a VRP project for class, and the algorithm we've been assigned to use to solve it requires finding whether or not a point falls inside the bounds of an ellipse. I'm familiar with collision detection for circles and quadrilaterals, but my research hasn't turned up anything which applies. Could someone possibly point me in the right direction, or direct me to an article which would help?Just to be a bit more specific on the circumstances, this is a two-dimensional problem which isn't currently tied to any graphical interface, and no code has been written yet, so I can design the data structure to represent the ellipse around the algorithm if necessary. I figure it will likely consist of a center point, a major radius, and a minor radius.Thanks a lot. I'll continue searching for the answer myself, too.   
  The equation of an ellipse with center (0,0) and the principle axis being e_x in cartesian coordinates is:E(x,y) = sqr( x/a ) + sqr( y/b ) - 1 = 0I am not sure, but I guess if E(x,y) > 0 the point is outside and if E(x,y) <= 0 inside of the ellipse. Note that I am not sure whether this is correct.Edit: http://en.wikipedia.org/wiki/Ellipse   ;Quote:Original post by DonDickieDI am not sure, but I guess if E(x,y) > 0 the point is outside and if E(x,y) <= 0 inside of the ellipse. Note that I am not sure whether this is correct.It's all good.Admiral   ;  Ah, thanks. That helps a lot.Now, that equation applies when the major axis is the x-axis... I need to be able to calculate what points are in an ellipse where that may not be the case. It seems to me that the easiest way to go about that would be to store a polar angle with each ellipse, indicating its rotation away from the x-axis. Then, instead of recalculating the ellipse itself, I'd "rotate" the points around it by that amount. The calculation to do that should be much simpler (translate the cartesian coordinates into polar coordinates, apply the rotation, the change them back to cartesian). Does that sound like a good way to go about it?   ;  One way is to remember that an ellipse is just a stretched circle. So work out how to transform the unit circle to your ellipse. Invert the transform and store it. Now for each point you want to test apply the inverted transform to the point and see if it lies inside the unit circle.   ;  Your way works fine, but if the ellipse is not axis-aligned, it may be easier to work with the polar representation. For an axially aligned ellipse of the formx2/a2 + y2/b2 = 1we may write the polar equation:Disclaimer: I don't condone hotlinking [rolleyes]So if the ellipse is to be rotated, it is easier to express it as a linear phase shift in polar coordinates q than the equivalent before converting to Cartesian form.Admiral   ;  Another way is to convert the point into the ellipse space (That should be relatively easy), and do a simple test with the unit sphere.   ;  Are not all of the points on an ellipse such that the sum of the distance from one of the points to each of the focal points (is that what they're called?) the same?  And a circle (geometrically speaking, not object-oriented speaking) is just a special case in that both points happen to be in the same spot?Why not just figure out what that summed distance is and then figure out if the summed distance from the point under test is within that same distance?  That's basically what the first response was getting at, though a whole bunch more elegantly.   ;  Thanks, everyone. I think I've got a working formula now. I just translate, rotate, and stretch the plane so that the ellipse becomes a unit circle, then test to see which points are 1 unit or less from the origin. Simple enough.   