光线投射算法（如何计算一个坐标点是否在一个多边形内）
2019-01-04 本文已影响0人
你值得拥有更好的12138
一、如何计算一个坐标点是否在一个多边形内
从点开始，投射一条有方向，有方向，有方向，水平射线，与多边形的边相交的点有几个。奇数说明在图形内，偶数说明在图形外。
二、需要排除与图形边(即线段)相切，平行，不相交，线段为零，重叠情况详见 图形展示
三、实现
设需要判断的点为(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
