Working with polygon regions [Resolved]

Hi,

I've created a program that displays DXF maps and allows the user to zoom, add markup etc.

In the near future I am going to have to implement a feature that allows the user to draw one or more POLYGON shaped region (meaning it could be triangle, square, or any other weird shape you can imagine!). These regions would be stored in a database or text file (which isn't necessariliy important right now) and from time to time I would need to determine what regions a specific X and Y coordinate on this map belong to.

What I'm looking for, is some ideas about how I would accomplish this. It would be easy as pie to figure this out if the regions were all square, but this isn't the case.

In case you are confused as to what I need to do, I am including here an example of what I'm talking about.

http://www.competers.com/mapsample.gif

As you can see from this example, Point A would belong to region 1 only, point B would belong to Regions 2, 3, and 4, Point C would belong to regions 1 and 4, and finally Point D belongs to no regions.

It's easy to visualize this, but how the heck do you program it?

I appreciate any ideas or suggestions you may have!

for each polygon:

from the point in question, move in a straight line in any direction until you reach the edge of the screen. count the number of times that you cross any of the lines of the polygon. if it's a mulitple of 2 then you are outside it.

eg:
from point B, move directly upwards. the counts are:

Region 1: 2 -> outside
Region 2: 1 -> inside
Region 3: 1 -> inside
Region 4: 1, or 3 depending on the accuracy of your drawing - either way - inside

;)


the quickest way for working out which lines are crossed would be to check each line - if the Y value is above the point, one X value is to the left of the point, and the other X value is to the right of it, then you must cross it!

Unfortunately, I can't find my calculus book.

You could try coloring the region within each closed polygon when your checking against that polygon. That way you can check the color at the point using the point method of the form or picturebox to see if its inside or not. After checking the polygon, revert the color inside the region to the original.

I don't think you can do this with irregular polygons. However, you can draw any irregular polygon as an array of triangles. I think you need to be able to handle your polygons in that fashion if you want to be able to solve this.

The second step would be a routine that determines whether the point is in any of the triangles. I can think of a way to get close, which involves a class that has an array of triangles (or vertices), and contains some information about the bounding rectangle (such that any point outside the rectangle is definitely outside any of the triangles that make up the whole polygon). You can disqualify most points by comparing them against the bounding rectangle:

Is the x larger than the largest x in the polygon, or smaller than the smallest x, etc.

If the point passes that test, you get into the more difficult issue of determining whether it is within the bounding rect, but outside all the constituent triangles. That would take more thought.

Since each triangle has it's own bounding rectangle, you can determine which triangles you need to work with in the same manner that you checked the bounding rect of the overall polygon.

To determine whether the point is within any one triangle...well, I don't have a solid answer. I did something like this, but the edges of the triangle were always one of four lines, which you can't do.

There must be someone who can answer this better, but if you can figure the left edge, right edge, etc, you can walk along each edge of the triangle and determine if it is inside or outside of each edge. The point must be inside of each of the three edges for it to be within the triangle.

Quote:

---

Originally posted by si_the_geek
for each polygon:

from the point in question, move in a straight line in any direction until you reach the edge of the screen. count the number of times that you cross any of the lines of the polygon. if it's a mulitple of 2 then you are outside it.

eg:
from point B, move directly upwards. the counts are:

Region 1: 2 -> outside
Region 2: 1 -> inside
Region 3: 1 -> inside
Region 4: 1, or 3 depending on the accuracy of your drawing - either way - inside

;)


the quickest way for working out which lines are crossed would be to check each line - if the Y value is above the point, one X value is to the left of the point, and the other X value is to the right of it, then you must cross it!

---

Wow! Never thought of it that way. :)

ae_jester: You can check how many times you crossed a line by comparing the colors. Count how many times it changes from non-black to black. If it's in multiples of two or zero then your outside the polygon. That should work even with circles, arc edges. Just make sure you close the regions properly.

There's also the problem that you'll pass through one or more lines tangentially. Maybe you can check in all four directions and do a poll. Three of the counts should match as even-count or odd-count. If you pass edges tangentially in all four directions is the worst case but the possibility should be remote.

You can't use the edge of the screen as the boundary, since he is talking about zooming. Some of the polygons will fall across the screen boundary. However, if you change that to "world space" it will work. You can define the world space as (x1,y1)-(x2,y2) where x1 is slightly smaller than the smallest vertex in the polygon list, while x2 is slightly larger than the largest vertex. Y1 and Y2 are defined the same way.

Quote:

---

Originally posted by Shaggy Hiker
You can't use the edge of the screen as the boundary, since he is talking about zooming. Some of the polygons will fall across the screen boundary. However, if you change that to "world space" it will work. You can define the world space as (x1,y1)-(x2,y2) where x1 is slightly smaller than the smallest vertex in the polygon list, while x2 is slightly larger than the largest vertex. Y1 and Y2 are defined the same way.

---

true, but a slight expansion of my final sentence would easily cover it (it's been a while since I did this sort of thing!):

for each line of the polygon: check both Y co-ordinates, if either is less than the Y of the point then check the X; if one X value is to the left of the point, and the other X value is to the right of it, then you must cross it

(if you want to include the boundaries of the polygon you should also check being equal X and Y positions)

Thanks for all the responses.

Unfortunately, any solution that involves checking colour, will not work. This is because these regions don't actually show up on the map screen during normal operation.

Also, with regards to si_the_geek's fine solution, I don't think it will work in this case. This is because in some cases if you move up or down from any given point on the map, you might cross a region boundary 3 times! What can you conclude from this? Nothing!!! You can't tell if you are inside or outside of the region.

Shaggy's idea about dividing each polygon into triangles seems to be the most logical solution. However, this produces another problem. How would you go about dividing a polygon into triangles?

I'll try and think about this for a while and see if I can come up with any ideas, but if anyone here has done something like this, or has some ideas, im all ears!

Sorry, I didnt think about this correctly. Si's solution WOULD work, but would it be the best and fastest way to do this? Is the triangle solution more efficient?

Right, the technique is pretty cool. If you work in a bounding area rather than screen area, your technique works just as well, but isn't limitted by resolution.

I wonder what the speed differences are. A polygon can consist of n vertices where n>2. Therefore, the number of edges is n, and the number of potential tests for crossing is the same. There has to be a technique to rule out the bulk of the lines for any particular test. By looking at triangles, you can rule out all but a handful pretty quickly by looking at bounding rectangles. Of course, once you decide which of the triangles the point could be in, you can test each of them as if they were polygons in a space, just as si_ has stated.

What is the quickest route? Do you leave the polygons as a series of line segments to be tested, or pre-calculate the triangles that form the polygons, and the bounding regions. I have the feeling that the latter moves most of its calculating into initialization, but I'm not sure.

Dividing a polygon into triangles is easy if the polygon is convex. Doing the same for a concave polygon is also simple, but only if certain critical points can be identified. In the end, I think the bounding regions and triangles will be faster, but only if you can pre-create the triangles, and I can't think of an easy general case way to do this.

However, both techniques can be melded. If you determine bounding regions for the polygons, you will be able to quickly determine which polygons (and hence, which set of line segments) need to be checked using si-'s method.

my way will mean about 10-20 lines of code, with minimal repetition of lines (you need to loop for each line of each polygon, but that's it).

I'm pretty sure Shaggy Hiker's way will mean more code, probably with many more repeats.

my version will mean up to 4 checks per line for bounding + a single check if the line intersects with the line from the point.

depending on the simplicity of the code for checking intersection, you just use a modified version of that instead of doing any boundary work, making it even simpler ;)

Si's way is easier since you evaluate with the given data (endpoints) rather than creating new data to do the comparison with.

I'm coming around to that view as well.

I wrote something similar, but every point had to be in a region, every region was convex, and the question was "which region am I in". All the work was done during the program loading, which left very little to do in the function. The points kept the region that they were last in, and passed that to a function that checked which region they were currently in. This question is sufficiently different that the technique doesn't appear to scale well.

As for creating new data, in some programs that's a really good idea. In a game, where speed is essential, anything you can pre-calculate (such as polygons, random numbers, etc.) during loading, that will save time during game time, will pay off. The total calculations and time taken can be more, if it means that the time taken during critical intervals will be reduced.

Right, if the regions were already divided into triangles to begin with then its only prudent to make use of that info. With games, the polygons are crucial for rendering, movement calculation, etc so its premade at the earliest possible time and used thereafter.

Since ae_jester's program wasn't designed with the triangles being determined upon creation of the region, then might as well use Si's method. :)

Hi Guys,

I made a quick and dirty implementation of Si's solution. It works great! Thanks for all the help!

I attached it, so you can check it out.

Instructions on how to use it:
For each region you want to add click the add new region button, then using your left mouse button click anywhere on the map area to add vertexes. To finish off the polygon, click the right mouse button.

WHen you want to test it, click the "Check Point" button, and as you move your mouse around the map area, it shows you in the list box which regions you are currently inside.

That's good stuff (except autoredraw turned off on the picturebox ;) )


If speed was an issue you could store the slope of each line, but it doesn't seem to be a problem in this case (unless you have lots of shapes & have it running constantly).

I wouldn't fill the list in the same way that you do (it flashes too much) - I would rather not clear it, but add/remove each polygon if apt. (although this is a bit slower!), or fill an array/collection with the names and clear+fill it all in one go.

Yeah, I've improved it here a lot since I posted that, but keep in mind this is just a 'demo'. I would have no need to display which regions the mouse is over in the real application (it would just need to keep track in memory).

Quote:

---

Originally posted by ae_jester
I would have no need to display which regions the mouse is over in the real application (it would just need to keep track in memory).

---

ah, that would be much better - you could add an extra propery (boolean) to the region type, and set it at the end of the region loop, eg:

VB Code:

'If lineCount Mod 2 = 1 Then
        '    List1.AddItem regions(i).regionName
        'End If
         regions(i).mouse_in_region = (lineCount Mod 2 = 1)
    Next i
End Sub

Actually, the real version of this would have nothing to do with the mouse. I would just need to call this 'function' and pass it an x and y coordinates for a 'house' on the map (my version didn't have a map, but my real app does). Based on which regions this coordinate belongs to, I would then have to send some information to each of the 'companies' that represent each region.