确定线段是否位于多边形内 [英] Determining if segment lies within a polygon

问题描述

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

Given a concave polygon, how can I determine whether a segment(edge) connecting two vertices lies within the polygon? In picture below there is an edge(red) connecting two same vertices that weren't connected in original polygon. I have no idea how determine interior and exterior. Thank you for any help.

多边形示例

推荐答案

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

If the additional segment intersects any other segment of the polygon, it is partly inside and partly outside.

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

Otherwise take a point on the additional segment, for example its midpoint and check if it is inside or outside. To test if a point is inside, take any ray extending from it and count the number of intersections with polygon edges. If the number of intersections is odd, it is inside.

听起来很简单，但要准备好处理特殊情况，例如共线线或顶点处的交点.这就是使实施变得困难的原因.

Sounds simple, but be prepared to handle special cases like collinear lines or intersections at vertex points. That's what will make the implementation difficult.

这篇关于确定线段是否位于多边形内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！