point inside 点在框内

判断一个点是否在一个图形内,而且考虑到计算效率,找到人家说的几种方法

  • 射线:从判断点向某个统一方向作射线,依交点个数的奇偶判断;
  • 转角:按照多边形顶点逆时针顺序,根据顶点和判断点连线的方向正负(设定角度逆时针为正)求和判断;
  • 夹角和:求判断点与所有边的夹角和,等于360度则在多边形内部。
  • 面积和:求判断点与多边形边组成的三角形面积和,等于多边形面积则点在多边形内部。

如果是矩形比较简单,直接判断四个点的范围,不能推广到多边,考虑到图形的凹凸就更复杂,考虑到程序需要直接拿来用罢了,

cv2.pointPolygonTest function finds the shortest distance between a point in the image and a contour. It returns the distance which is negative when point is outside the contour, positive when point is inside and zero if point is on the contour. In the function, third argument ismeasureDist. If it isTrue, it finds the signed distance. If false, it finds whether the point is inside or outside or on the contour (it returns +1, -1, 0 respectively).

cv2.pointPolygonTest(points, (i, j), False) >= 0

转角循环:

for ix, dt in enumerate(coor_list):      a = (dt[1][0]-dt[0][0])*(xy[1]-dt[0][1])-(dt[1][1]-dt[0][1])*(xy[0]-dt[0][0])      b = (dt[2][0]-dt[1][0])*(xy[1]-dt[1][1])-(dt[2][1]-dt[1][1])*(xy[0]-dt[1][0])      c = (dt[3][0]-dt[2][0])*(xy[1]-dt[2][1])-(dt[3][1]-dt[2][1])*(xy[0]-dt[2][0])      d = (dt[0][0]-dt[3][0])*(xy[1]-dt[3][1])-(dt[0][1]-dt[3][1])*(xy[0]-dt[3][0])      if ((a>=0 and b>=0 and c>=0 and d>=0) or (a<=0 and b<=0 and c<=0 and d<=0)): return ix  return -1

https://www.jianshu.com/p/ba03c600a557

https://www.docs.opencv.org/3.0-alpha/doc/py_tutorials/py_imgproc/py_contours/py_contours_more_functions/py_contours_more_functions.html

https://www.jianshu.com/p/ba03c600a557

另外引用蒙特卡洛算法的一个例子:

一个古人要求一个图形的面积,他把图形画在一块方形布上,然后找来一袋豆子,然后将所有豆子洒在布上,落在图形内豆子的重量比上那块布上所有豆子的重量再乘以布的面积就是他所要求的图形的面积。  两种编程思路来计算这个面积: 

方法一:将整个坐标轴看成一个边长为12的正方形,然后均匀的这个正方形分成N(N的大小取决于划分的步长)个点,然后找出N个点中有多少个点是属于阴影部分中,假设这个值为k,则阴影部分的面积为:k/N12^2 

方法二:将整个坐标轴看成一个边长为12的正方形,然后在(-6,6)中随机出N(N越大越好,至少超过1000)个点,然后找出这N个点中有多少个点在阴 影区域内,假设这个值为k,则阴影部分的面积为:k/N12^2。然后重复这个过程100次,求出100次面积计算结果的均值,这个均值为阴影部分面积。 

对比分析:以上两个方法都是利用蒙特卡罗方法计算阴影部分面积,只是在处理的细节有一点区别。前者是把豆子均匀分布在布上;后者则是随机把豆子仍在布上。就计算结果的精度而言,前者取决点的分割是否够密,即N是否够大;后者不仅仅通过N来控制精度,因为随机的因素会造成单次计算结果偏高和偏小,所以进行反复多次计算最后以均值来衡量阴影部分面积