作者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/cn.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