1

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's 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 solve this issue quickly?

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>

1 Answer 1

1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.