# Android Code SnippetGeo-Zone Determination (Point in Polygon)

#### Harris

##### Expert
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.

B4X:
``````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:

#### Harris

##### Expert
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

##### Well-Known Member
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

##### Expert

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

#### Troberg

##### Well-Known Member
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

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

#### Attachments

• 13.3 KB Views: 330
Last edited:

#### Harris

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

#### Harris

##### Expert
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

• DonManfred and Troberg

#### Troberg

##### Well-Known Member
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

##### Expert
@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

#### ilan

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

##### Active Member
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!!

• Beja and ilan

#### klaus

##### Expert
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:
B4X:
``````If CheckPointInPolygone(polx, poly, x, y) = True Then
Return 1
End If``````
You can change it to:
B4X:
``````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

#### ilan

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

##### Expert 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

##### Expert 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

##### Expert
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

##### Expert
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

#### ilan

##### Expert
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

##### Expert
• 