B4J Question [Solved] Build Map Polygon From Lat/Lon List

[Harris]

Using a list of lat/lon points, how would on create a google map polygon (abmaterial) that would capture the points shown in red square programmatically?

What I am trying to accomplish:
1. Automatically create a polygon around selected points of one vehicle.
2. Use this polygon to test all other vehicles and capture their points when it has been determined they drove inside this poly (using pointinpoly function - already built).
3. Compare various params of other vehicles to base vehicle (ie. speed, braking, etc)

For simplicity, I drew this example square (4 points). I suppose it could use all 120 points and conform to the shape of this track shown...

I have been fighting with the orange example using just 4 points - the first and last point in the list - then trying to extend it to make a sqaure box.

Thanks

 

[emexes]

Are you trying to do proximity detection, as in: which vehicles ever crossed paths, even if not at the same time?

Or more interested in which vehicles are close to each other right now, in both space *and* time?

 

[Harris]

@emexes - neither.... Trying to create a properly formed geozone (polygon) based a one vehicles track across a road section.
Then using other historical data points from other vehicles, capture a record set when they passed thru this zone (not an issue). Thanks


Getting closer... but still struggling.

This image did create a pretty good ploy zone.

This one all wrong using same code...

The code:

Sub chart_chartitemclicked(Message As String)
    
    Dim sb As ABMSideBar = page.GetSideBar("SideBar")
    Dim cn As ABMContainer =  sb.Content.Component("cnt1")
    Dim us As ABMCheckbox = cn.Component("btnshowus")
    DateTime.TimeFormat = "HH:mm:ss"
    ListFindOther.Initialize
    
    Dim mark As List
    mark.Initialize
    
     Dim mes As String = Message
    
'    Log(" chart clicked "&Message)
    Log(" ECM File SIze: "&ListECM.Size)
    
    Dim idx As Int = Message.IndexOf("row:")
'    Log(" row at: "&idx)
    mes = mes.Replace("row:","")
    Dim idx As Int = mes.IndexOf(",")
    Dim val As String =""
    If idx > 0 Then
         val  = mes.SubString2(1, idx)
        Log(" rec to get: "&val)
    Else
        Log(" no index > 0")   
    End If
    If IsNumber(val) Then
        Dim val0 As Int = val - 60 '20
        If val0 < 0 Then
            val0 = 1
        End If
        Dim val1 As Int = val + 60 '20
        If val1 > ListECM.Size Then
            val1 = ListECM.Size
        End If
        
        gm1.RemoveMarkers
        gm1.RemovePolygons
        
        Log(" Number of select recs: "&(val1-val0) )
        Dim xpp As Map
        xpp.Initialize
        Dim xpp As Map = ListECM.Get(0)
'        Dim tlt As Double = xpp.Get("501") '+ 0.0009
        Dim tln As Double = xpp.Get("502") ' - 0.0005
        
        For i = val0 To val1         

            Dim mpp As Map = ListECM.Get(i)

            ListFindOther.Add(mpp)
            
            Dim lt As Double = mpp.Get("501") '+ 0.0009
            Dim ln As Double = mpp.Get("502")  + 0.0005
            
            If ln < tln Then
                Log("IF ln: "&ln&"  tln: "&tln)
            Else
                Log("else ln: "&ln&"  tln: "&tln)
                Dim tln As Double = mpp.Get("502")'  - 0.0005
                    
            End If

            If (i = val1) Then
                mark.Add(lt)
                If ln < tln Then
                    Dim temp As Double
                    temp = (tln - ln) + .005
                    mark.Add(tln - (temp))
                  
                   Log("Subtracting: "&ln&"  tln: "&tln)
                Else
                    Log("Adding "&ln&"  tln: "&tln)
                    
                    mark.Add(tln + (0.305))
                End If
            Else
                mark.Add(lt)
                mark.Add(ln)
            End If
            
            Dim lat As String = mpp.Get("501")
            Dim lon As String = mpp.Get("502")
            Dim sp As String = mpp.GetDefault("2",0)
            Dim tm As String = mpp.GetDefault("1",0)
            Dim rp As String = mpp.GetDefault("4",0)
            
            If us.State Then
                sp = NumberFormat2(sp * 0.62137 ,1,1,1,False)
            End If
            Dim dt As String = DateTime.Time(tm)
            
            Dim  legend As String = " {B} Time: "&"   "&dt&"  {BR}"
            legend = legend&" Speed: "&"   "&sp&"  {BR}"
            legend = legend&" RPM: "&"   "&rp&" {/B} {BR}"

            If i = val Then
                gm1.AddMarker( "mk"&i,lat,lon, ABM.COLOR_RED ,"Speed: "&sp&"    Time: "&"  "&dt&"  ", legend)
            Else
                gm1.AddMarker( "mk"&i,lat,lon, ABM.COLOR_Blue ,"Speed: "&sp&"    Time: "&"  "&dt&"  ",legend)
            End If   
        Next

        
        gm1.SetLocation( lat,lon)
        gm1.Refresh
            
    End If
    
    gm1.AddPolygon( "p1" , mark   , ABM.COLOR_DEEPORANGE, ABM.INTENSITY_NORMAL,  1.0,  5, ABM.COLOR_CYAN, ABM.INTENSITY_NORMAL,  0.3)

End Sub

 

[emexes]

What should happen when the GPS track crosses over itself?

Should the polygon be a (say) 20 metre wide extrusion of the track, with holes in it:

or should it be a convex polygon formed by the extreme outer GPS track points?

(apologies for the squiggly straight lines - it was quicker to draw by hand than to find the polygon tool in this image editor) (if it even exists)

 

[Harris]

My needs are quite simple. Your example is quite complicated due to many points (markers) shown in black I presume.
There is only ONE road that can be travelled (a mine haul road) - not a city with many roads as you have shown. There are NO other roads for hundreds of miles.
So I guess if one had to choose, it would be the second pic of yours, if the alligator was only one track of points...
When a set of GPS points (markers) have been presented (as in pics above), have a method to build a polygon that encompasses them all!

The width of the geozone should be at least 10 meters wider (east, west, north and south) to allow for GPS wander (inaccuracy) so other vehicles evaluated will be shown as being in this zone... So, it really doesn't matter... build a square poly - or a poly that follows the exact track with expanded width on all sides - as I am trying to accomplish.

This shouldn't be too difficult for anyone with math skills - BUT me.... ( 2 + 2 = 5)

Thanks

 

[emexes]

I shouldn't be spending time on this, but the finding-a-bounding-convex-polygon intrigued me, and I tried a couple of ideas and quickly got this far:

but it's a squared algorithm so if you have a million points it will be doing a trillion comparisons. I have ideas for speeding it up, but I'll leave them until it's worth exploring further.

 

[emexes]

My needs are quite simple. Your example is quite complicated due to many points (markers) shown in black I presume.

I needed a sample GPS track that crossed itself, and Wally GPX is my first port of call for those. ?

When a set of GPS points (markers) have been presented (as in pics above), have a method to build a polygon that encompasses them all!

Is this getting closer to what you're after (a small point-count polygon to quickly determine if a new point is possibly near a large set of target points)?

 

[Harris]

If the green was the GPS track, and the yellow was the poly created, that would work...
So what is the algorithm?

 

[emexes]

This shouldn't be too difficult for anyone with math skills - BUT me.... ( 2 + 2 = 5)

Challenge accepted. Simple solutions are often better anyway.

First question is: will we be operating anywhere near the north pole (or south pole)? Sounds like a dumb question, but the reason I ask is: spherical lon-lat geometry gets a bit whacko near the poles, and if we can stay say at least 100 km away then we can do cartesian approximations to simplify the maths immensely.

 

[Harris]

Yes near the north pole.... Red Dog Mine - Teck Resources owned...

Red Dog Mine · Alaska

Alaska

www.google.com

 

[emexes]

View attachment 102315

If the green was the GPS track, and the yellow was the poly created, that would work...
So what is the algorithm?

The algorithm was that the red outer points were points that didn't have any other points in at least one of the four quadrants {above-left, above-right, below-left, below-right}. That filter reduced the number of points we need to look at to make the polygon, from thousands to tens.

But if you are happy with the yellow polygon above, why not just find the top/bottom/left/right bounds and have a square polygon of four points based on those extremities? Expanded by say 50 metres in each direction, to be sure, to be sure.

 

[Harris]

Expanded by say 50 metres in each direction, to be sure, to be sure.

Yes... but in code? How would this be created.
We can imagine all we want... but how to code when points wander back and forth... then create a rect that bounds all this???????????????

 

[emexes]

Yes near the north pole....

Lol, that gave me a bit of a start.

But it's far enough away from the pole that we can work with longitudinal degrees being an approximately constant 41.491 km, rather than introducing sines and cosines all over the place.

(1 degree = 41.312 km at the north end and 41.671 km at the south end)

 

[emexes]

Yes... but in code? How would this be created.

Something like this:

'assume GPS track points are in arrays Lon() and Lat()

MinLon = Lon(0)
MaxLon = Lon(0)
MinLat = Lat(0)
MaxLat = Lat(0)

For I = 1 To NumTrackPoints - 1    'first point (array element 0) already done
    If Lon(I) < MinLon Then
        MinLon = Lon(I)
    ElseIf Lon(I) > MaxLon Then
        MaxLon = Lon(I)
    End If

    If Lat(I) < MinLat Then
        MinLat = Lat(I)
    ElseIf Lat(I) > MaxLat Then
        MaxLat = Lat(I)
    End If
Next I

'allow a bit extra in each direction to handle GPS wander etc:

LatBuffer = (50 / 40000000) * 360    '50 metres = 0.00045 degrees latitude (planet earth circumference is nominally 40,000 km = 40,000,000 m)
LonBuffer = LatBuffer / Cos(68 degrees)    '50 metres = 0.00120 degrees longitude (scale varies with latitude)
'probably better as: LonBuffer = LatBuffer / Cos((MinLat + MaxLat) / 2) for use at other latitudes

'bounding rectangle polygon is now the four points:

'(MinLon - LonBuffer, MinLat - LatBuffer) to
'(MinLon - LonBuffer, MaxLat + LatBuffer) to
'(MaxLon + LonBuffer, MaxLat + LatBuffer) to
'(MaxLon + LonBuffer, MinLat - LatBuffer) to
'(MinLon - LonBuffer, MinLat - LatBuffer) starting point again, if needed to close polygon

 

[emexes]

I still feel like the end goal is that you want to work out how close you are to the track, or if you are within x metres of the track, or which point of the track is closest to you.

In which case, assuming the track is say 15 km long and the trucks trudge along at 20 km/hour and we've got 1 GPS reading per second, then we're only looking at a few thousand points (not millions) and modern computers are fast enough to just go through the list of track points directly. Reducing the computer's workload by creating a lower-point-count bounding polygon is probably overkill - ie nice in theory, less so in practice - and it'd be better to reduce the programmer workload instead.

Your accuracy requirements are probably flexible enough that you won't even need to use Pythagoras, let alone trigonometry.

 

[Brian Dean]

. . . . a poly that follows the exact track with expanded width on all sides - as I am trying to accomplish.
This shouldn't be too difficult for anyone with math skills . . .

I apologise for coming late to this conversation, and I do not want to interfere with @emexes enthusiasm for finding a solution, but I believe, as @Harris suggests, that this is a fairly common mapping task with a mathematical solution. In my field of experience (agriculture) it is called "buffering" - defining a buffer zone around some shape.

The mathematical approach is to construct lines parallel to each segment of the original line, and then to find where these lines intersect. This diagram shows the principle ...

Of course, in the real world things are not that simple. Complications arise when the distance between the points is smaller that the width of the buffer zone. This produces internal loops in the buffer edges that have to be detected and removed. However this problem can be very much reduced by smoothing the original lines, which in the case of GPS generated points is usually desirable in any case.

I have written routines that do this task, but they are written in Delphi and operate on Cartesian coordinates rather than Lat/Lon. Probably 75% of the code is concerned with avoiding, or detecting and handling, difficult cases. Translating these to B4X would take some time. It might be that @emexes can find a less rigorous but sufficient solution. I know that these days I am often surprised to find tasks that used to be difficult can be easily accomplished by innovative means.

I fear that I have not been of much help. Here is one tip - to smooth and reduce the original path to a simpler line try the Ramer-Douglas-Peucker algorithm.

 

[emexes]

@emexes enthusiasm for finding a solution

Lol I'll take that compliment. ?

It might be that @emexes can find a less rigorous but sufficient solution.

They don't call me Captain Pragmatic for nothing. ☮

 

[Brian Dean]

Lol I'll take that compliment.

Good - it was intended as a compliment.

 

[Brian Dean]

Hi @Harris. Things have gone quiet on this topic, but I have been reading through it again and came across this sentence from your post #5 ...

When a set of GPS points (markers) have been presented (as in pics above), have a method to build a polygon that encompasses them all!

What you are describing here is a well-known construct called the "convex hull". That is the shape that you would get if the points were pins stuck in a board and you stretched a rubber band around the outside.

If that solution is good enough for your purposes then there are plenty of algorithms to solve it. Your application does not seem time critical so you should be able to use one of the simpler solutions. What is more you should be able to use Lat/Lon values directly.

 

[TILogistic]

I think:

This is what he meant @emexes with his crocodile. ???

Algorithm Implementation/Geometry/Convex hull/Monotone chain - Wikibooks, open books for an open world

en.wikibooks.org