如何判断路线 L 和凹多边形 O 相交，并且效率的求算路线 L 在凹多边形 P 内部的距离

[biggun]

####题目如题：
- 如何判断路线 L 和凹多边形 O 相交，并且效率的求算路线 L 在凹多边形 P 内部的距离

- 判断相交可以做到
- 我选择的是首先对多边形做一个 triangulation 。利用得到的三角形集合可以很快的判断路线和多边形是否相交。
- 卡在了求出相交部分，路线在多边形内部的距离。

求指点。或者给出可行算法也行。

[menc]

从任意一边无穷远处沿一个方向前进，
得交点集合{P1,P2...Pn}
则，第 2k+1 个交点和第 2k+2 个交点间的距离和即为所求

[ossphil]

路线可以简化成一系列点，即一系列直线的合集，然后可以判断每个点是否在多边形内部，计算出交点就可以知道路线 L 在多边形内部的距离了。
http://alienryderflex.com/polygon/

[hccbook]

看你的要求有多高，低要求的话，可以尝试一下蒙特卡洛算法，或者其改进算法 MCMC