找回密码
 注册
Simdroid-非首页
查看: 181|回复: 3

[编程进阶] 如何判断平面上任意一点是否在凸多边形范围内?

[复制链接]
发表于 2011-8-20 23:09:28 | 显示全部楼层 |阅读模式 来自 浙江嘉兴
平面上已知一个凸包多边形,现有任意一点,

如何判断该点是否在凸多边形范围内?

http://mathworld.wolfram.com/ConvexHull.html
发表于 2011-8-24 23:33:27 | 显示全部楼层 来自 上海松江区
Simdroid开发平台
本帖最后由 eigen 于 2011-8-24 23:37 编辑

关于版主提出的这个问题我有两个想法,给大家抛砖引玉。如果有错误,请大家批评指正。

一. 几何方面:
1. 判断这个点P是否在这个平面凸多边形的边上。如果不是,就转到2;
2. 过这个点P引一条直线l, 判断直线l是否交于这个凸多边形的两条边。如果是,则设交点分别为Q,M,转到3;
3. 判断点P是否在线段QM的内部,如果是,则点P在这个凸多边形的内部。

二. 线性代数方面:
1. 设这个平面凸多边形的顶点分别是P_1,P_2,...,P_n,原点为O。判断向量OP是否能由向量组OP_1,OP_2,...,OP_n所线性表示。如果能,则转到2;
2. 判断以上线性表示的系数是否都在半闭半开区间[0,1)内。如果是,并且至少有2个系数不为0,则点P在这个凸多边形的内部。

评分

1

查看全部评分

回复 不支持

使用道具 举报

 楼主| 发表于 2011-8-25 09:47:47 | 显示全部楼层 来自 上海
看这个, http://demonstrations.wolfram.com/AmIInAPolygon/

但是这里面有些小 Bug .
回复 不支持

使用道具 举报

发表于 2011-8-25 14:14:39 | 显示全部楼层 来自 LAN
计算几何里最常用的方法是射线法。自该点向明显位于该多边形外部的一点做射线,判断该射线与多边形的交点数目,若为奇数即为在多边形内部,对非凸多边形也成立,算法复杂度为O(n),如果恰好通过顶点,要么考虑换个方向重新做射线,要么只考虑一条边。
回复 不支持

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|小黑屋|联系我们|仿真互动网 ( 京ICP备15048925号-7 )

GMT+8, 2024-3-29 17:33 , Processed in 0.036807 second(s), 15 queries , Gzip On, MemCache On.

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

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