Point in a predefined polygon

[John Graham]

I have a text file containing polygon data for an entire area, ie each polygon represents a zip or postal code area. I have another file which contains a load of co-ordiantes, I need to write a VB app to work out which polygon each set of co-ordinates falls within. ie I need to calculate whether a point lies inside or outside of a polygon

any help much appreciated

thanks

john

[kedaman]

Are the polygons convex?

[kedaman]

Choose a point outside the polygon, easiest would be say leftmost vertex -1 or if you are sure for instance that the polygon won't be located in origo, put it there for ease of calculations. A straight line (vertical or horizontal) would probably be even better (since this algoritm requires you calculate line intersections)

for a polygon convex polygon, there will be 1 intersection if the point is inside, 0 or 2 if not. You do this by testing each line in the polygon if it intersects with the line, this would probably be fastest if the line is vertical or horizontal

for a concave polygon there will be odd amount of intersection if the point is inside, odd if not.

[Kaverin]

If you weren't really concerned about speed (since it seems like you're determining this for something that's just for information and not speed purposes), you could take your points and create a region from them using CreatePolygonRgn(), and then test a given point by using PtInRgn() and giving it the handle to the region you just created. If your points are just x,y values this would be pretty easy to do. If the regions are complex though, what Kedaman mentioned would be better since it needs only the points of the polygon. I remembered seeing that before, so I went looking and I found it. The article id is Q121960 in MSDN, and titled "Alternative to PtInRegion() for Hit-Testing."

[kedaman]

PtinRegion will just eat up resources for you The regions might either get inprecise or huge bastards if you don't keep them in reasonable scale

[THEROB]

Here is a C function to determine if a point lies within a polygon:

c=0;
                for (i = 0, j = nbpol-1; i < nbpol; j = i++) {
                        if ((((tY[i]<=Y) && (Y<tY[j])) || ((tY[j]<=Y) && (Y<tY[i]))) &&
                        (X < (tX[j] - tX[i]) * (Y - tY[i]) / (tY[j] - tY[i]) + tX[i]))
                         c = !c;
                }

where tX and tY contain the points of the polygon, nbpol is the number of points, X and Y are the point.

if c is true the point is within.

Rob

[John Graham]

Thanks guys for all your replies, much appreciated, I'll start playing and see how I get on

cheers


john