Tricky geometry problem

[Turin]

I've got a sticky geometry problem here that I'm sure the folks on this board can help out with. I'm a little embarrassed that I can't figure this out on my own, because I used to tutor math (calculus) years ago, but apparently I've gotten a bit rusty with proofs. I think I've developed a solution, but I can't seem to prove that it works for all cases.

Quick but totally irrelevant background: over the past couple years, I've been helping my firm's in-house programmer to develop some custom software to interface with our CAD software. But she brought me this problem a while back and we've both been stumped for a while. The CAD software itself doesn't have any exposed functions we can access to get this information. While solving this problem will be good for my firm, it will also (more importantly) make me look good with the cute programmer.

Essentially the problem is this:
Given a polygon, can an algorithm be created to test whether a given point (x,y) falls within the boundaries of the polygon?

My solution so far is to take a ray extended from point (x,y) to any point (x1,y1) on an edge of the polygon. If the ray intersects the edges of the polygon an odd number of times, the point is inside the polygon. If it intersects the edges of the polygon an even number of times, the point is outside the polygon. The exception to this is when (x1,y1) is the vertex of the polygon. From a programming standpoint, I can always just exclude the vertices of the polygon from being the test points, so I'm not too worried about that.

The other problem comes in when the boundary of the polygon isn't in fact polygonal but has curved edges. In this case, it's possible that the point (x1,y1) falls on a point tangent to the ray. So there's another exception.

Ignoring the curved edges problem for the moment, can it be proved that this will this work? If not, can anyone point me in the right direction here?

[Surlethe]

You could also run into a problem if the point is on the boundary of the polygon: the line containing (x,y) and (x1,y1) could intersect the boundary at an infinite number of points or twice. Other than that, you might want to use a line segment instead of a ray, since a ray will give you the same number of intersection for two collinear points which are not both in the interior.

[Turin]

Okay, this I get:

You could also run into a problem if the point is on the boundary of the polygon: the line containing (x,y) and (x1,y1) could intersect the boundary at an infinite number of points or twice.

and thanks. But...

Other than that, you might want to use a line segment instead of a ray, since a ray will give you the same number of intersection for two collinear points which are not both in the interior.

This seems like it just adds another exception to program around, unless the length of the line segment is long enough to always cause one of the two points to fall outside the polygon. I'd have to come up with a whole seperate way of determining the suitable length, or come up with some arbitrarily long length (in which case I might as well just use a ray). What would be the advantage of using a line segment as opposed to a ray?

[Kuroneko]

For the simple region case, your method is guaranteed by the Jordan curve theorem. For the complex region case, the exception you name is not good enough. The problem, in general, is whether the ray intersects an a point that is the intersection of edges, especially if some of those edges also happen to be collinear (in general, one can't say whether or not such a point is a vertex, as it may not be or perhaps be a repeated vertex, etc.). From a coding perspective, one can either (1) shrug and say that the exceptions occur on a set of measure zero and are thus irrelevant unless the application is truly critical, or (2) invest clock cycles into triangulating the region first, or otherwise partitioning it into a collection of simple polygons.

[Surlethe]

This seems like it just adds another exception to program around, unless the length of the line segment is long enough to always cause one of the two points to fall outside the polygon. I'd have to come up with a whole seperate way of determining the suitable length, or come up with some arbitrarily long length (in which case I might as well just use a ray). What would be the advantage of using a line segment as opposed to a ray?

Think of it this way: fix a point on the boundary of your polygon, and point a ray out toward the horizon. It will cross the boundary of the polygon n times. There will be some points on the ray which are in the interior of the polygon and some points in the exterior; but the ray crosses n times regardless of whether those points are in the interior or exterior.

For the simple region case, your method is guaranteed by the Jordan curve theorem.

How does the Jordan curve theorem guarantee his method? I thought it only guaranteed that there exist an interior and exterior to a given Jordan curve, not that there is a method to find them.

[Kuroneko]

How does the Jordan curve theorem guarantee his method? I thought it only guaranteed that there exist an interior and exterior to a given Jordan curve, not that there is a method to find them.

For a simple region, the connectedness of the components guarantees that every time one crosses an edge (the boundary), one goes from outside to inside or vice versa, so that then one can simply count the parity of the number of crossings. This is not a completely trivial statement--even in the standard plane, it's not always true for complex polygons. In particular, one have complex polygons for which crossing a single edge does not reverse this outside/inside parity.

[Turin]

The problem, in general, is whether the ray intersects an a point that is the intersection of edges, especially if some of those edges also happen to be collinear (in general, one can't say whether or not such a point is a vertex, as it may not be or perhaps be a repeated vertex, etc.). From a coding perspective, one can either (1) shrug and say that the exceptions occur on a set of measure zero and are thus irrelevant unless the application is truly critical, or (2) invest clock cycles into triangulating the region first, or otherwise partitioning it into a collection of simple polygons.

All this portion of the application is intended to do is to check "insertion points" of real-world objects against the boundaries of the rooms they are supposed to be in, and then fill in a database entry for the object with an identifying number for the room. It's the sort of thing that's easy to do by hand but requires a lot of data-entry labor, so if the application has to catch errors and ask for user input for a handful of the objects, it won't be a big deal.

Think of it this way: fix a point on the boundary of your polygon, and point a ray out toward the horizon. It will cross the boundary of the polygon n times. There will be some points on the ray which are in the interior of the polygon and some points in the exterior; but the ray crosses n times regardless of whether those points are in the interior or exterior.

Sure, but I think I can save clock cycles here. First test point (x,y) to see if it falls on the boundary, which is easy to do with the functions already provided by the software. Then I can reject point (x,y) to the error handling function outright, without having to test it with either a ray or line segment. For purposes of this application, I can arbitrarily say all points (x,y) that fall on the boundary can be considered "in." In this case, if I use a ray I don't have to worry about the line segment not having enough length between (x,y) and any potential points of intersection, giving me a result of N=0 even though I would get N=1 with a ray in that same case.

[Jaepheth]

To check if point B is in a polygon:

Take a point known to be inside the polygon (A), then take the line equation concurrent with each side of the polygon and check to see if segment AB intersects the line. Count the number of intersections (the number of sides between the two points) If it's an even number (0,2,4,6,8,...) then B is inside, otherwise it's outside.

I'm fairly certain this'll work, but I haven't a proof

[Turin]

Just talked with the programmer and it looks like we can make this work as S&K have described above.

For anyone interested, basically the logic of this portion of the program would run as described below. This is in my own symbolic shorthand to the programmer (she's using VBA, which I don't know), rather than any particular programming language, so if it doesn't make sense, just ignore this post. *** denotes comments.

Code: Select all

function FindLocation(L):
For each object Q with insertion point (x,y)
    Goto Test

function Test(P):
For each polygon P
    (If (x,y) is on boundary of polygon P, let L=P; End Test
        (Else   ***If not on boundary
        Draw ray from (x,y) to (0,0)
            (If # intersections N = Even
            Let L=P; End Test
                (Else   ***If Odd
                Draw ray from (x,y) to (0,10)
                    (If # intersections N = Even
                    Let L=P; End Test
                    End If)
            End If)
    End If)
Next P
Let L=null   ***If no Test on P returns L=P
End Test

This lets me safely ignore & assign any case in which (x,y) resides on the boundary, and checks each point to the lower limit corner, then checks at a slight angle to the lower limit corner if that first check returns Not Even. This should clear up the overwhelming majority of the cases where the ray hits a curved "edge" at the tangent. I can handle that level of errors for this application, particularly because the default result shows the L as null and that will pop out quickly in the QA/QC check.

Thanks for your help, guys.

[Beowulf]

Still doesn't work. Suppose it's inside, goes out the polygon, hits a corner, and continues on. You'll end up with an even count, even though it's not outside. What you need to do is subdivide the polygon into a set of polygons, each of which is convex. Ray cast once for each polygon, to a point known to be outside the boundaries of the polygon group. If any of them return that you are inside the polygon group, then you're inside the original polygon.

[Turin]

Still doesn't work. Suppose it's inside, goes out the polygon, hits a corner, and continues on. You'll end up with an even count, even though it's not outside.

Sure, but that's why I'm testing each polygon twice. See below...

What you need to do is subdivide the polygon into a set of polygons, each of which is convex. Ray cast once for each polygon, to a point known to be outside the boundaries of the polygon group. If any of them return that you are inside the polygon group, then you're inside the original polygon.

This is a correct solution, but it's also significantly more complex from a processing standpoint, because I have to subdivide polygons with arbitrary numbers of sides and verify that all the sub-polygons thus created are convex.

By testing each polygon twice with a narrow angle between the rays, there is a very low likelihood that I'll run into a situation where I would exactly hit a vertex in both tests. While it's not an 100% reliable solution, it'll be "good enough" for this purpose. If I'm finding I'm getting unexpected null values, I can always add a third test ray to reduce that likelihood further. But I appreciate your attention to detail!

[Turin]

Ghetto edit / addition:

Keep in mind that the polygons I'm dealing with are derived from the boundaries of real-world spaces displayed as 2D plans, so there's a limit to the level of complexity I expect to find in the polygons. This is why the "good enough" solution is workable for this application.

[Kuroneko]

Convexity is irrelevant, as in terms of intersection count, any situation with concave polygons is realizable with convex ones--in both cases, hitting a corner and continuing onwards does not change parity, being an intersection of two edges (for simple polygons), and yet may involve switching the context from outside to inside or vice versa. Even for a triangle, having a ray from outside intersect with a corner and remain outside gives even parity (outside, correct), but having it go inside through a corner and subsequently leave through a single edge gives odd parity (inside, not correct). The moral is simply that there's nothing particular special about convex polygons--the fun starts when the polygons are complex rather than simple.