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?

4

2 に答える 2

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.

于 2012-10-06T19:23:46.353 に答える
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);
于 2012-10-06T19:41:47.387 に答える