PTT數位生活區 / Python

[問題] 點落在哪4個點中間

看板Python作者 (哭馬 <(￣︶￣)/)時間5年前 (2020/04/16 17:09), 5年前編輯推噓12(12推 0噓 30→)
留言42則, 9人參與, 5年前最新討論串1/1
假設我有100個不規則的離散點 已知他們的坐標為[x1, y1], [x2, y2], ......, [x100, y100] 現在我丟一個點P[xp, yp] 有什麼現成的函式可以知道P點是落在哪4個點中間呢(假如有落在某4點中間) 若沒有的話要怎麼去實作這件事呢 謝謝大家幫忙 Q_Q -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.163.131.156 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1587028183.A.704.html
推
04/16 18:06, 5年前 , 1F
建議你先釐清一下數學上的問題 你的狀況拿最外圍四個點不
04/16 18:06, 1F
→
04/16 18:08, 5年前 , 2F
就可以判斷了 另外三個點就可以圍出一塊面積 為什麼四個
04/16 18:08, 2F
→
04/16 18:08, 5年前 , 3F
點中間才是你要的
04/16 18:08, 3F
抱歉沒說明清楚 其實是想做雙線性內差 所以是想找出P點「最鄰近包圍它的4個點」這樣
推
04/16 19:12, 5年前 , 4F
1.你有的100個點是有規則排列的嗎?
04/16 19:12, 4F
→
04/16 19:13, 5年前 , 5F
2.如果有規則，建議先造一個array，dimension是最大
04/16 19:13, 5F
→
04/16 19:14, 5年前 , 6F
的範圍x_min, x_max, y_min, y_max
04/16 19:14, 6F
→
04/16 19:15, 5年前 , 7F
3. array裡面塞值就依照順序編號，最後查詢array中P
04/16 19:15, 7F
→
04/16 19:15, 5年前 , 8F
這個位置的值，對應過去就可以知道在哪四點中間。
04/16 19:15, 8F
→
04/16 19:17, 5年前 , 9F
4.這個方法會在一開始造array時犧牲速度，之後就比較
04/16 19:17, 9F
→
04/16 19:17, 5年前 , 10F
快可以讀取
04/16 19:17, 10F
100個點沒有規則欸 而且P點不在那100點中 這樣還有辦法找出「最鄰近包圍P4個點」嗎 ※ 編輯: kumaHL (39.9.107.175 臺灣), 04/16/2020 20:14:11
→
04/16 20:27, 5年前 , 11F
最單純就k-neighbor,k=4
04/16 20:27, 11F
推
04/16 20:46, 5年前 , 12F
k-nearst neighbor不一定包含那一點吧，放向也要看
04/16 20:46, 12F
→
04/16 20:57, 5年前 , 13F
掃一遍 array，p當原點把每個點分成四個象限取最近點
04/16 20:57, 13F
→
04/16 20:58, 5年前 , 14F
每個象限各自取最近點
04/16 20:58, 14F
推
04/17 03:45, 5年前 , 15F
先排序再找p落在哪個區間？
04/17 03:45, 15F
推
04/17 12:42, 5年前 , 16F
你的座標是二維且離散的，不能就用距離來算嗎？只有
04/17 12:42, 16F
→
04/17 12:42, 5年前 , 17F
一百個點就算一百次距離，去最小的四個距離就是答案
04/17 12:42, 17F
→
04/17 12:42, 5年前 , 18F
了吧
04/17 12:42, 18F
推
04/17 13:13, 5年前 , 19F
樓上，他要的是最近「而且包圍」P的四個點
04/17 13:13, 19F
推
04/17 13:16, 5年前 , 20F
我的想法是可以先找出最近且包圍的三個點（相對容易），再
04/17 13:16, 20F
→
04/17 13:16, 5年前 , 21F
從剩下的點裡面找出第四個點符合要求
04/17 13:16, 21F
→
04/17 13:18, 5年前 , 22F
雖然沒進行證明，不過猜想最近四包圍點中的其中三個應該就
04/17 13:18, 22F
→
04/17 13:19, 5年前 , 23F
是最近三包圍點，直覺要證明應該也不難
04/17 13:19, 23F
推
04/17 14:19, 5年前 , 24F
要做雙線性內差 資料點應該要為在一個矩形上
04/17 14:19, 24F
→
04/17 14:20, 5年前 , 25F
但你的資料是不規則的離散點 我建議是看一下
04/17 14:20, 25F
→
04/17 14:20, 5年前 , 26F
Delaunay triangulation或是其他空間內差方法
04/17 14:20, 26F
→
04/17 14:22, 5年前 , 27F
修改一下第一行 資料要位在矩形的四個端點
04/17 14:22, 27F
推
04/17 14:37, 5年前 , 28F
@jigfopsda 你的方法沒辦法，因為4點可以只落在其中兩個象
04/17 14:37, 28F
→
04/17 14:38, 5年前 , 29F
限就包圍住原點了
04/17 14:38, 29F
推
04/17 15:26, 5年前 , 30F
要先定義最鄰近是什麼意思 面積最小 還是四點與p距離加起來
04/17 15:26, 30F
→
04/17 15:27, 5年前 , 31F
最小
04/17 15:27, 31F
推
04/28 18:06, 5年前 , 32F
以下土炮法給你參考
04/28 18:06, 32F
→
04/28 18:06, 5年前 , 33F
一，4點兩兩連線共有6條，先實作一個判斷兩點在線段同側
04/28 18:06, 33F
→
04/28 18:06, 5年前 , 34F
的函數
04/28 18:06, 34F
→
04/28 18:06, 5年前 , 35F
二，統計此四邊形沒連線的剩餘兩點在線的同側次數
04/28 18:06, 35F
→
04/28 18:06, 5年前 , 36F
3次代表凹四邊形，4次代表凸
04/28 18:06, 36F
→
04/28 18:06, 5年前 , 37F
三，凸的話，第五個點在這4次時與其他2點在同側，代表在
04/28 18:06, 37F
→
04/28 18:06, 5年前 , 38F
凸四邊形內
04/28 18:06, 38F
→
04/28 18:06, 5年前 , 39F
四，凹的話，請先分辨鈍角及其對角，第五點和剩餘兩點要
04/28 18:06, 39F
→
04/28 18:06, 5年前 , 40F
在鈍角頂點構成的線（2條）在同側，且在頂點構成的線（2
04/28 18:06, 40F
→
04/28 18:06, 5年前 , 41F
條）時，與頂點同側
04/28 18:06, 41F
推
04/28 18:22, 5年前 , 42F
若不想自己做，用matplotlib的Path.contains_points即可
04/28 18:22, 42F
‣ 更多 kumaHL 的文章
文章代碼(AID): #1Uc23NS4 (Python)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 kumaHL 的文章
文章代碼(AID): #1Uc23NS4 (Python)