2

I've got a simple 2D triangle. I've been searching how do I know if a given point belongs to that triangle. Here's the algorithm (I've found it here: How to determine if a point is in a 2D triangle?), which's very good and fast (according to other people):

float sign(int x0, int y0, int x1, int y1, int x2, int y2){
    return (x0 - x2) * (y1 - y2) - (x1 - x2) * (y0 - y2);
}

int ptintr(int sx, int sy, int x0, int y0, int x1, int y1, int x2, int y2){
    int b1, b2, b3;

    b1 = sign(sx, sy, x0, y0, x1, y1) < 0.0f ? 1 : 0;
    b2 = sign(sx, sy, x1, y1, x2, y2) < 0.0f ? 1 : 0;
    b3 = sign(sx, sy, x2, y2, x0, y0) < 0.0f ? 1 : 0;

    if((b1) == b2 && (b2 == b3))
        return 1;
    return 0;
}

I call this function inside draw_ftriangle():

void draw_ftriangle(SDL_Surface * s, int x0, int y0, int x1, int y1, int x2, int y2, unsigned color){
    int ymin = min(y0, min(y1, y2));
    int xmin = min(x0, min(x1, x2));
    int ymax = max(y0, max(y1, y2));
    int xmax = max(x0, max(x1, x2));

    draw_line(s, x0, y0, x1, y1, color);
    draw_line(s, x1, y1, x2, y2, color);
    draw_line(s, x0, y0, x2, y2, color);

    for(; ymin < ymax; ymin++)
        for(; xmin < xmax; xmin++)
            if(ptintr(xmin, ymin, x0, y0, x1, y1, x2, y2))
                put_pixel(s, xmin, ymin, color);
}

Here sx and sy is the given point's coordinates, and x0, x1, x2, y0, y1, y2 are the points of triangle. But this algorithm doesn't work. Whenever I give to this function a coordinates of a point and a coordinates of triangle's point, it always return false. Could anyone tell me if this algorithm is correct, or maybe I left some mistake here?

Community
  • 1
  • 1
Arnas
  • 229
  • 1
  • 15
  • Out of curiousity, what happens if you change "`< 0.0f`" to "`<= 0.0f`"? Or better, "`<= 0.0lf`"? – paulsm4 Oct 06 '12 at 19:07
  • You haven't shown how you call these functions. Assuming this code is correct (I personally don't know either way), it could be you're calling the function incorrectly. – Jeff Mercado Oct 06 '12 at 19:09
  • 2
    I tried it with ptintr(0,0,0,0,1,0,1,1) and it returned 1 for me. Perhaps you could supply a failing case? – Peter de Rivaz Oct 06 '12 at 19:10
  • I suggest a little bit of learning vector calculus… it is one of the simplest problems. The point is in the triangle, if the mysign(t1,p,t2), mysign(p,t3,t2) and mysign(t1,t3,p) are all positive. mysign(a,b,c) is the determinant of the (b-a,c-a) matrix. A determinant of an (V,W) matrix is V.x*W.y-V.y*W.x . – peterh Dec 04 '13 at 21:08
  • Once all is said about 2D inclusion of a point in a triangle, this will not be the most efficient way to colour a triangle pixel by pixel: you use decisions on the order of pixels in the triangle's area where it would suffice to bother with the pixels on its circumference. – greybeard Mar 01 '15 at 07:34

2 Answers2

1

I tried this algorithm with two inputs:

ptintr(3,2,1,1,3,4,4,1)) => returned 1

ptintr(2,3,1,1,3,4,4,1)) => returned 0

They are both correct.

I might be wrong, but you are testing min and max coordinates sampled from the (x,y) pool, which means they will all be on the contour of the triangle. The algorithm considers coordinates on the contour as not part of it.

ptintr(3,1,1,1,3,4,4,1)) => returns 0 because the point (3,1) is on the contour.

Try changing the < operators to <= in function ptintr.

Jay
  • 18,959
  • 11
  • 53
  • 72
Dragos Foianu
  • 9
  • 1
  • Well ymin holds the most upper point on y axis, and xmin is holding the most left value on x axis. Then you go down on y axis and you go right on x axis, so not all of the points are on contours of triangle, some of them should be inside a triangle. – Arnas Oct 06 '12 at 19:30
  • @Arnas Then find us a case where your code does not work. Report the exact values to us for which it does not work. – Bart Oct 06 '12 at 19:41
  • 1
    I tested it multiple times and it works correctly. The problem is with your xmin which is incremented but not reset. You never go into the second for loop a second time because xmin is already at xmax. – Dragos Foianu Oct 06 '12 at 19:47
1

Your loop only does the top line because xmin is not reset.

In other words, the first time through the inner x loop you will increase xmin until it becomes xmax. The second time you do the inner x loop, xmin is already xmax so nothing happens.

Try

int x;
for(; ymin < ymax; ymin++)
    for(x=xmin; x < xmax; x++)
        if(ptintr(x, ymin, x0, y0, x1, y1, x2, y2))
            put_pixel(s, x, ymin, color);
Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75