5
$\begingroup$

I have a polygon enter image description here

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.

$\endgroup$
6
  • $\begingroup$ If you know the coordinates of all vertices of the polygon, doesn't mean you know it's shape. Beacuse there are many ways to connect the vertices and as much as different shapes. $\endgroup$
    – Stefan4024
    Sep 28 '13 at 10:09
  • $\begingroup$ But in this case i know the shape and the coordinates are according to it. $\endgroup$ Sep 28 '13 at 10:17
  • $\begingroup$ is there any concept for proving this? $\endgroup$ Sep 28 '13 at 10:18
  • $\begingroup$ Do you want a general solution or a solution just for this problem? $\endgroup$
    – Stefan4024
    Sep 28 '13 at 10:26
  • $\begingroup$ this problem was for an example.Is there any general solution? $\endgroup$ Sep 28 '13 at 10:31
1
$\begingroup$

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.

diagram

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.

$\endgroup$
1
  • 2
    $\begingroup$ This does not answer the question at all... far from it. "If a line cuts through ABDEF, then it also cuts ABCDEFG and vice versa" That might be true for a line but not even remotely true for a segment. And by looking at the image in the question it is extremely obvious that the question is about a segment not a line. Sure, the OP didn't use the proper terms, but it's still fairly obvious. Examples: The segment [[-3, 2], [-2, 2]] cuts ABDEF but not ABCDEFG. Similarly, the segment [[-2, 1], [-1, 1]] cuts ABCDEFG but not ABDEF. $\endgroup$
    – Dolma
    Oct 4 '18 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.