如何判断路线 L 和凹多边形 O 相交，并且效率的求算路线 L 在凹多边形 P 内部的距离
biggun · 2015-12-08 14:05:44 +08:00 · 2487 次点击这是一个创建于 3276 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目如题：
如何判断路线 L 和凹多边形 O 相交，并且效率的求算路线 L 在凹多边形 P 内部的距离
判断相交可以做到
我选择的是首先对多边形做一个 triangulation 。利用得到的三角形集合可以很快的判断路线和多边形是否相交。
卡在了求出相交部分，路线在多边形内部的距离。
求指点。或者给出可行算法也行。
 |
1
menc 2015-12-08 15:31:54 +08:00  1
从任意一边无穷远处沿一个方向前进，
得交点集合{P1,P2...Pn} 则，第 2k+1 个交点和第 2k+2 个交点间的距离和即为所求 |
 |
2
ossphil 2015-12-08 21:10:37 +08:00 1
路线可以简化成一系列点，即一系列直线的合集，然后可以判断每个点是否在多边形内部，计算出交点就可以知道路线 L 在多边形内部的距离了。
http://alienryderflex.com/polygon/ |
 |
3
hccbook 2015-12-09 09:16:22 +08:00
看你的要求有多高，低要求的话，可以尝试一下蒙特卡洛算法，或者其改进算法 MCMC
|
Select Language