日誌2014-11-02 18:51

判斷點是否在三角形內

純整數、不含除法
//兩點是否在直線同一邊
bool sameSide(int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3){
    int a = y0 - y1;
    int b = x1 - x0;
    int c = x0 * y1 - x1 * y0;
    if( (a * x2 + b * y2 + c) * (a * x3 + b * y3 + c) > 0) return true;
    return false;
}
//點是否在三角形內
bool insideTriangle(int px, int py, int x0, int y0, int x1, int y1, int x2, int y2){
    if (sameSide(px,py,x0,y0,x1,y1,x2,y2)||
        sameSide(px,py,x1,y1,x2,y2,x0,y0)||
        sameSide(px,py,x2,y2,x0,y0,x1,y1)) return false;
    return true;
}