0
$\begingroup$

Two Dimensions.

I have a list of N points which are the corners of an irregular, non-intersecting polygon in clockwise order.

For any other point, is it inside or outside the polygon?

Is there an algorithm for this?

$\endgroup$
  • 1
    $\begingroup$ Draw a line segment connecting the given point to another point far out (clearly outside the polygon for example because one of its coordinates is off the scale). Then calculate how many sides of the polygon this point intersects with. If an odd number, then the point was inside. If an even number, then it is outside. $\endgroup$ – Jyrki Lahtonen Mar 13 '16 at 11:16
  • $\begingroup$ Smart! So basically check each side for intersection and keep a tally. This is probably going to annoy you mathematicians, but what is the formula for if a segment intersects another segment? $\endgroup$ – Lorry Laurence mcLarry Mar 13 '16 at 11:28
  • 1
    $\begingroup$ The proper algorithm partly depends on what you mean by "inside or outside" the polygon. This is clear for a simple, non-self-intersecting polygon, due to the Jordan curve theorem, but if the polygon can intersect itself there are some strange cases. Please clarify: do you mean simple (non-self-intersecting) polygons? If not, clarify what "inside" means. $\endgroup$ – Rory Daulton Mar 13 '16 at 11:30
  • $\begingroup$ Oh, yeah. I meant a non-intersecting polygon. but one that can have obtuse or acute angles. $\endgroup$ – Lorry Laurence mcLarry Mar 13 '16 at 11:34
  • $\begingroup$ The segment $L$ from the point of interest $P_0=(x_0,y_0)$ to that far out point $P=(x,y_0)$ (with $x$ very larger) can be chosen to be parallel to $x$-axis. Then for another line segment connecting $P_1=(x_1,y_1)$ to $P_2=(x_2,y_2)$ can intersect $L$ only if $y_1$ and $y_2$ are on opposite sides of $y_0$. Only when this is the case will you do need to do a bit of linear algebra. CAVEAT: If $y_0$ coincides with the $y$-coordinate of one of the vertices, then you need to exercise some care. Basically you need to be careful not to overcount. $\endgroup$ – Jyrki Lahtonen Mar 13 '16 at 11:37
0
$\begingroup$

If there are self-intersections, the algorithm doesn't collapse; it simply gives figures like below (that may remind of Matisse...): the blue colored regions represent the set of points that are considered as "inside" the polygonal shape (of course, one shouldn't any more distinguish an "inside" and an "outside".

The fact that a region is filled is linked to the parity of the winding number. Let me explain it plainly.

Let us take, in the plane assimilated to the complex plane, a reference point $z_0$. Let us consider the function $w(z)=arg(z-z_0)/(2 \pi)$. When $z$ follows the (closed) contour, the difference of values of $w$ between the beginning and the end of the contour is the (signed) number of times the contour has "turned around" point $z_0$. Colored regions are those with an odd winding number.

For a rigorous mathematical definition see https://en.wikipedia.org/wiki/Winding_number.

enter image description here)

| cite | improve this answer | |
$\endgroup$

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.