Method and maths (maps, geometry, etc.)

[Zacariaz]

Hello all you happy people!

Once again I come here to have you solve all my problems, but hey, at least I'm keeping you all in shape

The problem at hand is this:

I have a flat map, that is , no weird math involving degrees longitude latitude and stuff like that, which is way beyond my abilities. Instead a point is determined by regular linear x/y coordinates, which should make things a bit easier.

I have defined an area on the map, using a simple closed poly line consisting of 3 or more points and now I need to determine if a specific point is placed inside this area. In reality there is talk of thousands of points, which is why this can't be done manually.

I've considered a number of options, none of which are practical and only one of which can work in reality it seems.

The one solution that I've considered and abandoned because it's simply too much work, is to make a sort of a table of ranges, then it should be a simple matter to look up coordinate y and check if coordinate x is within range or not.

As you can imagine, this is not very practical, but more importantly, it will be hard, though not impossible, to get working in reality as some areas has very complex shapes.

I'm thinking that it must be possible to use another approach. In the end, it's all just simple trigonometry, however, while it may be easy for a human being to do this, I'm at a loss as to how I'm going to get a machine to do it.

It should be noted that these areas are not overly complex, and that the number of points defining them may be, at worst, 20 point or similar. Also, I'm using the gmap v3 engine, in case any of you should know of some fancy feature which I've overlooked.


I do hope that one of you have an idea how to approach this problem (and maybe an idea for a better title? ) but knowing that the average IQ on this forum far surpasses my own, and I'm not as stupid as I seem, I'm not too worried.

Sample data (of the top of my head)

area: (1,1), (1,5), (3,3), (5,5), (6,0), (5,1), (5,2)
points: (5,3), (2,1), etc.

Unless you actually draw this, you'll notice that it's not too easy to visualise


Anyway, thanks in advance, I'll be seeing you all soon.


Best regards.

[bluemoon]

As a first step, I would not directly deal with a polygon with 20 points (or we call it vertex), but simplify the hit-test function to work with only triangles. Those complex 20 vertex polygon can break down into triangles if needed - it may not be very well optimized, but it should be accurate.

so the problem narrow down into 2 parts:
1) triangle hit-test, you can get thousand of example with google
2) the algorithm to break down complex polygon into triangles, I think this consist of a sort of vertex and a loop

Another method is use hardware to perform the test,
for example, render the polygon with openGL into a texture and check the point - but as always, hardware resource is limited and should not be abused.

Edit: Yet another method is to sort the vertex, construct a set of triangles with every two adjacent vertex and the point to-be tested,
calculate the sum of each interior angles, if that add up to 360 degree it is inside the polygon.

Hope this give you some direction.

[NickJohnson]

This seems like it would be a simple modification of the convex polygon collision detection algorithm. I would really go looking on game development forums if you want good information on this sort of stuff.

Edit: Here's an outline of the algorithm:

1. Break the polygon into convex pieces (there's some fancy algorithm for this)
2. For each side of the polygon, check whether the point is on the "inside" of the line extending from that side.
3. If the previous is true for all sides, the point is inside the polygon, otherwise it is not.

[MasterLee]

Wikipedia is your friend
http://en.wikipedia.org/wiki/Point_in_polygon

[Zacariaz]

Thanks ya all. I'll return shortly.

[Zacariaz]

It would seem that the wiki link was all I needed and yes, wikipedia is your friend, but it's sometimes hard when you don't know what to search for

anyway, thanks a bunch.

[davidv1992]

One word of advise, if you go and implement the ray intersection algorithm, be aware of special cases concerning corners, especially if you do this with floating point math. It is very easy to make mistakes on these cases.