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