射线法——判断一个点是否在多边形内部(适用于凸多边形和凹多边形)【关键原理解释+文字伪代码】

简介: 射线法——判断一个点是否在多边形内部(适用于凸多边形和凹多边形)【关键原理解释+文字伪代码】

问题介绍

给定一个点和一个多边形(由点集的点依次连接构成),需要判断该点是否在多边形的内部。


方法简述

要判断一个点是否在多边形内部,只需要从点出发,水平向右做一条射线,然后计算射线与多边形的交点数量。若交点数量为偶数,则点在多边形外部;若交点数量为奇数,则点在多边形内部。


计算交点数量

计算交点的方法主要有以下三种:

  1. 射线直接与某一条边相交(非边的端点)
  2. 射线与两条边的交点相交
  3. 射线与一条边有重合片段(边的斜率为0,且y轴坐标与射线的y轴坐标相等)


7a7a632cf5254086b207ec63cb03b1d2.png

图1 交点类型

要判断出上面的左拐、右拐情况,需要借助向量叉乘

图2 判断左右拐

一般多边形可以由一个点集合表示,点集合中的各个点按照顺序相连即可形成多边形



遍历过程

for (int i = 0; i < pointList.size(); i++) {
    //多边形线1(line2):pointI-pointIPlus1; 
    //多边形线2(line3):pointIPlus1-pointIPlus2;
    //多边形线3(line4):pointIPlus2-pointIPlus3
    Point pointI = pointList.get(i);
    Point pointIPlus1 = pointList.get((i + 1) % pointList.size());
    Point pointIPlus2 = pointList.get((i + 2) % pointList.size());
    Point pointIPlus3 = pointList.get((i + 3) % pointList.size());
    if(射线与line2相交){
        直接把相交点数+1
    }eles if(pointIPlus1在射线上面){
        if(pointIPlus2不在射线上面){
            判断是否满足图1的第二种情况,满足则交相交点+1
        }else{
            判断是否满足图1的第三种情况,满足则交相交点+1
        }
    }
}


注意点

图4 不可以+1的情况

目录
相关文章
|
4月前
|
算法
平面中判断点在三角形内算法(同向法)
平面中判断点在三角形内算法(同向法)
26 0
|
7月前
|
C++
[C++/PTA] 判断一个点是否在一个圆的内部
[C++/PTA] 判断一个点是否在一个圆的内部
79 0
|
算法 Java 索引
单元格法近似求解多边形最大内接矩形问题【思路讲解+java实现】
单元格法近似求解多边形最大内接矩形问题【思路讲解+java实现】
234 0
关于已知线段,如何求封闭图形轮廓的一些猜想
关于已知线段,如何求封闭图形轮廓的一些猜想
|
Java
判断顶点凹凸性、判断多边形的凹凸性、填充凹坑将凹多边形处理为凸多边形【java实现+原理讲解】
判断顶点凹凸性、判断多边形的凹凸性、填充凹坑将凹多边形处理为凸多边形【java实现+原理讲解】
260 0
判断顶点凹凸性、判断多边形的凹凸性、填充凹坑将凹多边形处理为凸多边形【java实现+原理讲解】
|
Java 索引
给定一个多边形的点集——判断所给点集的方向为顺时针方向还是逆时针方向【java实现+原理讲解】
给定一个多边形的点集——判断所给点集的方向为顺时针方向还是逆时针方向【java实现+原理讲解】
242 0
|
C++ 计算机视觉
C++使用opencv判断一个点是否在多边形之内
C++使用opencv判断一个点是否在多边形之内
201 0
|
算法
判断三角形的性质(直角或等腰)简便算法
判断三角形的性质(直角或等腰)简便算法
136 0