Igor Lopez: > 2011/7/16 Andrew Poelstra <as...@sfu.ca>: > > There is a fairly informative discussion of this problem on SO: > > http://stackoverflow.com/questions/2945337/how-to-detect-if-an-ellipse-intersectscollides-with-a-circle > > I had a look and found one algebraic solution close to the one I have > proposed. > > > The correct methods given there generally require root-solvers, > > Why is the algebraic solution not correct?
Because of false assumptions about the "inner" and "outer" arcs, see below. > > Since we rarely care about the exact distance, only "is it between > > 0 and Radius" it is probable that we could use a bisection method > > with very few iterations to get an answer. > > I am convinced we do not need any iterations or equation solvers. > We just need to check with the transformed point coordinates > in the equations for the two arcs where one is the inner arc and > the other is the outer arc where the point radius has been subtrcacted > respectively added to the arc lenghts(width, height). > If the point intersects the equation for the inner arc is <= 0 and > the equation for the outer arc is >= 0 and since it is not a complete > ellipse one need to check that the angle between point and > arc centerpoint is within the arcs limiting angles which is not > to difficult if the limiting angles are known. You are assuming that the two arcs are ellipses, which they are not. E.g. if you draw an ellipse with a thick pen, the inner space will look more like an almond than an ellipse. Take an ellipse with a = 5 and b = 4, and add a thickness = 1 to the perimeter. The point Pb = (xb,yb) = (3, 16/5) = (3, 3.2) is on the ellipse. Go out 1 (thickness) from that point in the normal direction (see e.g. [1]), i.e. along the line y - 16/5 = mn * (x - 3), mn = a*a*yb / (b*b*xb) = (25*16/5) / (16*3) = 5/3 you will come to the point Pt = (xt, yt) = (3+3/k, 16/5 + 5/k) ~= (3.51, 4.06) where k = sqrt(34), 5.83 < k < 5.84 Now, check if Pt lies on the ellipse: x^2/at^2 + y^2/bt^2 = 1, where at = a+1 = 6, bt = b+1 = 5 (3+3/k)^2 / 36 + (16/5+5/k)^2 / 25 ~= 1.0016 > 1 i.e. the new arc is not an ellipse. /// If this error is small enougth to ignore, fine, but what error do we tolerate? Regards, /Karl Hammar [1] http://de.wikipedia.org/wiki/Ellipse#Normalengleichung_.28kartesische_Koordinaten.29 ----------------------------------------------------------------------- Aspö Data Lilla Aspö 148 S-742 94 Östhammar Sweden +46 173 140 57 _______________________________________________ geda-user mailing list geda-user@moria.seul.org http://www.seul.org/cgi-bin/mailman/listinfo/geda-user
