计算几何相关内容，不过里边的实现仅供参考，实际跑起来是会有些问题的。

 

原理：海伦公式，2倍面积的行列式计算

*三角形面积公式行列式（海伦公式）
2*S=|p.x    p.y    1|
    |q.x    q.y    1|
    |s.x    s.y    1|
    */

面积为正代表s在p->q有向线段的左侧
 

结构体定义

struct Point {
    double x, y;
    bool extreme;
};

 in triangle

bool in_triangle(Point p, Point q, Point r, Point s) {
    return ToLeft(p, q, s) && ToLeft(q, r, s) && ToLeft(r, p, s);
}

 to left测试

bool ToLeft(Point p, Point q, Point s) {
    return Area2double(p, q, s) > 0;
}

Area的两种实现方法

int Area2(Point p, Point q, Point s) {
    return p.x*q.y + q.x*s.y + s.x*p.y
        - p.x*s.y - q.x*p.y - s.x*q.y;
}

double Area2double(Point p, Point q, Point s) {
    return p.x*q.y + q.x*s.y + s.x*p.y
        - p.x*s.y - q.x*p.y - s.x*q.y;
}

 

Area2()中，面积为0包含三种情况：数值太小；在线上，在右侧

实测Area2在数值比较小的时候会产生bug，数值太小需要改为浮点型

在线上的问题，如果是使用方法一致，在很多场景下可以忽略，但是如果你目的需要区分右侧和线上，可能会有问题，需要修改ToLeft的用法，或者补充一个ToRight。

 

 

 

 

 

https://github.com/huqinwei/cv_experiment/blob/main/pcl_test/ToLeft.cpp

https://github.com/huqinwei/cv_experiment.git