how to detemine if a line segment is inside of a 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?

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

for example look below picture:

few more examples:

回答1:

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

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

Just in case: http://en.wikipedia.org/wiki/Point_in_polygon

Edit, more explanations: There are two cases :

• L crosses at least one edge of P. Then L it at least partly inside P.
• L does not cross any edge of P. Then L is either outside or inside. And as the entire L is outside or inside, it is sufficient to test the position of any point of L (except the two ends of L). And testing if a point is outside or inside a polygon is a classic problem (that have a dedicated wikipedia page).

回答2:

If a line segment is completely inside a polygon, then there will be at least 1 polygon vertex on either sides of the line. See How to tell whether a point is to the right or left side of a line for finding which side a point is on.

UPDATE: However, the vice-versa may not be true. One should traverse all the polygon vertices in order starting from one end of the line segment. All vertices encountered in traversal from start to end of line segment should be on one side and the remaining should be on the other side.

The above will not be true if the line segment coincides with one of the edges of the polygon. In that case, there will be no vertex on one side of the line. However, in this case, the line is not lying completely inside the polygon either.