line2d::isPointOnLine issue

[Misan]

I encountered a weird problem: using line2d::intersectWith gives me a vector2d with the intersection point. Great. So I assumed that, naturally, calling isPointOnLine with that vector as a parameter would ALWAYS return true. That was not the case, so I looked at the method's source code:

bool isPointOnLine(const vector2d<T>& point) const
{
T d = getPointOrientation(point);
return (d == 0 && point.isBetweenPoints(start, end));
}

I changed the == operator to core::equals to compensate for the float rounding error, and it started working as expected. I don't know whether it's a known issue, but I thought I'd share anyway .

[CuteAlien]

Thanks. I know about it already, but unfortunately even using an epsilon here won't be sufficient in all cases (I already had cases where it failed even then). I found one robust implementation, but that one is slow (and complicated): http://www.cs.cmu.edu/~quake/robust.html

Not certain yet how to solve that - using an epsilon would catch more cases - without really fixing it - so couldn't decide if that is a good or a bad idea.

My current solution is avoiding that function in my code completely. Instead I find the nearest point on the line to a given point and check the distance between them.

[Misan]

Wouldn't checking the distance from the nearest point on the line be kind of mathematically equivalent to using an epsilon? At what distance, exactly, should I consider my point "on that line"?

Anyway, you're right, before your reply I also had a couple of cases where I had to increase my epsilon from the f32 rounding error.. but I'm just afraid that at some point I'll start getting false positives.

[CuteAlien]

Yes, that's also an epsilon - just not the same one. d isn't the distance here, so it's hard to tell what the epsilon should be.

[gerdb]

would it be better to test for circle - line intersection ? (circle with the radius F32_ROUNDING_ERROR)

Code: Select all

 
 
bool isPointOnLine(const vector2d<T>& point) const
{
 T d = getPointOrientation(point);
 f32 eps = 1.5f*F32_ROUNDING_ERROR; // so d can be -eps left or +eps right, but not 2*F32_ROUNDING_ERROR left or right
 return ( core::equals(d,0,eps) && point.isBetweenPoints(start, end));
}
 
 

as ive seen, isBetweenPoints(start, end) does not care for rounding errors either, i mean that the circle (x,y,r=F32_ROUNDING_ERROR) can lie before start, or behind point end.

[Misan]

@gerdb: As stated by CuteAlien before, the test sometimes fails even for values "much larger" than F32_ROUNDING_ERROR

[gerdb]

the test sometimes fails even for values "much larger" than F32_ROUNDING_ERROR

pls give some numbers that fail on your side, because mine don't.

i generated 10000 points A B, all coords are 1..1000000 times ROUNDING_ERROR_f32

Code: Select all

 
// test
 
        for (u32 i=0; i<10000; i++)
        {
                core::vector2df A( ((rand()%1000000)+1)*core::ROUNDING_ERROR_f32, ((rand()%1000000)+1)*core::ROUNDING_ERROR_f32 );
                core::vector2df B( ((rand()%1000000)+1)*core::ROUNDING_ERROR_f32, ((rand()%1000000)+1)*core::ROUNDING_ERROR_f32 );
                core::vector2df P = A+((B-A).normalize()*(f32)((B-A).getLength()/(f32)((rand()%1000000)+1)));
 
                core::stringc s("");
                s+=core::sprintf("A(%f,%f), B(%f,%f), P(%f,%f)\n", A.X, A.Y, B.X, B.Y, P.X, P.Y);
                s+=core::sprintf("Orientation = %f", getPointOrientation(A,B,P));
                s+=core::sprintf(", isBetweenPoints = %s", (isBetweenPoints(A,B,P))?"true":"false");
                s+=core::sprintf(", isPointOnLine = %s\n", (isPointOnLine(A,B,P))?"true":"false");
                s+=core::sprintf("Orientation2 = %f", getPointOrientation2(A,B,P));
                s+=core::sprintf(", isBetweenPoints2 = %s", (isBetweenPoints2(A,B,P))?"true":"false");
 
                ELOG_LEVEL lvlResult = (isPointOnLine2(A,B,P))?ELL_NONE:ELL_ERROR;
 
                s+=core::sprintf(", isPointOnLine2 = %s\n", (lvlResult==ELL_NONE)?"true":"false");
 
                logger->log( s.c_str(), lvlResult );
        }
 
 

the only difference between isPointOnLine && isPointOnLine2 is core::equals(d,0.0f,1.5f*ROUNDING_ERROR_f32);

Result: All function calls to isPointOnLine failed !!!!
All function calls to isPointOnLine2 succeeded !!!!

log-file:

http://benjaminhampe@benjaminhampe.be.o ... nLine.html

i would test for other points that are much larger, because substracting tiny from large numbers can produce false results.

but i would guarantee that there are no false positives.

EDIT: the test start to fail if coords of point A are 1000 times larger or smaller than point B

[Misan]

I have to admit, that's a pretty comprehensive test, but still, your point/line values are still pretty small (<1.0f). Most of my false negatives occurred with relatively long lines (>20.0f).

[CuteAlien]

I just looked at what getPointOrientation does, but would need more time to see why this work. It seems every point on the line can form 2 squares which start at the line-start and go through the point parallel to the axis and up to the end of the line on either x or y. And the area of those 2 squares always should be the same size independent of which point on the line is chosen. Would have to spend a few more minutes on this to figure out why this works, I didn't even know those squares have that property although it makes some intuitive sense (and it's even kinda interesting). But not sure yet if there is any epsilon that make sense. Working with areas it means probably if there is a meaningful epsilon it is likely using a square-root - but couldn't tell without calculating this through if there is any connection between the error and the distance of the point to the line (maybe someone wants to calculate this, just needs school math).

Maybe we should just replace this by a calculating the distance to the line and add the epsilon as parameter. It's slower but works. But we have to think about how to handle the points which are not between points in that case as isBetweenPoints wouldn't handle that. Probably we need a getClosestPoint function which does not only return the point but also the information if it was inside the segment (we already have that info, we just don't return it, should probably have one more getClosestPoint that returns the vector2d that is returned now as reference parameter and returns additionally an integer that is -1,0,1 for describing which part of the segment it hits (before,inside,behind)). And isPointOnLine could be renamed to isPointOnLineFast (just in case someone needs that function to work as it does - I guess it works well for example for lines which are parallel to the axis).