Triangle's inner point.

July 8, 2010 at 08:07 - by eelvex   |   no comments (Leave a comment)

Share on RedditShare on FacebookShare on Google+Tweet about this on TwitterShare on StumbleUponPrint this page

[ See the C code at bitbucket ]
[ See the diagram's code at bitbucket ]

Suppose you have a point P(x,y) and a triangle ABC defined by it's vertices: A(x_1,y_1), B(x_2, y_2), C(x_3, y_3). How can you tell if P is inside ABC?

One simple way to test that, is to compare triangle's areas: the area of the triangle ABC is equal to the sum of the smaller triangles formed by P only if P is an inner point. That is:

Inner point:
\textrm{E}(ABP) + \textrm{E}(CBP) + \textrm{E}(ACP) = \textrm{E}(ABC)
Not an inner point:
\textrm{E}(ABP) + \textrm{E}(CBP) + \textrm{E}(ACP) \neq \textrm{E}(ABC)

where the area of a triangle is simply: \frac{1}{2}|x_1y_2 + x_2y_3 + x_3y_1 - y_1x_2 - y_2x_3 - y_3x_1|

Testing with C and allegro

I used the code below for a quick "test" of the method. In this code, we first generate a random triangle. Then, we test if the mouse pointer (representing point P), is inside or outside that triangle. If it's in, we paint the triangle yellow(ish), if not, we paint it blue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <allegro.h>
#include <stdlib.h>
#include <time.h>


#define SWIDTH 640
#define SHEIGHT 480

BITMAP *buffer = NULL;

struct point {
    int x;
    int y;
};

struct triangle {
    struct point A, B, C;
};


double E(struct point A, struct point B, struct point C)
{
    int x1 = A.x, x2 = B.x, x3 = C.x;
    int y1 = A.y, y2 = B.y, y3 = C.y;
    return .5*abs(x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1);
}

int inner(struct triangle T, struct point P)
{
    if (E(T.A, T.B, P) + E(T.A, T.C, P) + E(T.B, T.C, P)  ==
            E(T.A, T.B, T.C))
        return 1;
    return 0;
}

void world(struct triangle T, int color)
{
    int x1 = T.A.x, x2 = T.B.x, x3 = T.C.x;
    int y1 = T.A.y, y2 = T.B.y, y3 = T.C.y;
    clear_bitmap(buffer);

    triangle(buffer, x1, y1, x2, y2, x3, y3, color);

    blit(buffer,screen, 0, 0, 0, 0, SCREEN_W, SCREEN_H);
}

int main(void)
{
    int pos;
    struct point P;
    struct triangle T;

    allegro_init();
    install_keyboard();
    install_mouse();
    show_os_cursor(MOUSE_CURSOR_ARROW);
    set_gfx_mode(GFX_AUTODETECT_WINDOWED, SWIDTH, SHEIGHT, 0, 0);

    buffer = create_bitmap(SWIDTH, SHEIGHT);

    srandom(time(0));
    T.A.x = random()%SWIDTH; T.A.y = random()%SHEIGHT;
    T.B.x = random()%SWIDTH; T.B.y = random()%SHEIGHT;
    T.C.x = random()%SWIDTH; T.C.y = random()%SHEIGHT;

    while(!key[KEY_ESC]) {
        rest(150);
        pos = mouse_pos;
        P.x = pos >> 16;
        P.y = pos & 0x0000ffff;
        if (inner(T,P))
            world(T, makecol(200,200,50));
        else
            world(T, makecol(50,50,200));
    }

    return 0;
}
END_OF_MAIN()
No tips yet.
Be the first to tip!
Like this post? Tip me with bitcoin!

1FCxajyLu6w8ndLMepoRP63g2sZMTfkxmK

Share on RedditShare on FacebookShare on Google+Tweet about this on TwitterShare on StumbleUponPrint this page
{ Tags: , , , }

no comments

RSS / trackback

respond

Real Time Analytics