V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 3799 days ago, the information mentioned may be changed or developed.
题目如题：
如何判断路线 L 和凹多边形 O 相交，并且效率的求算路线 L 在凹多边形 P 内部的距离
判断相交可以做到
我选择的是首先对多边形做一个 triangulation 。利用得到的三角形集合可以很快的判断路线和多边形是否相交。
卡在了求出相交部分，路线在多边形内部的距离。
求指点。或者给出可行算法也行。
 |
1
menc Dec 8, 2015  1
从任意一边无穷远处沿一个方向前进，
得交点集合{P1,P2...Pn} 则，第 2k+1 个交点和第 2k+2 个交点间的距离和即为所求 |
 |
2
ossphil Dec 8, 2015 1
路线可以简化成一系列点，即一系列直线的合集，然后可以判断每个点是否在多边形内部，计算出交点就可以知道路线 L 在多边形内部的距离了。
http://alienryderflex.com/polygon/ |
 |
3
hccbook Dec 9, 2015
看你的要求有多高，低要求的话，可以尝试一下蒙特卡洛算法，或者其改进算法 MCMC
|
Select Language