/*
* Test if a point is inside a triangle.
* Julian Saknussemm
*
* Given three points of a triangle, and another arbitrary 
*    point this program determines if that point lies
*    inside the triangle.
*
* This is determined by satisfying the following rule:
* A point P(x,y) is inside triangle A(x0,y0), B(x1,y1), C(x2,y2)
* iff
* P is on the same side of the line AB as C
* P is on the same side of the line BC as A
* and
* P is on the same side of the line AC as B
*
* A special case exits for a vertical line (inf gradient) 
*   when testing the side of the line
*/
 
#include <stdio.h>
#include <stdlib.h>
 
#define TRUE 1
#define FALSE 0
 
#define OVER_LINE 1
#define ON_LINE 0
#define UNDER_LINE -1
 
#define NECESSARY_INPUTS 8
 
int positionCheck (double px, double py,
                   double m, double b);
int sameSideCheck (double px, double py,
                   double m, double b,
                   double lx,double ly);
int triangleTest (double x0, double y0,
                  double x1, double y1,
                  double x2, double y2,
                  double px, double py);
 
 
 
 
int main(int argc, char* argv[]) {
    //x0, y0, x1, y1, x2, y2: respective points of triangle
    //px, py: point being tested
    double x0;
    double y0;
    double x1;
    double y1;
    double x2;
    double y2;
 
    double px;
    double py;
 
    int inputAmount = 0;
 
    //get input
    printf("Triangle Vertex A (x,y): ");
    inputAmount += scanf("%lf,%lf", &x0,&y0);
    printf("Triangle Vertex  B (x,y): ");
    inputAmount += scanf("%lf,%lf", &x1,&y1);
    printf("Triangle Vertex  C (x,y): ");
    inputAmount += scanf("%lf,%lf", &x2,&y2);
    printf("Test Point (x,y): ");
    inputAmount += scanf("%lf,%lf", &px,&py);
 
    if(inputAmount != NECESSARY_INPUTS) {
        //print error
        printf("Incorrect input\n");
    } else {
        // print answer
        if(triangleTest(x0, y0, x1, y1, x2, y2, px, py)) {
            printf("Point (%.2lf,%.2lf) is inside the triangle.\n", px, py);
        } else {
            printf("Point (%.2lf,%.2lf) is outside the triangle.\n", px, py);
        }
    }
 
    return EXIT_SUCCESS;
}
 
int triangleTest(double x0, double y0,
                 double x1, double y1,
                 double x2, double y2,
                 double px, double py) {
 
    //result after testing lines
    int line1Result;
    int line2Result;
    int line3Result;
 
    // mab = gradient from point (xa, xb) to (xb, yb)
    double m01;
    double m02;
    double m12;
 
    // Equation used:
    // b: y - y1 = m(x - x1) where x = 0
    double b01;
    double b02;
    double b12;
 
    // Gradient Formula
    m01 = (y1 - y0) / (x1 - x0);
    m02 = (y2 - y0) / (x2 - x0);
    m12 = (y2 - y1) / (x2 - x1);
 
    b01 = m01 * -x1 + y1;
    b02 = m02 * -x2 + y2;
    b12 = m12 * -x2 + y2;
 
    // vertical line checks
    if (x1 == x0) {
        line1Result = ((px <= x0) == (x2 <= x0));
    } else {
        line1Result = sameSideCheck(px, py, m01, b01, x2, y2);
    }
 
    if (x1 == x2) {
        line2Result = ((px <= x2) == (x0 <= x2));
    } else {
        line2Result = sameSideCheck(px, py, m12, b12, x0, y0);
    }
 
    if (x2 == x0) {
        line3Result = ((px <= x0) == (x1 <= x0));
    } else {
        line3Result = sameSideCheck(px, py, m02, b02, x1, y1);
    }
 
    return (line1Result && line2Result && line3Result);
}
 
// test if two points lie on the same side of a line
int sameSideCheck(double px, double py,
                  double m, double b,
                  double tx, double ty) {
 
    //ty, tx: point of triangle
    int result = FALSE;
    if (positionCheck(px, py, m, b) == positionCheck(tx, ty, m, b)) {
        result = TRUE;
    }
    return result;
}
 
int positionCheck(double px, double py, double m, double b) {
    int result;
    if(py < m * px + b) {
        result = UNDER_LINE;
    } else if (py == m * px + b) {
        result = ON_LINE;
    } else {
        result = OVER_LINE;
    }
    return result;
}

Download file: inside.c (3.9 KB)

Oscar Duretto – edited 10 years ago – history