光线投射算法（如何计算一个坐标点是否在一个多边形内）

一、如何计算一个坐标点是否在一个多边形内

从点开始，投射一条有方向，有方向，有方向，水平射线，与多边形的边相交的点有几个。奇数说明在图形内，偶数说明在图形外。

二、需要排除与图形边(即线段)相切，平行，不相交，线段为零，重叠情况详见 图形展示

三、实现

设需要判断的点为(x,y),线段点（x1,y1）(x2,y2)

1.排除以上情况，只需要保证在纬度上这个点在这条线段的两个点之间就ok。

(y1 > y) != (y2 > y)  或者

2.计算交点

x - （x2-x1）/(y2 - y1)*(y2- y)

image.png

上面公司就是交点的横坐标，如果交点的横坐标大于需要计算的点那就是有交点。不断的循环每一条边，最后计算交点的个数。图片这里就一个三角函数

image.png

的问题，数学再差也可以用初中的相似三角形计算

3.特殊例子

image.png

引用：判断点是否在多边形内的Python实现