Identify to witch polygon belongs a list of point with coordinates

[aleventura]

Hello, this is my first post to this forum. I hope to start participating actively.


This is the problem I am trying to solve. I got a table with several records (aprox 200.000), each with its own coordinates. And I need to identify the "Polygon" witch each point belongs (I got another table with the vertex for earch polygon) . I am working with Excel and Access at this point. Thanks for the help!


I know there is an algorithm that checks if the number of times a line cross another line from the desired point to another point is even, the point is inside polygon, if the number is odd, the point is outside the polygon. But I don’t know how to implement this. Here are some reference links with the algorithm:


http://alienryderflex.com/polygon/


http://www.codeproject.com/Tips/8422...side-a-Polygon


Here is a sample:


I got a table similar to this:


- Point_ID / Coordinates
- 1 / -70.559349,-33.411913
- 2 / -70.579004,-33.407542
- etc. (aprox. 200.000 points)






And I got the following table defining the boundaries of each polygon:


- Polygon_ID / Polygon_Sequence / Coordinates
- 1 / 1 / -70.567331,-33.408803
- 1 / 2 / -70.584755,-33.414249
- 1 / 3 / -70.586987,-33.409692
- 1 / 4 / -70.585527,-33.404175
- 1 / 5 / -70.571537,-33.398084
- 1 / 6 / -70.567331,-33.408803
- 2 / 1 / -70.567245,-33.409047
- 2 / 2 / -70.564756,-33.416570
- 2 / 3 / -70.552998,-33.418576
- 2 / 4 / -70.551796,-33.408474
- 2 / 5 / -70.560122,-33.407542
- 2 / 6 / -70.562525,-33.407327
- 2 / 7 / -70.567245,-33.409047
- etc...


So, this is the output I need (in **bold**):


- Point_ID / Coordinates / **Polygon_ID**
- 1 / -70.559349,-33.411913 / **2**
- 2 / -70.579004,-33.407542 / **1**
- etc...


Thanks a lot!
Alejandro

[June7]

How complex are these polygons? Do any fold back on themselves, any donut holes? Regardless of solution, need to parse coordinates into separate number values. This works with the sample data.

PointsXY
SELECT Points.Point_ID, CDbl(Left([Coordinates],InStr([Coordinates],",")-1)) AS X, CDbl(Mid([Coordinates],InStr([Coordinates],",")+1)) AS Y
FROM Points;

PolygonsXY
SELECT Polygons.Polygon_ID, Polygons.Polygon_Sequence, CDbl(Left([Coordinates],InStr([Coordinates],",")-1)) AS X, CDbl(Mid([Coordinates],InStr([Coordinates],",")+1)) AS Y
FROM Polygons;

MinMax
SELECT PolygonsXY.Polygon_ID, Max(PolygonsXY.X) AS MinX, Min(PolygonsXY.X) AS MaxX, Max(PolygonsXY.Y) AS MinY, Min(PolygonsXY.Y) AS MaxY
FROM PolygonsXY
GROUP BY PolygonsXY.Polygon_ID;

PointPolygon
SELECT PointsXY.Point_ID, PointsXY.X, PointsXY.Y, MinMax.Polygon_ID
FROM MinMax, PointsXY
WHERE (((PointsXY.X) Between [MinX] And [MaxX]) AND ((PointsXY.Y) Between [MinY] And [MaxY]));

I goggled: VB point within polygon
http://www.vb-helper.com/howto_point_in_polygon.html

Most of what I found deals with gaming and mouse click position.