确定线段是否位于多边形内

Question

给定一个凹多边形，如何确定连接两个顶点的线段（边）是否在多边形内？在下图中，有一条边（红色）连接两个在原始多边形中未连接的相同顶点。我不知道如何确定内部和外部。感谢您的帮助。

Example of polygons

Answer 1

如果附加线段与多边形的任何其他线段相交，则它部分在内部，部分在外部。

否则在附加线段上取一个点，例如它的中点，并检查它是在内部还是外部。要测试一个点是否在内部，取任何从它延伸的射线并计算与多边形边的交点数。如果交点的个数是奇数，就是在里面。

听起来很简单，但要准备好处理共线或顶点相交等特殊情况。这将使实施变得困难。