CODEWITHSUNDEEP
c++algorithmmathpolygon
user3878881
user3878881

Reputation: 71

how to detemine if a line segment is inside of a polygon?

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:

click to view image

few more examples:

click to view image

Upvotes: 5

Views: 1806

Answers (2)

Fumidu
Fumidu

Reputation: 288

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).

Upvotes: 5

sray
sray

Reputation: 584

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.

Upvotes: -2

Related Questions