Home » Eclipse Projects » GEF » Bug in lineContainsPoint in Polyline
| Bug in lineContainsPoint in Polyline [message #74498] |
Thu, 03 April 2003 14:46  |
Eclipse User |
|
|
|
Originally posted by: jayuen.alumni.uwaterloo.ca
Hi:
There is a bug in the lineContainsPoint(int, int, int, int, int, int, int)
method in the Polyline class (Draw2D 2.1). Currently, the lineContainsPoint
implementation uses ints to store the numerator, denominator, and result
variables. However, if a drawn line is too long, the numerator will
overflow when it is shifted 10 bits. One solution to this is to declare the
numerator, denominator, and result as longs rather than ints.
Here is the changed code:
-------
private boolean lineContainsPoint(
int x1, int y1,
int x2, int y2,
int px, int py,
int tolerance) {
LINEBOUNDS.setSize(0, 0);
LINEBOUNDS.setLocation(x1, y1);
LINEBOUNDS.union(x2, y2);
LINEBOUNDS.expand(tolerance, tolerance);
if (!LINEBOUNDS.contains(px, py))
return false;
int v1x, v1y, v2x, v2y;
long numerator, denominator;
long result = 0;
if (x1 != x2 && y1 != y2) {
v1x = x2 - x1;
v1y = y2 - y1;
v2x = px - x1;
v2y = py - y1;
numerator = v2x * v1y - v1x * v2y;
denominator = v1x * v1x + v1y * v1y;
result = ((numerator << 10) / denominator * numerator) >> 10;
}
// if it is the same point, and it passes the bounding box test,
// the result is always true.
return result <= tolerance * tolerance;
------
Thanks,
Jason
|
|
|
| Re: Bug in lineContainsPoint in Polyline [message #74518 is a reply to message #74498] |
Thu, 03 April 2003 15:22  |
| Eclipse User |
|
|
|
Originally posted by: none.us.ibm.com
"Jason Yuen" <jayuen@alumni.uwaterloo.ca> wrote in message
news:b6i2p0$kbm$1@rogue.oti.com...
> Hi:
>
> There is a bug in the lineContainsPoint(int, int, int, int, int, int, int)
> method in the Polyline class (Draw2D 2.1). Currently, the
lineContainsPoint
> implementation uses ints to store the numerator, denominator, and result
> variables. However, if a drawn line is too long, the numerator will
> overflow when it is shifted 10 bits. One solution to this is to declare
the
> numerator, denominator, and result as longs rather than ints.
>
> Here is the changed code:
>
> -------
> private boolean lineContainsPoint(
> int x1, int y1,
> int x2, int y2,
> int px, int py,
> int tolerance) {
> LINEBOUNDS.setSize(0, 0);
> LINEBOUNDS.setLocation(x1, y1);
> LINEBOUNDS.union(x2, y2);
> LINEBOUNDS.expand(tolerance, tolerance);
> if (!LINEBOUNDS.contains(px, py))
> return false;
>
> int v1x, v1y, v2x, v2y;
> long numerator, denominator;
> long result = 0;
>
> if (x1 != x2 && y1 != y2) {
>
> v1x = x2 - x1;
> v1y = y2 - y1;
> v2x = px - x1;
> v2y = py - y1;
>
> numerator = v2x * v1y - v1x * v2y;
> denominator = v1x * v1x + v1y * v1y;
> result = ((numerator << 10) / denominator * numerator) >> 10;
Since you apparently have a long line test case, would you mind trying this
as well:
result = ((long)numerator)*numerator / denominator;
> }
>
> // if it is the same point, and it passes the bounding box test,
> // the result is always true.
> return result <= tolerance * tolerance;
>
> ------
>
> Thanks,
> Jason
>
>
|
|
|
| Re: Bug in lineContainsPoint in Polyline [message #74612 is a reply to message #74518] |
Fri, 04 April 2003 20:11 |
| Eclipse User |
|
|
|
Originally posted by: seank.nulogy.com
You are right Randy, the problem is the numerator overflowing during the
calculation of the result. This code works too:
result = (int)((((long)numerator << 10) / denominator * numerator) >> 10);
(I've left the variables result, numerator and denominator as ints).
In our test case, the values of numerator and denominator each go above 200
000 000 (yes, this is one long line). So perhaps it isn't necessary for the
numerator and denominator to be declared as longs since that would require a
line about 4 times longer than the one in our test to cause an overflow of
these variables. IMHO that is not likely to happen. On the other hand, you
never really know and i don't think that declaring them as longs will
appreciably hurt the performance of this method.
Anyhow, we just wanted to let you guys know about it. We'll leave the exact
implementation of the fix to the GEF gurus :)
Sean
"Randy Hudson" <none@us.ibm.com> wrote in message
news:b6i4s5$m6a$1@rogue.oti.com...
>
> "Jason Yuen" <jayuen@alumni.uwaterloo.ca> wrote in message
> news:b6i2p0$kbm$1@rogue.oti.com...
> > Hi:
> >
> > There is a bug in the lineContainsPoint(int, int, int, int, int, int,
int)
> > method in the Polyline class (Draw2D 2.1). Currently, the
> lineContainsPoint
> > implementation uses ints to store the numerator, denominator, and result
> > variables. However, if a drawn line is too long, the numerator will
> > overflow when it is shifted 10 bits. One solution to this is to declare
> the
> > numerator, denominator, and result as longs rather than ints.
> >
> > Here is the changed code:
> >
> > -------
> > private boolean lineContainsPoint(
> > int x1, int y1,
> > int x2, int y2,
> > int px, int py,
> > int tolerance) {
> > LINEBOUNDS.setSize(0, 0);
> > LINEBOUNDS.setLocation(x1, y1);
> > LINEBOUNDS.union(x2, y2);
> > LINEBOUNDS.expand(tolerance, tolerance);
> > if (!LINEBOUNDS.contains(px, py))
> > return false;
> >
> > int v1x, v1y, v2x, v2y;
> > long numerator, denominator;
> > long result = 0;
> >
> > if (x1 != x2 && y1 != y2) {
> >
> > v1x = x2 - x1;
> > v1y = y2 - y1;
> > v2x = px - x1;
> > v2y = py - y1;
> >
> > numerator = v2x * v1y - v1x * v2y;
> > denominator = v1x * v1x + v1y * v1y;
> > result = ((numerator << 10) / denominator * numerator) >> 10;
>
> Since you apparently have a long line test case, would you mind trying
this
> as well:
>
> result = ((long)numerator)*numerator / denominator;
>
>
>
> > }
> >
> > // if it is the same point, and it passes the bounding box test,
> > // the result is always true.
> > return result <= tolerance * tolerance;
> >
> > ------
> >
> > Thanks,
> > Jason
> >
> >
>
>
|
|
| |
| Re: Bug in lineContainsPoint in Polyline [message #74991 is a reply to message #74630] |
Tue, 08 April 2003 15:06 |
| Eclipse User |
|
|
|
Originally posted by: jayuen.alumni.uwaterloo.ca
Not charting the galaxy but we probably have too much time on our hands :)
The situation arose when we had two Polylines in our diagram, each of which
was connecting two separate pairs of glyphs. We then graphically dragged
both lines to make them really long (roughly the diagonal of a 15" screen at
1400x1050). When we tried to select the rectangle in the bottom left
corner, the selection jumped to the long line on the right. This led us to
examine Figure.containsPoint() which is called when selection is determined.
Please see the attached image (the glyphs in the image are zoomed out 50%
but you get the idea).
We encountered a similar problem (and reported it) with the Ellipse
containsPoint() method about a month ago which I think you also discovered.
The problem seems to arise anytime a large left bit shift is used on an int
(e.g. in the Ellipse and in the Polyline, I think a 10 bit shift is
employed) in order to presumably yield more significant digits when
computing the bounds checks.
Hope that helps..
Jason
"Randy Hudson" <none@us.ibm.com> wrote in message
news:b6ldum$8tr$1@rogue.oti.com...
> > In our test case, the values of numerator and denominator each go above
> 200
> > 000 000 (yes, this is one long line). So perhaps it isn't necessary for
> the
>
> When do lines this big show up. Are you charting the galaxy or something
> :-)?
>
> > numerator and denominator to be declared as longs since that would
require
> a
> > line about 4 times longer than the one in our test to cause an overflow
of
> > these variables. IMHO that is not likely to happen. On the other hand,
> you
> > never really know and i don't think that declaring them as longs will
> > appreciably hurt the performance of this method.
>
> It probably is negligible here, but I wonder how many places we would have
> to use longs? We've already started using doubles in some places to
support
> zoom. That's why I'm curious about the situation which led you to
overflow.
>
>
>
|
|
|
Goto Forum:
Current Time: Sat Jul 26 19:32:23 EDT 2025
Powered by FUDForum. Page generated in 0.04125 seconds |
Home