如何确定线段是否在多边形内部? [英] how to detemine if a line segment is inside of a polygon?

问题描述

我们有一条线段 L ，该线段由多边形中的两个点 定义，一个多边形 P 由4个或更多点定义，我需要一个算法确定 L 是否在 P 内?

we have a line segment L defined by two points from polygon and a polygon P define by 4 or more points, I need an algorithm determine if L is inside P?

线段必须完全在多边形内部，如果只是部分定义为外部.

The line segment must be completely inside the polygon, if only partly it will defined as outside.

例如，看下面的图片:

更多示例:

推荐答案

第1步:L是否越过P的任意边?如果是，则L不在P内.如果否，请参阅步骤2

Step 1: Is L crossing any edge of P? If yes, L is not inside P. If no, see step 2

第2步:L的中间M在哪里?如果M在P内，则L在P内.

Step 2: Where is the middle M of L? If M is inside P, L is inside P.

以防万一:: http://en.wikipedia.org/wiki /Point_in_polygon

编辑，更多说明:有两种情况:

• L穿过P的至少一个边缘.然后L至少部分地位于P的内部.
• L不与P的任何边相交.然后L处于外部或内部.并且由于整个L在外部或内部，因此足以测试L的任何点的位置(L的两端除外).测试点是在多边形的外部还是内部是一个经典问题(具有专用的Wikipedia页面).

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