如何确定对角线是否在凹多边形内？

凹面(非凸面)多边形的对角线(对角线是连接不相邻顶点的线段)可以完全在多边形之内或之外(或者可以与多边形的边缘相交).如何确定它是否完全在多边形中？(没有多边形点测试的方法).

如果对角线与边缘至少有一个交点,则它部分地位于多边形中并且部分地位于多边形之外,但是,如果对角线没有与它们相交,则只有两种状态:它完全在多边形中或完全在多边形之外.

要确定它是在多边形内还是外面:

假设多边形的顶点逆时针排序.考虑位于名为P [i]的顶点上的对角线的一个端点(另一个端点是p [j]).然后,制作三个向量,其第一个点是p [i]:

V1:p [i + 1] - p [i]

V2:p [i-1] - p [i]

V3:p [j] - p [i]

当且当且我们逆时针从V1移动到V2时,当且仅当V3在V1和V2之间时,对角线完全在多边形中.

alt text http://www.freeimagehosting.net/uploads/1b97107f4a.jpg

逆时针从V1到V2时,如何判断V3是否介于V1和V2之间？去这里.

我用这种方法写了一个程序,它有效地工作.