Where is the interior of the polygon?

Question

There is an axis-parallel (orthogonal) simply-connected polygon given as a list of corners. How can I know whether a certain vertical segment has the interior of the polygon on its east or on its west?

For example, in the following polygon:

 (0,0) (0,1) (1,1) (1,0) (0,0)

The first segment, $(0,0)-(0,1)$, has the interior on its east, and the third segment, $(1,1)-(1,0)$, has the interior on its west. But in the following polygon:

 (0,0) (0,1) (1,1) (1,0) (2,0) (2,2) (-1,2) (-1,0) (0,0)

The first three corners are just like the first polygon, but here the first segment, $(0,0)-(0,1)$, has the interior on its west.

The order of the input can be reversed:

 (0,0) (1,0) (1,1) (0,1) (0,0)

In this case, the second segment has the interior on its west and the fourth has the interior on its east.

How can I know which case I am at?

Answer 1

This is an instance of what is generally known as the Point in Polygon problem. Assuming all your vertex coordinates are integral, you essentially want to find out if (-0.5, 0.5) or (0.5,0.5) are on the interior of the polygon.

One thing you need to do is decide on how you will deal with complicated cases like loops in the polygon edge. The usual course is to decide on the even-odd rule or the nonzero winding number rule. Or you could assume that the polygon has a noncrossing boundary.

Once you have all this decided, you cast a ray out from your test point and apply the counting rule you have chosen.

Answer 2

In addition to the Point in Polygon solution suggested by NovaDenizen, I thought of another possible solution:

Loop over the corners of the polygon, count the number of right-turns and compare to the number of left-turns. If the number of right-turns is larger (as in the first example), then the direction is clockwise and the interior is at our right hand; this means that, for example, if a segment points north then the interior is to its east. If the number of left-turns is larger (as in the second and third examples) then the opposite is true.

Answer 3

If the polygon is "triangulizable"

No need to compute the triangulization! Suppose that the polygon has N vertices.

Compute the sum of the $N$ angles all oriented the same way, that is, following a direction along the polygon line. If they sum up to $180(N-2)$, then the way you computed the angles defines the inside. If they sum up to $180(N+2)$, then it was the outside. This comes from the trivial fact that around each point, there is a full 360° angle, so:

$$Inside + Outside = 360N$$

If the polygon is triangulizable, then by removing one of the triangles, you remove 180°. You can have at most N-2 triangles.

If the polygon is not "triangulizable"

Adding one cross on the polygon makes this impossible with this method to determine which side is the inside and which is the outside. The reason is simple: because we could scale either side without changing the angles.

In the following case, the sum of angles for both sides is the same.