射線法的優(yōu)化

• 1.射線法簡述
• • 具體處理
  • python代碼

1.射線法簡述

因為工作需要，所以需要判斷某個坐標(biāo)的點是不是在某個區(qū)域范圍（單個閉合多邊形）內(nèi)。經(jīng)過在網(wǎng)上搜索資料，發(fā)現(xiàn)射線法能解決我的問題，并且十分巧妙，記錄一下。
據(jù)說這個辦法也叫==奇偶規(guī)則法==，如果比較想一探究竟的話可以去了解一下，具體證明什么的我也無能為力，good luck。
原理：
1.如果一個點在一個多邊形內(nèi)部，那么以它為起始點，發(fā)射一條射線（任意方向），那么它至少會和一條邊相交，也就是有一個交點。如圖所示

2.如果點在多邊形內(nèi)部出發(fā)射線不止和一條邊相交，在不經(jīng)過端點和整條邊的情況下，一定和邊有奇數(shù)個交點（我也不知道怎么證明，但是畫了很多圖，確實是這么神奇。如果有大佬能證明再好不過了），看圖，有3個交點

3.如果經(jīng)過端點和邊需要單獨討論。
綜上，如果一個點在閉合多邊形內(nèi)部，那么它和多邊形的交點是奇數(shù)個。

具體處理

1.單個閉合多邊形需要端點都按順時針或者逆時針順序構(gòu)建。這是構(gòu)建多邊形的基礎(chǔ)，如果這一步出錯了，后面的都無法進(jìn)行
2.由于兩個點A(x1,y1)、B(x2,y2)形成的坐標(biāo)系方程是y=(y2(x-x1)+y1(x2-x))/(x2-x1),除數(shù)是x2-x1，如果A、B橫坐標(biāo)相同，則除數(shù)是0，為了避免這個問題，我們?nèi)∧繕?biāo)點沿y軸正半軸平行線做射線，就像上面畫的那樣，也為了偷個懶，代入目標(biāo)點的橫坐標(biāo)，得到連線和射線的交點縱坐標(biāo)y，如果交點縱坐標(biāo)大于目標(biāo)點縱坐標(biāo)，則必定相交，交點數(shù)+1，如果剛好相等，就在邊上，直接返回在多邊形內(nèi)部（方程可以自己求，萬一我錯了我就是罪人，畢竟好久不讀書了，勿噴）
3.如果射線經(jīng)過了一個端點，無論計算兩次還是1次都會出問題，如圖

統(tǒng)一按2個或者1個算都是錯的，所以處理方式是穿過兩個點中的較大（或者較小）x軸坐標(biāo)記一次交點，仍然是奇數(shù)次為圖形內(nèi)部，不信可以試試（反正我不會證明）（如果是從x軸發(fā)射射線，那就是取較大或者較小的y坐標(biāo)記錄交點）
4.經(jīng)過一條邊，也就是平行于y軸，這條邊不計算交點
5.剛好在邊上/就是端點，很簡單，就不說了
6.對于max(y1,y2)<y的線段，不進(jìn)行判斷，因為是向上去取射線，所以絕對不會有任何交點，加快速度
7.同理，對于max(x1,x2)<x或者min(x1,x2)>x的線段，不進(jìn)行判斷，因為線段是平行于y軸的，所以絕對不會與線段有任何交點，加快速度

python代碼

# 測試邊界樣例0.0，0.0;1.0,0.0;1.0,1.0;0.0,1.0 # 用;分割坐標(biāo)點，用,分割橫縱坐標(biāo) class Point:def __init__(self, lng, lat):try:self.lng = float(lng)self.lat = float(lat)except Exception as e:self.lng = 0self.lat = 0class Bound:def __init__(self, bounds, **kwargs):self.attribute = kwargspoints = bounds.split(';')points_list = list()for point in points:lng = float(point.split(',')[0])lat = float(point.split(',')[1])points_list.append(Point(lng, lat))self.bounds = points_listdef inrange(self, point: Point):if isinstance(point, Point):passelse:# print("請檢查傳入的點類型")raise TypeError("傳入類型應(yīng)該是Point類型而不是" + str(type(point)) + "類型")pos = 0inrange = Falsewhile pos < len(self.bounds):beg_point = self.bounds[pos]end_point = self.bounds[(pos + 1) % len(self.bounds)]# print(self.attribute['ywzm'],beg_point.lng,beg_point.lat,end_point.lng,end_point.lat)# 固定射線往y軸正半軸射出，則它只會與x軸坐標(biāo)區(qū)間包含該點的射線相交# 1.與端點連線線段相交（可能在連線上）if min(beg_point.lng, end_point.lng) < point.lng < max(beg_point.lng, end_point.lng): # 只要線段的x軸坐標(biāo)包含點坐標(biāo)就有可能相交，否則不可能，過濾掉if point.lat < max(beg_point.lat, end_point.lat): # 只要該點的y軸坐標(biāo)小于射線兩端點的任意一個y軸坐標(biāo)，則有可能相交# 構(gòu)建兩點的方程，判定目標(biāo)點的射線與線段的交點y軸坐標(biāo)是否在點上方，是則相交，否則不交if (end_point.lat * (point.lng - beg_point.lng) + beg_point.lat * (end_point.lng - point.lng)) / (end_point.lng - beg_point.lng) > point.lat:# print(beg_point.lng, beg_point.lat, end_point.lng, end_point.lat)inrange = not inrange# 在邊上就不執(zhí)行了，直接判定在內(nèi)部elif (end_point.lat * (point.lng - beg_point.lng) + beg_point.lat * (end_point.lng - point.lng)) / (end_point.lng - beg_point.lng) == point.lat:# print(beg_point.lng, beg_point.lat, end_point.lng, end_point.lat)inrange = Truebreak# print(inrange)# 2. 剛好就是端點或者經(jīng)過端點，則以穿過起始點坐標(biāo)為相交，終止點不交,起始點選擇為x軸坐標(biāo)小的點elif point.lng == beg_point.lng or point.lng == end_point.lng:# print(beg_point.lng, beg_point.lat, end_point.lng, end_point.lat)# 3.剛好線段與y軸平行if beg_point.lng == end_point.lng: # 與y軸平行不算，但是需要考慮是不是在點是不是在線段上或者端點if min(beg_point.lat, end_point.lat) <= point.lat <= max(beg_point.lat, end_point.lat): # 點在線段上跳出循環(huán)inrange = Truebreakelse:if point.lng == min(beg_point.lng, end_point.lng): # 穿過起始點記錄一次inrange = not inrange# print(inrange)pos += 1# print(inrange)return inrange

第一次寫，有問題請指正，有時間一起學(xué)習(xí)

總結(jié)

以上是生活随笔為你收集整理的射线法学习记录的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。