三角形の内外判定(2D)

C++

id:melponからもらったコードをメモ。


http://codepad.org/Nd0zKyFy

struct point
{
    point() : x(0), y(0) { }
    point(double x_, double y_) : x(x_), y(y_) { }
    double x, y;
};
point operator-(const point& a, const point& b) { return point(a.x - b.x, a.y - b.y); }
point operator+(const point& a, const point& b) { return point(a.x + b.x, a.y + b.y); }

typedef point vector2d;

// 外積を求める
double cross(const vector2d& a, const vector2d& b)
{
    return a.x * b.y - a.y * b.x;
}

// 点 p が反時計回りの三角形 abc の内側にあるかどうか判定
bool point_in_triangle(const point& p, const point& a, const point& b, const point& c)
{
    // p が ab の右側にあれば三角形の外側にある
    if (cross(p - a, b - a) < 0.0) return false;
    // p が bc の右側にあれば三角形の外側にある
    if (cross(p - b, c - b) < 0.0) return false;
    // p が ca の右側にあれば三角形の外側にある
    if (cross(p - c, a - c) < 0.0) return false;
    return true;
}

#include <cassert>
#include <iostream>

int main()
{
    assert(point_in_triangle(point(0, 0),
        point(-1, -1), point(0, 1), point(1, -1)));
    assert(!point_in_triangle(point(-2, 0),
        point(-1, -1), point(0, 1), point(1, -1)));
    std::cout << "success" << std::endl;
    return 0;
}