今天讲如何判断一个点是否在一个多边形内部,先看demo:

    判断点在多边形的内部还是外部

    上图中横线和竖线的交点表示我们要测试的点,移动右边和下边的滚动条,调整横线和竖线的位置。要被测试的是一个中间带有空心的不规则形状,中间的空心属于外面,画虚线的部分才属于这个不规则形状的内部。

    相交个数法

    这种方法的主要思想就是判断这个点向右横切不规则图形的交点的个数:

    如果向右横切交点的个数为奇数,那么表示在图形的内部;如果交点的个数为偶数,那么表示在图形的外部。

    具体程序计算的时候,我们就遍历每一条边,计算那条边是否和点的右射线有交点,如果有,那我们就加一个,现在看看如何计算那个交点:

    这里需要注意的是,边的数组一定要能形成一个封闭的多边形,也就是从起点出发最后一定要能够回到起点。并且这个计算方法适用于凸变形或者凹变形,或者中间带有空洞的不规则形状。

    凸边同一方向

    这种计算方式只适用于凸边形,这种的意思就是说在凸边形中如果顺时针遍历边,那么内部点在所有边的右边;如果逆时针遍历边,那么内部点在边的左侧。

    现在我们来看一个顺时针在右侧的情况,看看这两条线的斜率的关系:

    需要注意的是我们这里的坐标和数学中的坐标是不太一样的,这里的y轴是向下的,那么p在p0p1的右侧的话,那么p0p的斜率肯定是大于p0p1的。

    这样的话我们可以总结为,遍历所有的边,计算p0p和p0p1的斜率,如果在顺时针遍历的情况下,如果都是k(p0p)-k(p0p1)都是大于0的话,那么就是内部店;如果有一个小于0,那么就是外部点,如果有一个为0的,那么表示在线上。

    凸边形判断点内外侧

    回到顶部
    我要评论

    所有评论

      相关文章