Community
Participate
Working Groups
Build Identifier: I20091030-1201 There is a class in draw2d called Geometry which is being used in polyline.containsPoint(int x, int y) This has a method called segmentContainsPoint which uses Dot product of two vectors formula to calculate the distance between the point and the line segment... /** * @return true if the least distance between point (px,py) and segment (x1,y1) - (x2,y2) is * less then specified tolerance */ private static boolean segmentContainsPoint(int x1, int y1, int x2, int y2, int px, int py, int tolerance) { /* * Point should be located inside Rectangle(x1 -+ tolerance, y1 -+ tolerance, x2 +- * tolerance, y2 +- tolerance) */ Rectangle lineBounds = Rectangle.SINGLETON; lineBounds.setSize(0, 0); lineBounds.setLocation(x1, y1); lineBounds.union(x2, y2); lineBounds.expand(tolerance, tolerance); if (!lineBounds.contains(px, py)) { return false; } /* * If this is horizontal, vertical line or dot then the distance between specified point * and segment is not more then tolerance (due to the lineBounds check above) */ if (x1 == x2 || y1 == y2) { return true; } /* * Calculating square distance from specified point to this segment using formula for Dot * product of two vectors. */ int v1x = x2 - x1; int v1y = y2 - y1; int v2x = px - x1; int v2y = py - y1; int numerator = v2x * v1y - v1x * v2y; int denominator = v1x * v1x + v1y * v1y; int squareDistance = (int) ((long) numerator * numerator / denominator); return squareDistance <= tolerance * tolerance; } Here at the end ,the dot product formula is wrong the denominater should be modded,since it can be negative and the distance can come out to be negative, which will be always less tolerance^2... In certain scanarious the segmentcontainspoint returns true hence the selection. Reproducible: Sometimes
Are you talking about: int denominator = v1x * v1x + v1y * v1y ? It's the sum of squares... How could this be negative?
(In reply to comment #1) > Are you talking about: > int denominator = v1x * v1x + v1y * v1y > ? > > It's the sum of squares... How could this be negative? (In reply to comment #1) > Are you talking about: > int denominator = v1x * v1x + v1y * v1y > ? > > It's the sum of squares... How could this be negative? int squareDistance = (int) ((long) numerator * numerator / denominator); If the value of v1x * v1x + v1y * v1y becomes more then integer max, then after casting it will become negative :)
Indeed, that makes sense, we've faced int overflows before :-) Wonder if we can make this a bit better... like having long denominator and long numerator and to the cast to long for their calculation. Looks like denominator calculation may result in overflo too. What do you think?
Would't it be sufficient to change numerator, denumerator and squareDistance to long and do the comparison based on longs?
(In reply to comment #4) > Would't it be sufficient to change numerator, denumerator and squareDistance to > long and do the comparison based on longs? yep that seems perfect solution(until it overflows someday ;D )
Created attachment 169436 [details] patch Alexander, Vijay can you code review / buddy test this patch please?
(In reply to comment #6) > Created an attachment (id=169436) [details] > patch > > Alexander, Vijay > can you code review / buddy test this patch please? Hi Alex this will not work. int numerator = v2x * v1y - v1x * v2y; int denominator = v1x * v1x + v1y * v1y; long numerator = (long) v2x * v1y - v1x * v2y; long denominator = (long) v1x * v1x + v1y * v1y; long squareDistance = numerator * numerator / denominator; I tryed multiplying two big integers so that the result is long. it first overflows and then is is casted to long. So long v1y = y2 - y1; long v2x = px - x1; long v2y = py - y1; long numerator = v2x * v1y - v1x * v2y; long denominator = v1x * v1x + v1y * v1y; long numerator = v2x * v1y - v1x * v2y; long denominator = v1x * v1x + v1y * v1y; long squareDistance = numerator * numerator / denominator; "It is inevitable, Mr Anderson" everything should be long cuz,v1x * v1x can overflow.
This dot product may be used at many places, what about them. For example In GMF,and many other calculations(i do not know of any apart from PolyLineConnectionex class)
(In reply to comment #7) > (In reply to comment #6) > > Created an attachment (id=169436) [details] [details] > > patch > > > > Alexander, Vijay > > can you code review / buddy test this patch please? > > Hi Alex > > this will not work. > > int numerator = v2x * v1y - v1x * v2y; > int denominator = v1x * v1x + v1y * v1y; > > long numerator = (long) v2x * v1y - v1x * v2y; > long denominator = (long) v1x * v1x + v1y * v1y; > long squareDistance = numerator * numerator / denominator; > > I tryed multiplying two big integers so that the result is long. > it first overflows and then is is casted to long. > > So > > long v1y = y2 - y1; > long v2x = px - x1; > long v2y = py - y1; > > long numerator = v2x * v1y - v1x * v2y; > long denominator = v1x * v1x + v1y * v1y; > > long numerator = v2x * v1y - v1x * v2y; > long denominator = v1x * v1x + v1y * v1y; > long squareDistance = numerator * numerator / denominator; > > "It is inevitable, Mr Anderson" > > everything should be long cuz,v1x * v1x can overflow. Right, the multiplication already has to be performed based on long precision.
Created attachment 177978 [details] patch Here is the corrected patch. If this one looks ok - I'll deliver it for 3.6.1
(In reply to comment #10) > Created an attachment (id=177978) [details] > patch > > Here is the corrected patch. If this one looks ok - I'll deliver it for 3.6.1 Looks ok to me,
Thanks, Anthony. Delivered to R3_6_maintenance and HEAD.
