mxlzhenzhu 发表于 2013-7-30 10:22

如何判断一个点的位置，是否属于这个图形？

江湖救急，请帮忙想想：
问题是这样的，有一个平面图形【可以看成是某岛国的国土】，实际上对它的已知信息只知道它是由许多点构成，而且这些点的分布规律几乎是均匀分布的，但是坐标并没有其他规律可循，另外这些点“离散这个图形”足够精细；现在要判断，任意给定一个点的坐标（可以看成是经度和纬度），问是否这个点落在这个几何图形内部？

如下图所示，白色部分全部都是“不属于这个图形区域”，而绿色部分则“属于这个图形区域”，求算法。


mokchie 发表于 2013-7-30 12:15

本帖最后由 mokchie 于 2013-7-30 12:16 编辑

xl可以试一下Delaunay三角划分算法，根据点集将图形区域进行三角网格划分，再用这些小三角判断你的点是否在区域内。最基本的Delaunay算法是划分凸区域的，但可以稍加改进就能处理非凸区域。matlab有现成的Delaunay划分功能。

mxlzhenzhu 发表于 2013-7-30 15:04

mokchie 发表于 2013-7-30 12:15 static/image/common/back.gif
xl可以试一下Delaunay三角划分算法，根据点集将图形区域进行三角网格划分，再用这些小三角判断你的点是否在 ...

谢谢，但是我回来和哥们讨论，被确认这本质是一个采样与分辨率的问题，不用搞这么复杂，用LMS VL的数据插值算法就可以搞定。

ChaChing 发表于 2013-8-11 00:08

mxlzhenzhu 发表于 2013-7-30 15:04 http://forum.chinavib.com/static/image/common/back.gif
谢谢，但是我回来和哥们讨论，被确认这本质是一个采样与分辨率的问题，不用搞这么复杂，用LMS VL的数据插 ...没看懂甚含意? 可否说清楚些

mxlzhenzhu 发表于 2013-8-11 14:39

ChaChing 发表于 2013-8-11 00:08 http://forum.chinavib.com/static/image/common/back.gif
没看懂甚含意? 可否说清楚些

这些点要是间距太大了，计算就会不精确；可以认为分辨率太低（间距大），就会损失掉无法挽回的信息，后面就麻烦了。

人走茶不凉 发表于 2013-9-17 08:11

图形学里，射线法{:{26}:}

mxlzhenzhu 发表于 2013-9-19 00:01

人走茶不凉 发表于 2013-9-17 08:11 static/image/common/back.gif
图形学里，射线法

你好，请问要计算那些虚线该怎么搞？求指导！【关键是里面有的是空心的！】

人走茶不凉 发表于 2013-9-19 07:58

mxlzhenzhu 发表于 2013-9-19 00:01 static/image/common/back.gif
你好，请问要计算那些虚线该怎么搞？求指导！【关键是里面有的是空心的！】

虚线难道真的虚？那只不过是画成了虚线！

Rainyboy 发表于 2013-11-15 03:46

也就是说，已知的是一些（很多）属于图形的坐标点(xi,yi,zi),i=0,1,,,,N，然后想要对给出的点c = (x0,y0,z0)判断，点c是否在图形的内部？

我想，有一个很笨的算法，出发点就是，如果点c在图形的内部，那么在足够近的距离delta_d内应该有图形的内部点，那么就计算所有点到c的距离，求出最小距离d_min,如果
dmin > delta_d 就可以认为点c在图形的外部。

delta_d的确定挺重要，既然已经说了图形采样点的分布几乎是均匀的，那么可以用采样点之间的平均最短距离作为 delta_d。
页: [1]
查看完整版本: 如何判断一个点的位置，是否属于这个图形？