[发明专利]一种夹角和法结合叉乘法判定点与任意多边形位置关系方法

摘要

本发明公开了一种夹角和法结合叉乘法判定点与任意多边形位置关系方法，按顺序遍历封闭的多边形顶点，当遍历没结束时计算判定点与顶点的方位角；通过减去前一个顶点的方位角(即方位角差)，得到夹角值，夹角值取绝对值；夹角不会大于180°，当大于180°进行处理夹角值等于360°减去上一步骤得到的夹角值；判定点与组成夹角的两个顶点向量进行叉乘计算。叉乘大于零时，夹角方向为正；不大于零时，夹角方向为负；夹角和计算按夹角方向进行加减，正时加，负时减；遍历结束时，当夹角和为360°，则判定点在多边形内；不为360°时，则判定点在多边形外。本发明通过增加叉乘法来判断夹角的方向，保证了判别点与任意多边形位置关系临界情况的判定。

主权项

一种夹角和法结合叉乘法判定点与任意多边形位置关系方法，其特征在于，设P＝{p1，p2，…，pn，p1}是一个顶点为pi(xi，yi)，i＝1，2，…，n的任意多边形，Pt是一个判定点；PtPi为连接pt和pi的诸向量，αi表示向量PtPi到PtPi+1的夹角；计算向量PtPi的方位角βi，PtPi+1的方位角βi+1；夹角αi由方位角之差来计算：αi＝|βi+1‑βi|；因αi(‑180°＜αi≤180°)，当αi＞180°时，αi＝360°‑αi；通过Pt与PiPi+1叉乘判断夹角方向，大于零时夹角αi方向为正，不大于零时夹角αi方向为负；计算夹角和，当夹角和等于360°时，点在多边形内；夹角和等于0°时，点在多边形外。