Android Question Polygon around multiple lat/lon points

RB Smissaert · Nov 10, 2024

I need to write some code to get a polygon (list of lat/lng points) that surrounds a number of lat/lng points on a map.
This polygon needs to surround the points tightly, so a simple rectangle (which would be very easy to code) won't do.
This link looks promising:
https://github.com/mapbox/concaveman
And I wonder if maybe somebody of this group has already coded this for B4A.
In that case I would be very interested to see that code.

RBS

RB Smissaert · 2024-11-19T13:22:40+0000

RB Smissaert said:
Bit of improvement by changing this:

B4X:

'Find the leftmost point For i = 1 To iPoints - 1

To this:

B4X:

'Find the leftmost point For i = 0 To iPoints - 1

Not sure why it was 1 in the C++ code.

RBS

If the passed tLL list is sorted asc on Lng and asc on Lat (in this order) and have ConvexHull like this:

B4X:

Sub ConvexHull(lst_tLL As List, iPoints As Int) As List
    
    Dim i As Int
    Dim iLeft As Int
    Dim tLL As TMapLatLng
    Dim tLL_Left As TMapLatLng
    Dim iP As Int
    Dim iQ As Int
    Dim lst_tLLBorder As List
    
    'There must be at least 3 points
    If iPoints < 3 Then Return lst_tLLBorder 'return un-initialized list

    lst_tLLBorder.Initialize

'    'Find the leftmost point
'    For i = 0 To iPoints - 1
'        tLL = lst_tLL.Get(i)
'        tLL_Left = lst_tLL.Get(iLeft)
'        If tLL.fLng < tLL_Left.fLng Then
'            iLeft = i
'        End If
'    Next

    ' Start from leftmost point, keep moving counterclockwise
    ' until reach the start point again.
    
    Log("iP: " & iP & ", iLeft: " & iLeft)

    Do While True 'iP <> iLeft
        'Add current point to result
        lst_tLLBorder.Add(lst_tLL.Get(iP))

        ' Search for a point 'q' such that orientation(p, q, x) is counterclockwise for all points 'x'.
        iQ = (iP + 1) Mod iPoints
        
        For i = 0 To iPoints - 1
            'If i is more counterclockwise than current q, then update q
            'If Orientation(points(p), points(i), points(q)) = 2 Then
            If Orientation(lst_tLL.Get(iP), lst_tLL.Get(i), lst_tLL.Get(iQ)) = 2 Then
                iQ = i
            End If
        Next

        ' Now q is the most counterclockwise with respect to p
        ' Set p as q for next iteration, so that q is added to result 'hull'
        iP = iQ
        Log("iP: " & iP)
        
        If iP = iLeft Then
            Exit
        End If

    Loop
    
    Return lst_tLLBorder

    ' Print Result
'    For i As Integer = 0 To hull.Count - 1
'        Console.WriteLine("(" & hull(i).x & ", " & hull(i).y & ")")
'    Next

End Sub

Then it works fine, even with the mirror C shape map points.
The sort is easy to do as the Lat/Lng values come from a SQLite database.
It also avoids finding the lowest value of Lng.

RBS

RB Smissaert · 2024-11-19T13:29:37+0000

RB Smissaert said:

If the passed tLL list is sorted asc on Lng and asc on Lat (in this order) and have ConvexHull like this:

B4X:

Sub ConvexHull(lst_tLL As List, iPoints As Int) As List
   
    Dim i As Int
    Dim iLeft As Int
    Dim tLL As TMapLatLng
    Dim tLL_Left As TMapLatLng
    Dim iP As Int
    Dim iQ As Int
    Dim lst_tLLBorder As List
   
    'There must be at least 3 points
    If iPoints < 3 Then Return lst_tLLBorder 'return un-initialized list

    lst_tLLBorder.Initialize

'    'Find the leftmost point
'    For i = 0 To iPoints - 1
'        tLL = lst_tLL.Get(i)
'        tLL_Left = lst_tLL.Get(iLeft)
'        If tLL.fLng < tLL_Left.fLng Then
'            iLeft = i
'        End If
'    Next

    ' Start from leftmost point, keep moving counterclockwise
    ' until reach the start point again.
   
    Log("iP: " & iP & ", iLeft: " & iLeft)

    Do While True 'iP <> iLeft
        'Add current point to result
        lst_tLLBorder.Add(lst_tLL.Get(iP))

        ' Search for a point 'q' such that orientation(p, q, x) is counterclockwise for all points 'x'.
        iQ = (iP + 1) Mod iPoints
       
        For i = 0 To iPoints - 1
            'If i is more counterclockwise than current q, then update q
            'If Orientation(points(p), points(i), points(q)) = 2 Then
            If Orientation(lst_tLL.Get(iP), lst_tLL.Get(i), lst_tLL.Get(iQ)) = 2 Then
                iQ = i
            End If
        Next

        ' Now q is the most counterclockwise with respect to p
        ' Set p as q for next iteration, so that q is added to result 'hull'
        iP = iQ
        Log("iP: " & iP)
       
        If iP = iLeft Then
            Exit
        End If

    Loop
   
    Return lst_tLLBorder

    ' Print Result
'    For i As Integer = 0 To hull.Count - 1
'        Console.WriteLine("(" & hull(i).x & ", " & hull(i).y & ")")
'    Next

End Sub

Then it works fine, even with the mirror C shape map points.
The sort is easy to do as the Lat/Lng values come from a SQLite database.
It also avoids finding the lowest value of Lng.

RBS

The sort on Lat is actually not needed.
Seems to work all fine now and very fast.

RBS

emexes · 2024-11-19T13:30:35+0000

RB Smissaert said:
Bit of improvement by changing this:

B4X:

'Find the leftmost point For i = 1 To iPoints - 1

To this:

B4X:

'Find the leftmost point For i = 0 To iPoints - 1

Not sure why it was 1 in the C++ code.

RBS

That was the bit that I thought was at fault, but it's not.

iLeft is initialized to 0. This check:

B4X:

        tLL = lst_tLL.Get(i)
        tLL_Left = lst_tLL.Get(iLeft)
        If tLL.fLng < tLL_Left.fLng Then

will never be triggered when i and iLeft are both 0 (or both the same) and thus there should be no noticeable improvement in result.

emexes · 2024-11-19T13:34:27+0000

RB Smissaert said:
Seems to work all fine now and very fast.

I'm finding that it's almost working, except that the left-most point isn't the first element of the Hull list.

Which I think is due to you using a do-while-loop with the test at the top, whereas the C code has the test at the bottom.

Still chewing on that bone. Maybe I'm wrong again.

RB Smissaert · 2024-11-19T13:38:39+0000

emexes said:
I'm finding that it's almost working, except that the left-most point isn't the first element of the Hull list.

Which I think is due to you using a do-while-loop with the test at the top, whereas the C code has the test at the bottom.

Still chewing on that bone. Maybe I'm wrong again.

This works all fine it seems:

B4X:

    'Produces convex hull from a set of iPoints points.
    'lst_tLL needs to be sorted asc on Lng
    '--------------------------------------------------
Sub ConvexHull(lst_tLL As List, iPoints As Int) As List
    
    Dim i As Int
'    Dim iLeft As Int
'    Dim tLL As TMapLatLng
'    Dim tLL_Left As TMapLatLng
    Dim iP As Int
    Dim iQ As Int
    Dim lst_tLLBorder As List
    
    'There must be at least 3 points
    If iPoints < 3 Then Return lst_tLLBorder 'return un-initialized list

    lst_tLLBorder.Initialize

'    'Find the leftmost point
'    For i = 0 To iPoints - 1
'        tLL = lst_tLL.Get(i)
'        tLL_Left = lst_tLL.Get(iLeft)
'        If tLL.fLng < tLL_Left.fLng Then
'            iLeft = i
'        End If
'    Next

    ' Start from leftmost point, keep moving counterclockwise
    ' until reach the start point again.
    
    Do While True 'iP <> iLeft
        'Add current point to result
        lst_tLLBorder.Add(lst_tLL.Get(iP))

        ' Search for a point 'q' such that orientation(p, q, x) is counterclockwise for all points 'x'.
        iQ = (iP + 1) Mod iPoints
        
        For i = 0 To iPoints - 1
            'If i is more counterclockwise than current q, then update q
            'If Orientation(points(p), points(i), points(q)) = 2 Then
            If Orientation(lst_tLL.Get(iP), lst_tLL.Get(i), lst_tLL.Get(iQ)) = 2 Then
                iQ = i
            End If
        Next

        ' Now q is the most counterclockwise with respect to p
        ' Set p as q for next iteration, so that q is added to result 'hull'
        iP = iQ
        Log("iP: " & iP)
        
        If iP = 0 Then
            lst_tLLBorder.Add(lst_tLL.Get(0)) 'to close the polygon
            Exit
        End If

    Loop
    
    Return lst_tLLBorder

    ' Print Result
'    For i As Integer = 0 To hull.Count - 1
'        Console.WriteLine("(" & hull(i).x & ", " & hull(i).y & ")")
'    Next

End Sub

RBS

RB Smissaert · 2024-11-19T13:45:11+0000

RB Smissaert said:

This works all fine it seems:

B4X:

    'Produces convex hull from a set of iPoints points.
    'lst_tLL needs to be sorted asc on Lng
    '--------------------------------------------------
Sub ConvexHull(lst_tLL As List, iPoints As Int) As List
   
    Dim i As Int
'    Dim iLeft As Int
'    Dim tLL As TMapLatLng
'    Dim tLL_Left As TMapLatLng
    Dim iP As Int
    Dim iQ As Int
    Dim lst_tLLBorder As List
   
    'There must be at least 3 points
    If iPoints < 3 Then Return lst_tLLBorder 'return un-initialized list

    lst_tLLBorder.Initialize

'    'Find the leftmost point
'    For i = 0 To iPoints - 1
'        tLL = lst_tLL.Get(i)
'        tLL_Left = lst_tLL.Get(iLeft)
'        If tLL.fLng < tLL_Left.fLng Then
'            iLeft = i
'        End If
'    Next

    ' Start from leftmost point, keep moving counterclockwise
    ' until reach the start point again.
   
    Do While True 'iP <> iLeft
        'Add current point to result
        lst_tLLBorder.Add(lst_tLL.Get(iP))

        ' Search for a point 'q' such that orientation(p, q, x) is counterclockwise for all points 'x'.
        iQ = (iP + 1) Mod iPoints
       
        For i = 0 To iPoints - 1
            'If i is more counterclockwise than current q, then update q
            'If Orientation(points(p), points(i), points(q)) = 2 Then
            If Orientation(lst_tLL.Get(iP), lst_tLL.Get(i), lst_tLL.Get(iQ)) = 2 Then
                iQ = i
            End If
        Next

        ' Now q is the most counterclockwise with respect to p
        ' Set p as q for next iteration, so that q is added to result 'hull'
        iP = iQ
        Log("iP: " & iP)
       
        If iP = 0 Then
            lst_tLLBorder.Add(lst_tLL.Get(0)) 'to close the polygon
            Exit
        End If

    Loop
   
    Return lst_tLLBorder

    ' Print Result
'    For i As Integer = 0 To hull.Count - 1
'        Console.WriteLine("(" & hull(i).x & ", " & hull(i).y & ")")
'    Next

End Sub

RBS

Map points: 1104
iP: 1
iP: 4
iP: 7
iP: 18
iP: 78
iP: 89
iP: 311
iP: 376
iP: 490
iP: 788
iP: 1037
iP: 1081
iP: 1103
iP: 1102
iP: 1101
iP: 1039
iP: 1023
iP: 350
iP: 248
iP: 237
iP: 173
iP: 50
iP: 0
Time taken to get border points: 3 milli-seconds
Produced border points (note one duplicate point): 24

RBS

emexes · 2024-11-19T13:45:59+0000

RB Smissaert said:

B4X:

'    'Find the leftmost point
'    For i = 0 To iPoints - 1
'        tLL = lst_tLL.Get(i)
'        tLL_Left = lst_tLL.Get(iLeft)
'        If tLL.fLng < tLL_Left.fLng Then
'            iLeft = i
'        End If
'    Next

    ' Start from leftmost point, keep moving counterclockwise
    ' until reach the start point again.
    
    Do While True 'iP <> iLeft
        'Add current point to result
        lst_tLLBorder.Add(lst_tLL.Get(iP))

RB Smissaert said:
This works all fine it seems:

I'm having trouble imagining that working reliably if you're starting from an effectively-random point (the first point, which might not be a hull point) rather than the left-most point (which will be a hull point).

RB Smissaert · 2024-11-19T13:50:39+0000

emexes said:
I'm having trouble imagining that working reliably if you're starting from an effectively-random point (which might not be a hull point) rather than the left-most point (which will be a hull point).

It won't be random as the initial index (iP) will be 0 and that will be a point with the lowest value of Lng, so the left-most point and that will be border point.
Have tested quite a few shapes now and all seems fine.
Happy to be proven wrong though.

RBS

emexes · 2024-11-19T14:03:27+0000

RB Smissaert said:
It won't be random as the initial index (iP) will be 0 and that will be a point with the lowest value of Lng, so the left-most point and that will be border point.

Are your input points sorted into Lng order? I guess if you can rely on that being the case, then: mission accomplished!

I eventually got your earlier code working with random points, after initialising iP to be iLeft, and moving the do-while-loop test to the bottom.

RB Smissaert · 2024-11-19T14:06:47+0000

emexes said:
Are your input points sorted into Lng order? I guess if you can rely on that being the case, then: mission accomplished!

I eventually got your earlier code working with random points, after initialising iP to be iLeft, and moving the do-while-loop test to the bottom.

> Are your input points sorted into Lng order?
Yes.

>I eventually got your earlier code working with random points, after initialising iP to be iLeft, and moving the do-while-loop test to the bottom.
Could you post me your Sub ConvexHull?

RBS

emexes · 2024-11-19T14:11:22+0000

RB Smissaert said:
If the passed tLL list is sorted asc on Lng and asc on Lat (in this order)

Ah, that explains it. I didn't realise you were still sorting your input points. Sorting them got you around not initialising iP to be iLeft. If you're happy remembering to sort the points beforehand, then: "if it ain't broke, don't fix it" sounds good to me too.

Are you including the sort time in your profiling?

RB Smissaert · 2024-11-19T14:14:09+0000

emexes said:
Ah, that explains it. I didn't realise you were still sorting your input points. Sorting them got you around not initialising iP to be iLeft. If you're happy remembering to sort the points beforehand, then: "if it ain't broke, don't fix it" sounds good to me too.

Are you including the sort time in your profiling?

> Are you including the sort time in your profiling?
No.
It won't be much though, only sorting asc on Lng.

It would be neater though, not to have to rely on this sort and if you got it working without that then I am interested in your code.

RBS

emexes · 2024-11-19T14:44:54+0000

RB Smissaert said:
Could you post me your Sub ConvexHull?

No worries. It's been fun. I'm still not sure what happens if two points are on top of each other, especially if they're hull points, so feel free to give that a burl.

B4X:

'Produces convex hull of a set of iPoints points.
Sub ConvexHull(lst_tLL As List, iPoints As Int) As List
    
    Dim i As Int
    Dim iLeft As Int
    Dim tLL As TMapLatLng
    Dim tLL_Left As TMapLatLng
    Dim iP As Int
    Dim iQ As Int
    Dim lst_tLLBorder As List
    
    'There must be at least 3 points
    If iPoints < 3 Then Return lst_tLLBorder 'return un-initialized list

    lst_tLLBorder.Initialize

    'Find the leftmost point
    For i = 1 To iPoints - 1
        tLL = lst_tLL.Get(i)
        tLL_Left = lst_tLL.Get(iLeft)
        If tLL.fLng < tLL_Left.fLng Then
            iLeft = i
        End If
    Next
    
    ' Start from leftmost point, keep moving counterclockwise
    ' until reach the start point again.
    
    iP = iLeft    'hidden by obscurity within original c code: int p = l, q;
    
    Do While True
        'Add current point to result
        lst_tLLBorder.Add(lst_tLL.Get(iP))

        ' Search for a point 'q' such that orientation(p, q, x) is counterclockwise for all points 'x'.
        iQ = (iP + 1) Mod iPoints
        
        For i = 0 To iPoints - 1
            'If i is more counterclockwise than current q, then update q
            If Orientation(lst_tLL.Get(iP), lst_tLL.Get(i), lst_tLL.Get(iQ)) = 2 Then
                iQ = i
            End If
        Next

        ' Now q is the most counterclockwise with respect to p
        ' Set p as q for next iteration, so that q is added to result 'hull'
        iP = iQ

        If iP = iLeft Then
            lst_tLLBorder.Add(lst_tLL.Get(iP))    'close hull polygon
            Exit
        End If
    Loop
    
    Return lst_tLLBorder

End Sub

DonManfred · 2024-11-19T15:06:43+0000

emexes said:
No worries.

Why post the same post THREE times? #73, #74, #75

RB Smissaert · 2024-11-19T16:13:31+0000

emexes said:

No worries. It's been fun. I'm still not sure what happens if two points are on top of each other, especially if they're hull points, so feel free to give that a burl.

B4X:

'Produces convex hull of a set of iPoints points.
Sub ConvexHull(lst_tLL As List, iPoints As Int) As List
   
    Dim i As Int
    Dim iLeft As Int
    Dim tLL As TMapLatLng
    Dim tLL_Left As TMapLatLng
    Dim iP As Int
    Dim iQ As Int
    Dim lst_tLLBorder As List
   
    'There must be at least 3 points
    If iPoints < 3 Then Return lst_tLLBorder 'return un-initialized list

    lst_tLLBorder.Initialize

    'Find the leftmost point
    For i = 1 To iPoints - 1
        tLL = lst_tLL.Get(i)
        tLL_Left = lst_tLL.Get(iLeft)
        If tLL.fLng < tLL_Left.fLng Then
            iLeft = i
        End If
    Next
   
    ' Start from leftmost point, keep moving counterclockwise
    ' until reach the start point again.
   
    iP = iLeft    'hidden by obscurity within original c code: int p = l, q;
   
    Do While True
        'Add current point to result
        lst_tLLBorder.Add(lst_tLL.Get(iP))

        ' Search for a point 'q' such that orientation(p, q, x) is counterclockwise for all points 'x'.
        iQ = (iP + 1) Mod iPoints
       
        For i = 0 To iPoints - 1
            'If i is more counterclockwise than current q, then update q
            If Orientation(lst_tLL.Get(iP), lst_tLL.Get(i), lst_tLL.Get(iQ)) = 2 Then
                iQ = i
            End If
        Next

        ' Now q is the most counterclockwise with respect to p
        ' Set p as q for next iteration, so that q is added to result 'hull'
        iP = iQ

        If iP = iLeft Then
            lst_tLLBorder.Add(lst_tLL.Get(iP))    'close hull polygon
            Exit
        End If
    Loop
   
    Return lst_tLLBorder

End Sub

Thanks, that works fine indeed without the sort on Lng.
I think this is all sorted now, that is regarding the convexhull approach.
As to the much more complicated concavehull code, I think I will leave that for now.

RBS

RB Smissaert · 2024-11-19T16:15:41+0000

emexes said:

No worries. It's been fun. I'm still not sure what happens if two points are on top of each other, especially if they're hull points, so feel free to give that a burl.

B4X:

'Produces convex hull of a set of iPoints points.
Sub ConvexHull(lst_tLL As List, iPoints As Int) As List
   
    Dim i As Int
    Dim iLeft As Int
    Dim tLL As TMapLatLng
    Dim tLL_Left As TMapLatLng
    Dim iP As Int
    Dim iQ As Int
    Dim lst_tLLBorder As List
   
    'There must be at least 3 points
    If iPoints < 3 Then Return lst_tLLBorder 'return un-initialized list

    lst_tLLBorder.Initialize

    'Find the leftmost point
    For i = 1 To iPoints - 1
        tLL = lst_tLL.Get(i)
        tLL_Left = lst_tLL.Get(iLeft)
        If tLL.fLng < tLL_Left.fLng Then
            iLeft = i
        End If
    Next
   
    ' Start from leftmost point, keep moving counterclockwise
    ' until reach the start point again.
   
    iP = iLeft    'hidden by obscurity within original c code: int p = l, q;
   
    Do While True
        'Add current point to result
        lst_tLLBorder.Add(lst_tLL.Get(iP))

        ' Search for a point 'q' such that orientation(p, q, x) is counterclockwise for all points 'x'.
        iQ = (iP + 1) Mod iPoints
       
        For i = 0 To iPoints - 1
            'If i is more counterclockwise than current q, then update q
            If Orientation(lst_tLL.Get(iP), lst_tLL.Get(i), lst_tLL.Get(iQ)) = 2 Then
                iQ = i
            End If
        Next

        ' Now q is the most counterclockwise with respect to p
        ' Set p as q for next iteration, so that q is added to result 'hull'
        iP = iQ

        If iP = iLeft Then
            lst_tLLBorder.Add(lst_tLL.Get(iP))    'close hull polygon
            Exit
        End If
    Loop
   
    Return lst_tLLBorder

End Sub

> not sure what happens if two points are on top of each other
That won't happen as there is a select distinct SQL.
I for some reason I need the list without SQL then I will use a map
to sort out any duplicates.

RBS

Android Question Polygon around multiple lat/lon points

RB Smissaert

Well-Known Member

RB Smissaert

Well-Known Member

RB Smissaert

Well-Known Member

emexes

Expert

emexes

Expert

RB Smissaert

Well-Known Member

RB Smissaert

Well-Known Member

emexes

Expert

RB Smissaert

Well-Known Member

emexes

Expert

RB Smissaert

Well-Known Member

emexes

Expert

RB Smissaert

Well-Known Member

emexes

Expert

DonManfred

Expert

RB Smissaert

Well-Known Member

RB Smissaert

Well-Known Member

Similar Threads