声振论坛

 找回密码
 我要加入

QQ登录

只需一步,快速开始

查看: 3102|回复: 8

[其他相关] 如何判断一个点的位置,是否属于这个图形?

[复制链接]
发表于 2013-7-30 10:22 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?我要加入

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

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

haow.PNG
回复
分享到:

使用道具 举报

发表于 2013-7-30 12:15 | 显示全部楼层
本帖最后由 mokchie 于 2013-7-30 12:16 编辑

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

评分

1

查看全部评分

 楼主| 发表于 2013-7-30 15:04 | 显示全部楼层

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

发表于 2013-8-11 00:08 | 显示全部楼层
mxlzhenzhu 发表于 2013-7-30 15:04
谢谢,但是我回来和哥们讨论,被确认这本质是一个采样与分辨率的问题,不用搞这么复杂,用LMS VL的数据插 ...
没看懂甚含意? 可否说清楚些
 楼主| 发表于 2013-8-11 14:39 | 显示全部楼层
ChaChing 发表于 2013-8-11 00:08
没看懂甚含意? 可否说清楚些


这些点要是间距太大了,计算就会不精确;可以认为分辨率太低(间距大),就会损失掉无法挽回的信息,后面就麻烦了。
发表于 2013-9-17 08:11 | 显示全部楼层
图形学里,射线法
 楼主| 发表于 2013-9-19 00:01 | 显示全部楼层
人走茶不凉 发表于 2013-9-17 08:11
图形学里,射线法

你好,请问要计算那些虚线该怎么搞?求指导!【关键是里面有的是空心的!】
发表于 2013-9-19 07:58 | 显示全部楼层
mxlzhenzhu 发表于 2013-9-19 00:01
你好,请问要计算那些虚线该怎么搞?求指导!【关键是里面有的是空心的!】

虚线难道真的虚?那只不过是画成了虚线!
发表于 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。
您需要登录后才可以回帖 登录 | 我要加入

本版积分规则

QQ|小黑屋|Archiver|手机版|联系我们|声振论坛

GMT+8, 2024-12-23 09:36 , Processed in 0.074802 second(s), 23 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表