How to find whether the line is inside the polygon or outside.

Question

I have a polygon

How can i prove whether the black color line lies outside the polygon or inside the polygon .

Given the coordinates of the black line and all the vertices of the polygon.

Answer 1

If we have an $n$ points on a plane and we know their coordinates we can easily check whether given line cuts the polygon. So first here's explanation why this method works. Let say we have $n$ point on a plane, we can connect them in the way we like, but with one restriction that no two sides of the polygon cut each other. Then choose an arbitrary point and connect it with every other point. And at last draw a convex polygon, such that the original polygon is inscribed in it.

So in the picture: $ABCDEFG$ is the polygon we want to check if certain line cuts it, WLOG $B$ is our arbitrary point and $ABDEF$ is the convex polygon.

If a line cuts through $ABDEF$, the it also cuts $ABCDEFG$ and vice versa. Because if the line cuts the polygon the it will have one "penetration" and one "exit" point. Now we've reduced the polygon to a convex one.

We can now use the fact that if a line cuts a convex polygon then it also cuts at least one of the its diagonals or another line that cuts it inside the polygon.

As I said earlier using the slope formula we can obtain equation for any line ( because we don't know which point is a vertex of the convex polygon we find every possible segment no matter if its a side or a diagonal).

We know that two line intersect each other, unless they are parallel, but we are interested in a intersection in between the defining points of the segment.

To find if the intersection happens in the segment, do the following. For example use the segment $BC$ we already know the equation of the line that passes through it, so we find the intersection point with the line we want to know if it cuts the polygon. Let denote that point as $X$. Using distance formula find the length of the segments $BC, BX, CX$. If the following equation is satisfied then the lines intersect at segment $BC$:

$$|BX| + |CX| = |BC|$$

If it's true for one segment then you can stop and that means that the line cuts the polygon.