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

Discussion in 'Code Snippets' started by Harris, May 19, 2015.

Similar threads

B4A Code Snippet Get panel touch direction
B4A Code Snippet Mathemetics Pendulum
B4A Code Snippet Bicubic curves
B4A Question RDC query
B4A Question anti-aliasing ?
  1. Harris

    Harris Well-Known Member Licensed User

    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.

    Code:
    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
     
    Last edited: May 27, 2015
  2. Harris

    Harris Well-Known Member Licensed User

    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.
     
  3. Troberg

    Troberg Well-Known Member Licensed User

    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.
     
  4. Harris

    Harris Well-Known Member Licensed User

    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 likes this.
  5. Troberg

    Troberg Well-Known Member Licensed User

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

    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.

    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?

    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.
     
  6. klaus

    klaus Expert Licensed User

    I have used this routine for general geometry not lat / lon.
    Code:
    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.
     

    Attached Files:

    Last edited: Feb 10, 2016
  7. Harris

    Harris Well-Known Member Licensed User

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

    Harris Well-Known Member Licensed User

    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 likes this.
  9. Troberg

    Troberg Well-Known Member Licensed User

    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.
     
  10. Harris

    Harris Well-Known Member Licensed User

    @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
     
    Troberg likes this.
  11. ilan

    ilan Expert Licensed User


    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 :) )

    calc1.png
     
  12. Daniel-White

    Daniel-White Active Member Licensed User

    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" . :D great!!
     
    Beja and ilan like this.
  13. klaus

    klaus Expert Licensed User

    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:
    Code:
    If CheckPointInPolygone(polx, poly, x, y) = True Then
        
    Return 1
    End If
    You can change it to:
    Code:
    If CheckPointInPolygone(polx, poly, x, y) = False Then
        
    Return 1
    End If
    Then you have the same for an inner surrounding.
     
    Daniel-White, Beja and ilan like this.
  14. ilan

    ilan Expert Licensed User

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

    ilan Expert Licensed User

    :( 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:

    p1.png


    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:

    p2.png

    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 :(

    p3.png

    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)
     
  16. Informatix

    Informatix Expert Licensed User

    Did you look at the maths functions of libGDX?
     
  17. ilan

    ilan Expert Licensed User

    Hmmm no :oops:

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

    Informatix Expert Licensed User

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

    ilan Expert Licensed User

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

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

    Informatix Expert Licensed User

    Look at lgMathPolygon.contains or the various functions of lgMathIntersector.
     
    Beja and ilan like this.
Loading...
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice