|
|
如何判断点在多边形的内部？
关注者
39
被浏览
10,313
8 个回答
有个思路，先把多边形三角剖分，变成一堆三角形的组合，然后可以判断点是否在各个三角形内。（其实三角剖分应该算是解决方案的重点，可以用ear-clipping三角剖分）。然后判断点在三角形内又可以先算出点的双线性插值坐标（s,t）
P＝A+sV1＋tV2，注意到在P,A,V1,V2都已知的时侯这是个二元一次方程，用克拉默法则一步到位解出（s,t），注意三点不可以共线不然行列式为0。最后高中都学过一个论断就是如果一个点在三角形内那么s＋t≤1。那就可以用这条不等式判断点是否在三角形内。
P＝A+sV1＋tV2，注意到在P,A,V1,V2都已知的时侯这是个二元一次方程，用克拉默法则一步到位解出（s,t），注意三点不可以共线不然行列式为0。最后高中都学过一个论断就是如果一个点在三角形内那么s＋t≤1。那就可以用这条不等式判断点是否在三角形内。