i have a big number of Polygons extracted from a KML file. The polygons represents "blocks" on the Earth surface.
I can read the coordinates of the polygons and store their values, as well as some other information i have regarding the polygon.
My problem is, i now have a collection of points (with their coordinates, again we're talking about points on the earth surface) and i need to check in which polygon they belong.
I know PiP is not a trivial nor new problem, so i don't want to reinvent the wheel!
Is there any VB.NET library which can help me solve this issue quickly?
Thanks
EDIT
My polygons are in the shape of n-tuples, example with a 5-tuple (some of them have more, all of them have the first and last point equal):
[( -59.00002600000005,-52.00002600000001,0 ),
( -59.00002600000005,-51.50002600000001,0 ),
( -59.50002600000005,-51.50002600000001,0 ),
( -59.50002600000005,-52.00002600000001,0 ),
( -59.00002600000005,-52.00002600000001,0 ) ]
At the moment i'm reading the KML file this way:
'foreach KML Placemark
For Each p As System.XML.Linq.XElement In xdata.Descendants(ns +"Placemark")
ID = p.Element(ns+"name").Value
'coordinates, every substring has triple x,y,z but i only care about x,y
temp = p.Descendants(ns+"coordinates").Value
str = temp.split(" ")
'number of polygon vertexes
lunghezza(ID) = str.length()-1
'polygon vertexes
Dim polygonPoints(str.length()-1) As System.Drawing.PointF
'first substring is empty
for s = 1 to str.length()-1
'i get x,y
x = String2Array(str(s),",",false)(1)
y = String2Array(str(s),",",false)(2)
'cast to double
flt_x = double.Parse(x)
flt_y = double.Parse(y)
'point is made
polygonPoints(s-1) = new System.Drawing.PointF(flt_x, flt_y)
next
'points are associated to the polygon ID
punti(ID) = polygonPoints
Next
At this point i try to see if a point is inside one of these polygons i have stored: to do this i used the algorithm that i found here
dim ok as boolean = false
dim xinters as double
' flt_y and flt_x contain my test latitude and longitude
'foreach polygon stored
for each id in IDS
if not empty(id)
'get number of points defining the polygon
Dim polygonPoints2(lunghezza(id)) As System.Drawing.PointF
'i get the polygon vertexes
polygonPoints2 = punti(id)
dim p1, p2 as System.Drawing.PointF
'first point
p1 = polygonPoints2(0)
'counter
dim c as integer = 0
for i as integer = 1 to lunghezza(id)
p2 = polygonPoints2(i Mod lunghezza(id))
if ( flt_x > Math.min(p1.x, p2.x) and flt_x <= Math.max(p1.x, p2.x) and flt_y <= Math.max(p1.y, p2.y) and p1.x <> p2.x) then
xinters = (flt_x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + p1.y
if (p1.y = p2.y or flt_y <= xinters)
c = c + 1
end if
end if
p1 = p2
next
if (c mod 2) <> 0
'found one!
ok = true
exit for
end if
end if
next
But i never get to find to which polygon my point belongs! What am i doing wrong?
to test i am using coordinates: x: 44,3034627 y: 7,800283
i am sure these fit into this polygon:
<Polygon>
<extrude>0</extrude>
<altitudeMode>clampToGround</altitudeMode>
<outerBoundaryIs>
<LinearRing>
<coordinates>
10.99997399999995,45.999974,0
10.99997399999995,46.499974,0
10.49997399999995,46.499974,0
9.999973999999952,46.499974,0
9.499973999999952,46.499974,0
8.999973999999952,46.499974,0
8.499973999999952,46.499974,0
7.999973999999952,46.499974,0
7.999973999999952,45.999974,0
7.499973999999952,45.999974,0
6.999973999999952,45.999974,0
6.999973999999952,45.499974,0
6.999973999999952,44.999974,0
6.999973999999952,44.499974,0
6.999973999999952,43.999974,0
7.499973999999952,43.999974,0
7.999973999999952,43.999974,0
7.999973999999952,44.499974,0
8.499973999999952,44.499974,0
8.999973999999952,44.499974,0
9.499973999999952,44.499974,0
9.999973999999952,44.499974,0
10.49997399999995,44.499974,0
10.49997399999995,43.999974,0
10.99997399999995,43.999974,0
11.49997399999995,43.999974,0
11.99997399999995,43.999974,0
11.99997399999995,44.499974,0
12.49997399999995,44.499974,0
12.49997399999995,44.999974,0
11.99997399999995,44.999974,0
11.49997399999995,44.999974,0
11.49997399999995,45.499974,0
10.99997399999995,45.499974,0
10.99997399999995,45.999974,0
</coordinates>
</LinearRing>
</outerBoundaryIs>
</Polygon>
I am starting to suspect the issue is in the PiP algorithm, more specifically regarding the <> and = comparisons between Doubles hence the re-tag
In the end, all my work was correct and i was just reading the coordinates in the wrong order and not treating correctly the input strings. Here is the corrected code to read the KML:
'foreach KML Placemark
For Each p As System.XML.Linq.XElement In xdata.Descendants(ns +"Placemark")
ID = p.Element(ns+"name").Value
'coordinates, every substring has triple x,y,z but i only care about x,y
temp = p.Descendants(ns+"coordinates").Value
str = temp.split(" ")
'number of polygon vertexes
lunghezza(ID) = str.length()-1
'polygon vertexes
Dim polygonPoints(str.length()-1) As System.Drawing.PointF
'first substring is empty
for s = 1 to str.length()-1
'i get x,y
y = String2Array(str(s),",",false)(1)
x = String2Array(str(s),",",false)(2)
'cast to double
flt_x = double.Parse(x.replace(".", ","))
flt_y = double.Parse(y.replace(".", ","))
'point is made
polygonPoints(s-1) = new System.Drawing.PointF(flt_x, flt_y)
next
'points are associated to the polygon ID
punti(ID) = polygonPoints
Next