Crazy boolean bug

ID:263887
 
Jan 27 2008, 10:25 pm
Code:
            //Returns 1 if the given point is inside the triangle, 0 otherwise
            pointInTriangle(var/datum/Point/p)
                
                //Look for being outside bounding rect
                //this should speed up this algorithm a lot
                if( (p.x>maxx) || (p.x<minx) )
                    return 0
                if( (p.y>maxy) || (p.y<miny) )
                    return 0

                var/A=findArea()  //Area of the triangle

                //We need to create mini triangles containing our point
                var/datum/Triangle
                    ABP=new(a.x, a.y, b.x, b.y, p.x, p.y)
                    BCP=new(b.x, b.y, c.x, c.y, p.x, p.y)
                    CAP=new(c.x, c.y, a.x, a.y, p.x, p.y)

                //add the area of all the triangles
                //if they're more than the area of this triangle, point is not inside
                world<<"ABP: [ABP.findArea()] BCP: [BCP.findArea()] CAP: [CAP.findArea()]"
                var/sumA=ABP.findArea() + BCP.findArea() + CAP.findArea()
                world<<"Point: ([p.x], [p.y]) SumA: [sumA] A: [A]"
                if( sumA > A)
                    return 0
                return 1


Problem description:

I've been scratching my head for hours over this one. For some reason, sometimes sumA and A will equal the exact same thing and yet the if statement resolves to true.

Triangle is (6, 6) (8.12132, 8.12132) (3.87868, 8.12132)

ABP: 0 BCP: 2.37868 CAP: 2.12132
Point: (7, 7) SumA: 4.5 A: 4.5
ABP: 1.06066 BCP: 0.257361 CAP: 3.18198
Point: (7, 8) SumA: 4.5 A: 4.5

The two datasets above are the problematic ones. And the really strange thing is that a dataset such as:

ABP: 2.12132 BCP: 2.37868 CAP: 0
Point: (5, 7) SumA: 4.5 A: 4.5

evaluates correctly. Is this possibly a bug with Byond or am I missing something?

If this isn't clear let me know and I'll explain further or post more code or something.
Jan 27 2008, 11:13 pm
I made a quick test program and I didn't see any problems. However, I may have changed something though without realizing it. I am guessing that your problem is with one of your equations, or perhaps you put a c somewhere and you meant to put an a.

var/triangle/tri = null

mob
    verb
        NewTri(ax as num,ay as num,bx as num,by as num,cx as num,cy as num)
            tri = new(ax,ay,bx,by,cx,cy)
        
        TryPoint(x as num,y as num)
            var/point/p = new(x,y)
            if(tri.pointInTriangle(p))
                world << "Yeah!"
            else world << "NO!"

proc
    distance(ax,ay,bx,by)
        return sqrt((ax-bx)**2+(ay-by)**2)            

point
    var
        x
        y
    New(xx,yy)
        x = xx
        y = yy

triangle
    var
        point/a
        point/b
        point/c
    New(ax,ay,bx,by,cx,cy)
        a = new (ax,ay)
        b = new (bx,by)
        c = new (cx,cy)
    
    proc
        findArea()
            var
                lA = distance(b.x,b.y,c.x,c.y)
                lB = distance(c.x,c.y,a.x,a.y)
                lC = distance(a.x,a.y,c.x,c.y)
                p = (lA+lB+lC)/2
            return sqrt(p*(p-lA)*(p-lB)*(p-lC))

triangle
    proc
        pointInTriangle(point/p)
            var/A=findArea()  //Area of the triangle
    
            //We need to create mini triangles containing our point
            var/triangle
                ABP= new(a.x,a.y,b.x,b.y,p.x,p.y)
                BCP= new(b.x,b.y,c.x,c.y,p.x,p.y)
                CAP= new(c.x,c.y,a.x,a.y,p.x,p.y)
    
            //add the area of all the triangles
            //if they're more than the area of this triangle, point is not inside
            world<<"ABP: [ABP.findArea()] BCP: [BCP.findArea()] CAP: [CAP.findArea()]"
            var/sumA=ABP.findArea() + BCP.findArea() + CAP.findArea()
            world<<"Point: ([p.x], [p.y]) SumA: [sumA] A: [A]"
            if( sumA > A) return 0
            return 1


Results from the same tests you ran.
ABP: 0.928505 BCP: CAP: 2.29129
Point: (7, 7) SumA: 3.21979 A: 4.5
Yeah!
ABP: 1.22023 BCP: CAP: 3.26101
Point: (7, 8) SumA: 4.48124 A: 4.5
Yeah!
ABP: BCP: 2.55347 CAP: 1.00367
Point: (5, 7) SumA: 3.55715 A: 4.5
Yeah!
Jan 27 2008, 11:47 pm
You might be running into some floating-point issues - Most programming languages use something called 'floating point' representation for fractions. BYOND uses it for numbers >65535, <65535, or with a fractional component, I believe.

Floating point numbers have a few disadvantages, however - in particular, there's always some level of inaccuracy. 0.1, for example, cannot be represented exactly with a finite number of bits in a computer.

This leads to interesting problems when, for example, checking for equality. Just checking if two floats a and b are equal to each other:

if(a==b)

will likely fail under some circumstances when you want them to be considered equal. The solution? Check that they're the same within some small range of error:

if((a-b)<epsilon)

where 'epsilon' is a small number (Maybe 10**-9 or so).

This can also apply to > and < operators, at the boundaries. If you go:

if(a<b)
<br/> and a and b are very close, sometimes you might get false positives (or negatives).

The solution, again, involves epsilon:

if((a-b)<epsilon)

There's a bit of fiddliness here - there's always going to be inaccuracies, no matter what. It's a matter of what side you want the inaccuracy to be on - do you want false positives or false negatives?

If you want false negatives (occasionally saying points aren't in when they are), then just checking if a<b is suitable. If you want false positives (occasionally saying points are in when they aren't), then check if a-b < epsilon.
Jan 28 2008, 9:10 am (Edited on Jan 28 2008, 9:35 pm)
In response to Jp
I think you may be right. I've been thinking this might be the case. Of course, if that's true, then there are digits somewhere that are being stored but not displayed when output using the << operator.

I'll try your epsilon expression tonight and see if I can get it working that way. Thanks.

[UPDATE] I plugged in your epsilon code with a feather of 0.001 and it seems to be working beautifully now. I guess BYOND has a hard coded setting for how many decimal places it displays when using the << operator, even if more is actually being stored in the variable. Thanks for your help!