问题介绍
给定一个点和一个多边形（由点集的点依次连接构成），需要判断该点是否在多边形的内部。
方法简述
要判断一个点是否在多边形内部，只需要从点出发，水平向右做一条射线，然后计算射线与多边形的交点数量。若交点数量为偶数，则点在多边形外部；若交点数量为奇数，则点在多边形内部。
计算交点数量
计算交点的方法主要有以下三种：
- 射线直接与某一条边相交（非边的端点）
- 射线与两条边的交点相交
- 射线与一条边有重合片段（边的斜率为0，且y轴坐标与射线的y轴坐标相等）
图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的情况
