判断目标点是否在凸多边形区域

2025-05-08

无标签

目标点 $p$ 对凸多边形每个顶点之间建立一个向量 $vec$ （如： $\vec{v}_{p\to v_{1}}$ ），该向量与其对应的顶点的边 $edge$ （如： $v_{2}-v_{1}$ ）进行叉乘，得到一个叉积值。

若每个叉积值的符号都一样（都是正数/都是负数），则证明点在凸多边形内。

否则，则证明点不再凸多边形内。

1
bool Chunk::inChunk(Vector2 p)
2
{   int size = vertexs.size();
3
    for(int i = 0; i < size; ++i)
4
    {
5
        //假设凸多边形的边edge都是逆时针方向
6
        Vector2 edge = vertex[(i+1)%size]-vertex[i];
7
        Vector2 vec = vertex[i] - p;
8
        int result = cross(edge,vec);
9
        //若点在凸多边形内，得到的叉积值应都是正数
10
        if(sign(result) == 0)
11
            return false;
12
    }
13
    return true;