point inside 點在框內
- 2020 年 3 月 13 日
- 筆記
判斷一個點是否在一個圖形內，而且考慮到計算效率，找到人家說的幾種方法
- 射線：從判斷點向某個統一方向作射線，依交點個數的奇偶判斷；
- 轉角：按照多邊形頂點逆時針順序，根據頂點和判斷點連線的方向正負（設定角度逆時針為正）求和判斷；
- 夾角和：求判斷點與所有邊的夾角和，等於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.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來控制精度，因為隨機的因素會造成單次計算結果偏高和偏小，所以進行反覆多次計算最後以均值來衡量陰影部分面積
