围栏算法研究与实现

Publish: April 18, 2017 Category: 编程,代码分享 No Comments

实际应用中常用的解决方法。

1.1 方法选择

实现电子围栏的方法选择 判断点是否在电子围栏内/外,用数学来描述就是判断一个点是在多边形内/外部,为 了方便,这里的多边形默认为有向多边形,规定沿多边形的正向,边的左侧为多边形的外侧 域,即多边形边按顺时针方向遍历。比较常见的判断点与多边形关系的算法有射线法、点线判断法、夹角和法等[3],不过只有射线法可以正确用于凹多边形,其他 2 个只可以用于凸多 边形。

点线判断法 把多边形的每条边看作首尾相连的有向线段。如果一个点相对于多边形的每条边(有向 线段)的方向(左侧还是右侧)都相同,那么这个点就在这个多边形内部。这种方法只适用于凸多边形,而不适用于凹多边形。定义点在有向线段的一侧,定义有向线段(x1,y1),(x2,y2), 对于点(x, y)计算:

v = (x2-x1)*(y-y1) - (y2-y1)*(x-x1)

v=0 表示点在线段所在的直线上,v>0 表示点在线段的左侧,v<0 表示点在线段的右侧。 上面的计算式也可以表示比较斜率的大小:

 (y-y1)/(x-x1) > (y2-x1)/(x2-x1) 

阅读剩余部分...