Jordan Curve Theorem

Robert P. Munafo, 2023 Feb 21.

The Jordan curve theorem gives a simple way to determine if a point in certain two-dimensional spaces (including normal cartesian space) is in the interior of a polygon (or more generally, any region defined by a closed curve) in the same two-dimensional space.

It can be used to find the period of a mu-atom given a rectangle that surrounds it; see Jordan curve method.

A complete description is given on Wikipedia: Jordan curve theorem.

Example

Given this quadrilateral with corners at the indicated coordinates, and the marked point with coordinates (6, 7), we want to answer the question: is the point inside or outside the quadrilateral?

. . ' (9,9) . . ' ' . (1,7) ' * . . . . . . . . . . . . . (9,1) . . . ' ' (3,-2) '

To answer this question by the Jordan Curve Theorem, we consider a ray starting at the point in question (extending in whatever direction we choose, say to the right):

. . ' (9,9) . . ' ' . (1,7) ' *-------.--------------> . . . . . . . . . . . . (9,1) . . . ' ' (3,-2) '

We count the number of times that the ray crosses the boundary of the region (i.e. intersects an edge of the quadrilateral). If the answer is even, the point is outside the region; if the answer is odd, the point is inside.

In this example the ray crosses exactly once, so we know that the point is within the quadrilateral.

If a Vertex Shares a Y Coordinate

Suppose the quadrilateral has a vertex whose Y coordinate is the same as the Y coordinate of the point of interest:

. . . * * ' ' ' ' . . . . *-------*--------------> . . . . . . . . . . *

In this situation, two of the line segments intersect the ray, so the count of intersections is even. This means that the point of interest would be considered to be outside the region, instead of inside.

To handle this problem, a slight modification of the line intersection test can be used:

Each line segment is considered to have a "start" and an "end".

When considering the four edges of the quadrilateral, each vertex is the "start" of exactly one line segment.

When determining if a line segment intersects, the start vertex counts but the end vertex does not.

If the Point of Interest Is the Origin

When the point being tested is the origin, the ray/line intersection calculation is a bit simpler. The ray is the positive half of the real axis. See the line intersection article for the formula; after computing the point of intersection i, a boundary crossing occurs if and only if i is positive. Do this for all four edges of the quadrilateral, and count the number of crossings to see if it is odd.

Program

The following program sets up an example and prints the calculations as it goes; you can use the example values to verify that your implementation is working.

(NOTE: The variable names a, b, ..., h are similar to those in the program in the Inverse Interpolation for a Quadrilateral article, but not in the same order; here we have assigned them to the vertices in clockwise order.)

// Use Jordan Curve method to determine if the origin is within // a quadrilateral. The quadrilateral is as in this diagram, "O" // represents the origin. // . .(9,7) // . . ' ' . // (-3,5) ' . // . . // . . // . . // . . // . O . // . . (10,-1) // . . . ' // (-1,-4) ' a = -3 b = 5 c = 9 d = 7 e = 10 f = -1 g = -1 h = -4 // We will count how many edges cross the positive real axis. // Start our counter at 0 crossings = 0 CHECK_EDGE1: // check first edge (a,b)-(c,d) // are both Y coordinates on the same side of the real axis? we can // quickly check for this by multiplying and looking for a positive result if (b*d > 0) then goto CHECK_EDGE2 // if both are zero, we don't have to count this edge if ((b = 0) and (d = 0)) then goto CHECK_EDGE2 // test if first endpoint is right on the positive real axis if (b = 0) and (a < 0) then goto CHECK_EDGE2 // if other endpoint is on real axis, it does not count if (d = 0) then goto CHECK_EDGE2 // now do the interpolation calculation if ((a - b*(c-a)/(d-b)) < 0) then goto CHECK_EDGE2 // if we make it this far, the first edge crosses the real axis crossings = crossings + 1 CHECK_EDGE2: // repeat all of the above for the second edge if (d*f > 0) then goto CHECK_EDGE3 if (f = 0) then goto CHECK_EDGE3 if (d = 0) and (c < 0) then goto CHECK_EDGE3 if ((c - d*(e-c)/(f-d)) < 0) then goto CHECK_EDGE3 crossings = crossings + 1 CHECK_EDGE3: // repeat all of the above for the third edge if (f*h > 0) then goto CHECK_EDGE4 if (h = 0) then goto CHECK_EDGE4 if (f = 0) and (e < 0) then goto CHECK_EDGE4 if ((e - f*(g-e)/(h-f)) < 0) then goto CHECK_EDGE4 crossings = crossings + 1 CHECK_EDGE3: // repeat all of the above for the fourth edge if (h*b > 0) then goto DONE_COUNTING if (b = 0) then goto DONE_COUNTING if (h = 0) and (g < 0) then goto DONE_COUNTING if ((g - h*(a-g)/(b-h)) < 0) then goto DONE_COUNTING crossings = crossings + 1 DONE_COUNTING: if ((crossings = 1) or (crossings = 3)) then print "The origin is INSIDE the quadrilateral." jct_result = true else print "The origin is outside the quadrilateral." jct_result = false end if

revisions: 20080309 oldest on record; 20230218 reference Jordan method article; 20230220 Add illustrasted example; 20230221 Add section about a shared Y coordinate and sample program

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Feb 22.

s.27