Android Code Snippet Geo-Zone Determination (Point in Polygon)

I use this in my app to determine if a vehicle is within a defined zone made of 5 or more lat/lon coordinates. Point 1 is also Point 5 (first point and last point are same value).
A simple box shows how to create this:

1----------2
| ........... |
| ........... | clockwise (or counter clockwise)
| ........... |
4----------3

In my case, I determine either a) the speed of the vehicle or b) how long stopped in zone.

Note: Larger zones work best due to the inaccuracy of GPS. My accuracy reading jumps
from 6 meters to 24 or more meters...

Source: Klaus from post #6 below
This function is tested and works fine.

Sub FindInZone( polx As List, poly As List, x As Double, y As Double) As Boolean
' polx = list of lats for polygon
' poly = list of lons for polygon
' y = lon to test
' x = lat to test

    Dim x1, y1, x2, y2, D As Double
    Dim i, ni As Int
 
    ni = 0
    x1 = polx.Get(0)
    y1 = poly.Get(0)
    For i = 0 To polx.Size -1
        If i < polx.Size Then
            x2 = polx.Get(i)
            y2 = poly.Get(i)
        Else
            x2 = polx.Get(0)     ' checks the last line
            y2 = poly.Get(0)
        End If
   
   
        If y >= Min(y1, y2) Then
            If y <= Max(y1, y2) Then
                If x <= Max(x1, x2) Then
                    If (x = x1 AND y = y1) OR (x = x1 AND x = x2) Then ' checks vertices and vertical lines
                        Return True
                    End If
                    If y1 <> y2 Then
                        D = (y - y1) * (x2 - x1) / (y2 - y1) + x1
                        If x1 = x2 OR x <= D Then
                            ni = ni + 1
                        End If
                    End If
                End If
            End If
        End If
        x1 = x2
        y1 = y2
    Next

    If ni Mod 2 = 0 Then
        Return False
    Else
        Return True
    End If
End Sub

 

[ilan]

Look at lgMathPolygon.contains or the various functions of lgMathIntersector.

the libgdx math functions are really good. i managed to create the polygons and also check if they are overlapping the problem is that
if they are touching each other i get returned as they are overlapping.

so i tried to scale 1 polygon and like this if they are only touching at their frames each other i get false (thats what i want)

the problem is that the scaling of the vertices is relative to the origin of the polygon.

so i have first to set the origin but thats not that simple

i tried to get the lowest x,y and highest x,y and then get the center of the polygon

                Dim centerx, centery As Float
                centerx = lowx + ((highx-lowx)/2)
                centery = lowy + ((highy-lowy)/2)

the problem is that if i have a triangle the center is on the walls of the triangle and then the scaling is not done correct

with a square it is ok

if i would take a more complex polygon i wont get the result i need.

is there any way to check only if polygons are overlapping with a minimum area and not just laying next to each other?

thanks

 

[ilan]

i think i need to calculate the centroid of the polygon

http://stackoverflow.com/questions/2792443/finding-the-centroid-of-a-polygon

https://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon

 

[JordiCP]

Central point for a square works because of its simmetry. Also would work for regular polygons. Not sure if centroid would solve all cases

If you want to make a smaller polygon contained in the "original one", I would follow this algorithm:

• For each pair of vertices (Vi,Vj)
  • calculate the central point of the segment joining them. (Cij) and its slope (m)
  • Then take two perpendicular points to this one, at a small distance to this central point (Cij1,Cij2)
    • One of them will be inside and the other outside the polygon.
    • As you can calculate for each point if it is inside or outside the polygon, keep the one which falls inside and discard the other. Let's call it CijI
  • With this point, get a line with the same angle as the original, and keep it (CijI and m) for later use
• Next
• Once you have done this for all the lines, just calculate their intersecting points and you have the new polygon

If you draw the steps, you will see that it is more or less what you are doing mentally when posting the triangle example

 

[ilan]

Central point for a square works because of its simmetry. Also would work for regular polygons. Not sure if centroid would solve all cases

If you want to make a smaller polygon contained in the "original one", I would follow this algorithm:

• For each pair of vertices (Vi,Vj)
  • calculate the central point of the segment joining them. (Cij) and its slope (m)
  • Then take two perpendicular points to this one, at a small distance to this central point (Cij1,Cij2)
    • One of them will be inside and the other outside the polygon.
    • As you can calculate for each point if it is inside or outside the polygon, keep the one which falls inside and discard the other. Let's call it CijI
  • With this point, get a line with the same angle as the original, and keep it (CijI and m) for later use
• Next
• Once you have done this for all the lines, just calculate their intersecting points and you have the new polygon

If you draw the steps, you will see that it is more or less what you are doing mentally when posting the triangle example

Thank you for your answer but i really dont understand the instruction how to get a copied scaled polygon inside it self.

I have all vectors for the path of the polygon

To make it simple:

Lets take a triangle with 3 vectors (x/y)

V1(100,100)
V2(200,200)
V3(100,200)

What would be the centre of this triangle?

 

[ilan]

ok this code is working for me so far:

Sub compute2DPolygonCentroid(vertices As List) As String
    Dim centroid(2) As Double
    Dim signedArea = 0.0 As Double
    Dim x0 = 0.0 As Double
    Dim y0 = 0.0 As Double
    Dim x1 = 0.0 As Double
    Dim y1 = 0.0 As Double
    Dim a = 0.0 As Double
   
    For i = 0 To vertices.Size - 1
        If i = vertices.Size - 1 Then
            Dim dbl() As Double = vertices.Get(i)
            Dim dbl2() As Double = vertices.Get(0)
            x0 = dbl(0)
            y0 = dbl(1)
            x1 = dbl2(0)
            y1 = dbl2(1)
            a = x0*y1 - x1*y0
            signedArea = signedArea + a
            centroid(0) = centroid(0) + ((x0 + x1)*a)
            centroid(1) = centroid(1) + ((y0 + y1)*a)   

            signedArea = signedArea * 0.5
            centroid(0) = centroid(0) / ((6.0*signedArea))
            centroid(1) = centroid(1) / ((6.0*signedArea))
        Else
            Dim dbl() As Double = vertices.Get(i)
            Dim dbl2() As Double = vertices.Get(i+1)
            x0 = dbl(0)
            y0 = dbl(1)
            x1 = dbl2(0)
            y1 = dbl2(1)
            a = x0*y1 - x1*y0
            signedArea = signedArea + a
            centroid(0) = centroid(0) + ((x0 + x1)*a)
            centroid(1) = centroid(1) + ((y0 + y1)*a)               
        End If
    Next
    Return centroid(0) & ":" & centroid(1)
End Sub

this gives me the center of the polygon and now i can set the origin and scale it correctly

i have not tested it with more complex polygons, will let you know when i get to it

thanx a lot guys

 

[ilan]

dear @Harris, sorry that i turned your thread to this chaos
i hope you forgive me