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

 

[Harris]

Thanks for the likes guys and gals... I have been testing this and it works surprisingly well with consumer device chip sets.
I shall report any other findings during my test and real world use.

 

[Troberg]

Some suggestions/questions:

* Don't require the last and first coordinate to be the same, instead, add the last, duplicate, as needed in the sub. Less risk for mistakes when calling it that way.
* Why five coordinates minimum? What about a triangle? From the look of it, I can't see any reason a triangle shouldn't work.
* I don't know, but it might be a good idea to check what happens when the ray-cast line passes exactly through one of the vertices. It could be that it's counted twice. or not at all. Probably, it needs to be changed so that, for example, the test for the first end is >= and the other end is <.
* Likewise, check what happens if it passes exactly along a horizontal bounding line.

 

[Harris]

Excellent reply...

I am only working from what I barely understand about this process. From what I read about examples on-line, they said to close to loop (terminate the polygon from where it started).

What I am finding, however, is that my tests are reporting that I am in a polygon, when in fact I am no where near it! This happens for only 3 - 4 seconds but completely distorts my intentions ( can I state you were speeding in this zone when you you were no where near it? ). I have created many zones over a 50 km region and at times, my Point in Polygon tests return I am in a zone where in fact - I am no where near it???

@Troberg - PLEASE correct the code where required. Truly grateful.

My example shows a simple schema... four points in a rectangle (most of which is needed but more complex shapes should also work) where the last point is the first ( 5th point) - to close the polygon... Where is my error?

Many errors occur from my GPS - creating the zone (the four or more points). The GPS from my device (often) returns the wrong Lat/Lon so my polygon is ill-formed.

History - In the past, I used Google Earth to create to create a KML of such polygon shapes. However, this project is so far remote North that Hi-Res Google maps don't exist. This is why I am using a device to map the polygon structure for us...

Thanks Harris

 

[Troberg]

I don't have time to correct the code in the near future. I'll try to explain instead:

From what I read about examples on-line, they said to close to loop (terminate the polygon from where it started).

Not wrong, just neater if the caller didn't have to send the first coordinate twice. It's one of those details you tend to forget when you get back to the code half a year later...

Of course the polygon must be closed, what I meant was that, instead of relying on the caller to do it, it's neater to just have the caller send the coordinates in order, then, in this sub, just add the first coordinate again at the end of the list.

What I am finding, however, is that my tests are reporting that I am in a polygon, when in fact I am no where near it! This happens for only 3 - 4 seconds but completely distorts my intentions ( can I state you were speeding in this zone when you you were no where near it? ). I have created many zones over a 50 km region and at times, my Point in Polygon tests return I am in a zone where in fact - I am no where near it???

Well, the algorithm as such is sound. There might be some small bug in the implementation, or you may get bad positions from the GPS. Have you checked what data you actually get?

Many errors occur from my GPS - creating the zone (the four or more points). The GPS from my device (often) returns the wrong Lat/Lon so my polygon is ill-formed.

History - In the past, I used Google Earth to create to create a KML of such polygon shapes. However, this project is so far remote North that Hi-Res Google maps don't exist. This is why I am using a device to map the polygon structure for us...

I think we may have the answer there. GPS is much more unreliable far north and far south, as the satellites are not on perfect 90 degrees orbits. The orbits are tilted quite a lot, to get better coverage away from the poles, as the poles are fairly uninteresting for most people. Also, if driving, you might need an external antenna, or at least Think about how you position the GPS in the car. If you are far north, you want to get as good view as you can on the southern sky, that's where you'll find the most satellites.

 

[klaus]

I have used this routine for general geometry not lat / lon.

Sub CheckPointInPolygone(polx() As Double, poly() As Double, x As Double, y As Double) As Boolean
    Dim x1, y1, x2, y2, D As Double
    Dim i, ni As Int
  
    ni = 0
    x1 = polx(0)
    y1 = poly(0)
    For i = 1 To polx.Length
        If i < polx.Length Then
            x2 = polx(i)
            y2 = poly(i)
        Else
            x2 = polx(0)     ' checks the last line
            y2 = poly(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

You can replace x by lat and y by lon.
You can replace polx by a List and poly by another List and x1 = polx(i) by x1 = ListX.Get(i) etc.

Attached a small test program.

 

[Harris]

Thanks Klaus... I shall try it out and see how it behaves.

 

[Harris]

Tested your sub after modifying it.
WORKS GREAT!!!!
No false positives at any time and showed I was in each zone on my 50 km drive.
My one second timer which tests FindInZone for each new lat/lon (from fused location provider) returned true the instant I crossed the border.

Can't say I understand the math but it works for me! Now I can put this one to bed.

Thanks so much Klaus, and Troberg for your suggestions.


Original First Post updated to new FindInZone

 

[Troberg]

If I might enquire, as road databases, traffic regulations and software handling them is something I've worked a lot with, so this is an area of interest for me, how do you get the speed limit data? Do you have some kind of database you can get it from, or you intending to make some kind of field inventory? Also, how do you intend to handle when different speeds are close to each other (such as intersections or when you have a small road closely parallel to a large road)?

I'm not intending to steal your thunder here, it's just a subject which interests me, and which I might provide some experience in (although my experience is from Swedish and Jordanian conditions). It might also be useful when I go public with my car computer project, should i be able to convince you to participate.

 

[Harris]

@Troberg:

Google Earth - Red Dog Mine, AK
This is the largest Lead/Zinc mine in the world.

Follow the road south to the port. This is where all supplies come in and the concentrate is stored for shipping out.
The trucking operation is a fleet of 25 heavy duty Western Star's. It is this fleet, operated by NANA/Lynden Logistics, that I am building a custom management system for.

I created a stand alone utility (Geo-Zone Maker) that management will use to zone out certain (nasty) sections along this road. These zones will then be up loaded to the server database and then distributed / downloaded to Android vehicle devices within the fleet. Now management can monitor to ensure the speed limits that were defined for each zone are being adhered to - both summer and winter limits.

There is much more to this system than geo-zones, but this gives you an idea of where it is headed. In fact, my system is a complete ELD as mandated by the FMCSA in the US.

Thanks

 

[ilan]

I have used this routine for general geometry not lat / lon.

Sub CheckPointInPolygone(polx() As Double, poly() As Double, x As Double, y As Double) As Boolean
    Dim x1, y1, x2, y2, D As Double
    Dim i, ni As Int
 
    ni = 0
    x1 = polx(0)
    y1 = poly(0)
    For i = 1 To polx.Length
        If i < polx.Length Then
            x2 = polx(i)
            y2 = poly(i)
        Else
            x2 = polx(0)     ' checks the last line
            y2 = poly(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

You can replace x by lat and y by lon.
You can replace polx by a List and poly by another List and x1 = polx(i) by x1 = ListX.Get(i) etc.

Attached a small test program.

thank you for that code

if i would like to add a tolerance so if the point is on the edges i still get false where do i need to put that tolerance?

(i hope the image will explain it better )

 

[Daniel-White]

This look nice, so that mean, an example we can make an APP to work in specific city, and when the user leave the city we can trigger in the APP a message to end user with "This APP will not work in that territory" . great!!

 

[klaus]

You can have a look at this project PointInPolygonSurrounding.
The only point is that the program, in this project, returns if the point is in the polygon, in an outer surrounding within a given distance or out of the surrounding.
The code could easily modified to check the inverse.

In the CheckPointInPolygonSurroundig the program checks if the point is insides the polygon and returns 1 if yes.
If no the program checks if the point is at a distance lower than the given distance.
If yes the point is in the outer surrounding, if no it's outsides the surrounding.
This is done with this code:

If CheckPointInPolygone(polx, poly, x, y) = True Then
    Return 1
End If

You can change it to:

If CheckPointInPolygone(polx, poly, x, y) = False Then
    Return 1
End If

Then you have the same for an inner surrounding.

 

[ilan]

Thank you very much for your help @klaus i will check that example out.

 

[ilan]

i am afraid this solution will not help me much.




lets say i have 2 polygons and i want to know if they are overlapping so what am i doing i check if one of the corners of 1 polygon is inside the other and then i return = true (polygons are overlapping:

BUT thats not true because if the second polygon would be completley inside the other then NO corner would be inside the first polygon and i would get returned = FALSE
but they are overlapping:

ok so i had another idea i will check if 1 point is inside the other polygon then return = true OR the complete polygon is inside (no corners are outside the first polygon)
and like this get TRUE in both cases, GREAT i got the solution... NOT REALLY

in this case you can see that the second polygon corners are on the same 1 polygon corners and i would get TRUE (overlapping) but they are not overlapping...

is there a way to check if part of 1 polygon is overlapping the second polygon? (so check the areas of the polygons...)

i searched for the web and found AABB where i need to check from the center of 1 polygon to the other but how do i calculate the center point of a polygon??

could not figure out hot to solve my problem,... SOMEONE CAN HELP ME PLEASE?? (i was not focused enough at geometry lesson in school)

 

[Informatix]

i am afraid this solution will not help me much.




lets say i have 2 polygons and i want to know if they are overlapping so what am i doing i check if one of the corners of 1 polygon is inside the other and then i return = true (polygons are overlapping:

View attachment 44599


BUT thats not true because if the second polygon would be completley inside the other then NO corner would be inside the first polygon and i would get returned = FALSE
but they are overlapping:

View attachment 44600

ok so i had another idea i will check if 1 point is inside the other polygon then return = true OR the complete polygon is inside (no corners are outside the first polygon)
and like this get TRUE in both cases, GREAT i got the solution... NOT REALLY

View attachment 44601

in this case you can see that the second polygon corners are on the same 1 polygon corners and i would get TRUE (overlapping) but they are not overlapping...

is there a way to check if part of 1 polygon is overlapping the second polygon? (so check the areas of the polygons...)

i searched for the web and found AABB where i need to check from the center of 1 polygon to the other but how do i calculate the center point of a polygon??

could not figure out hot to solve my problem,... SOMEONE CAN HELP ME PLEASE?? (i was not focused enough at geometry lesson in school)

Did you look at the maths functions of libGDX?

 

[ilan]

Did you look at the maths functions of libGDX?

Hmmm no

Can i check 2 paths if they are overlapping with libgdx math function?

 

[Informatix]

Hmmm no

Can i check 2 paths if they are overlapping with libgdx math function?

You can do so many things that I can answer Yes without taking a great risk to be wrong.

 

[ilan]

You can do so many things that I can answer Yes without taking a great risk to be wrong.

Thank you very much @Informatix, i will take a look at it.

Can you maybe guide me to what function i should look at?

 

[Informatix]

Thank you very much @Informatix, i will take a look at it.

Can you maybe guide me to what function i should look at?

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