[Solved] Detecting if a point is inside a polygon with wrap-around.

[SupSuper]

The X-Com game world consists of a flat map with a series of polygons representing the land masses, like so:


(image from Ufopaedia.org)

One of the things that needs to be checked when the player tries to place a base, is whether the base is on land. This is done by checking if the clicked point is inside a polygon.

While this is very simple, the problem is that a lot of the polygons "wrap-around". That is, since the flat map is rendered as a globe, a lot of the polygons wrap around from one side to the other like this:


In black is how the polygon should work, while in red is how the polygon will be interpreted. Naturally this poses a problem using standard point-in-polygon algorithms.

So... anyone have any ideas how to solve this? Mathematically, programatically, however you can explain it.

[pmprog]

Not had chance to look at the code properly yet, but it looks like you draw the world (Globe.cpp) in polygons after adjusting them on world rotation and zoom, could you not simply perform your mouse check against this polygon set, rather than the initial globe set?

They must be accurate, because you draw them, and you'll know which ones are visible by the backFace variable.

And to save recalculating these, you could create a visibleWorldPolygon list as you're drawing the globe with the real polygon they tie up to, their calculated draw polygon, and any other information

Edit:
I appreciate that's not exactly what you asked for, so here's another solution:
Let's assume you have coordinate (X, Y) to check, as I'm processing each polygon, I would use this to identify if the polygon crossed the "edge"

Code: [Select]

HasLeft5PC = False
HasRight5PC = False
For Each Point in Polygon
  If Point.X < (Map.Width / 20) Then HasLeft5PC = True
  If Point.X > Map.Width - (Map.Width / 20) Then HasRight5PC = True
Next

If so, I would check if X > Map.Width - (Map.Width / 20) and X = X - Map.Width (Making X a negative value on the map)

In my Polygon test, I would then do the same and check if it's in the right 5% of the map, and subtract the map width to make it negative.

This means your polygon will all be based around zero, going negative as well as positive, and you're standard checks would work fine.

If you're using unsigned variables, you could always push it the other way, to add the map width to those points in the left half of the map.

[SupSuper]

Not had chance to look at the code properly yet, but it looks like you draw the world (Globe.cpp) in polygons after adjusting them on world rotation and zoom, could you not simply perform your mouse check against this polygon set, rather than the initial globe set?

They must be accurate, because you draw them, and you'll know which ones are visible by the backFace variable.

And to save recalculating these, you could create a visibleWorldPolygon list as you're drawing the globe with the real polygon they tie up to, their calculated draw polygon, and any other information

Actually that works pretty well, thanks. I'm shocked I didn't think of it.

[pmprog]

Glad to help.

Interestingly enough, I've noticed the other day, that a few places where the hit test written to cout is incorrect. The only one I can remember clearly is West Africa around Nigeria, Niger and Mali.

I think there was one around the Gulf of Mexico, but I can't remember.

Don't know if these will be fixed with your new method, I'll update my copy of the source when I get home and give it a try (if you've checked the changes in)

Edit: The new source fixed that spot in Africa, but I've found another

[SupSuper]

From what I can tell, these "holes" happen in the edges of adjacent polygons, probably because due to rounding errors or approximations or what not the polygons don't actually end up meshing together exactly as they look and you end up with tiny gaps where the test fails.

I wouldn't know where to even begin to fix that though.

[pmprog]

The only way I can think of doing this is in your polygon check, is to multiply all the coordinates by 100 (or even 1000). This should increase the tolerance on these crossover points

[SupSuper]

Another idea might be that the "point-in-polygon" algorithm is ambiguous on polygon edges. Boy the bugs never stop coming. :rolleyes: