# Android Code SnippetGeo-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.

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:

#### ilan

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

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

#### JordiCP

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

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

##### Expert
ok this code is working for me so far:

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

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

Replies
2
Views
277
Android Question String Lenght in B4A?
Replies
3
Views
342
Android Question area of polygon
Replies
39
Views
1K
Android Question Map zone query
Replies
2
Views
350