Android Question Polygon around multiple lat/lon points

R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
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
 
Sort by date Sort by votes
R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
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
 
Upvote 0
R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
The sort on Lat is actually not needed.
Seems to work all fine now and very fast.

RBS
 
Upvote 0
E

emexes

Expert
Licensed User
Longtime User

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.
 
Last edited:
Upvote 0
E

emexes

Expert
Licensed User
Longtime User
RB Smissaert said:
Seems to work all fine now and very fast.
Click to expand...

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.
 
Upvote 0
R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
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
 
Upvote 0
R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
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
 
Upvote 0
E

emexes

Expert
Licensed User
Longtime User
RB Smissaert said:
This works all fine it seems:
Click to expand...

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).
 
Upvote 0
R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
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).
Click to expand...
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
 
Upvote 0
E

emexes

Expert
Licensed User
Longtime User
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.
Click to expand...

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.
 
Upvote 0
R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
> 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
 
Upvote 0
E

emexes

Expert
Licensed User
Longtime User
RB Smissaert said:
If the passed tLL list is sorted asc on Lng and asc on Lat (in this order)
Click to expand...

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?
 
Upvote 0
R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
> 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
 
Upvote 0
E

emexes

Expert
Licensed User
Longtime User
RB Smissaert said:
Could you post me your Sub ConvexHull?
Click to expand...

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
 
Upvote 0
R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
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
 
Upvote 0
R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
> 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
 
Upvote 0
E

emexes

Expert
Licensed User
Longtime User
emexes said:
I'm still not sure what happens if two points are on top of each other
Click to expand...

I can see that if points 1 and 2, or 2 and 3, are equal (on top of each other), then dVal will return 0.

Still trying to work out what happens if points 1 and 3 are equal.

If points 1 and 3 are equal, then can substitute point 3 for point 1, at which would make the two factors of the first product the same as the two factors of the second product, BUT NEGATIVE, and two negatives make a positive, and thus the two products will be the same, and subtracting same from same will return 0.

So, somewhat serendipitously, the problem of points on top of each other appears to take care of itself. I think worst case is that if you had only three points and they were all the same, then the returned hull would be those same three points in the same order (not that it matters), with 0 length perimeter enclosing 0 area.

B4X: 
' To find orientation of ordered triplet (p, q, r).
' The function returns following values
' 0 --> p, q and r are collinear
' 1 --> Clockwise
' 2 --> Counterclockwise 
Sub Orientation(tLL1 As TMapLatLng, tLL2 As TMapLatLng, tLL3 As TMapLatLng) As Double
  
        Dim dVal As Double = (tLL2.fLat - tLL1.fLat) * (tLL3.fLng - tLL2.fLng) - (tLL2.fLng - tLL1.fLng) * (tLL3.fLat - tLL2.fLat)
 
Last edited:
Upvote 0
R

RB Smissaert

Well-Known Member
Licensed User
Longtime User
Just one final(?) remark:
This is one of the nicest bits of code I have seen.
Just 2 very small Subs, sorting out a complex task very fast.

RBS
Thanks for working out that duplicate points are not a problem.
Will do some testing to double confirm that.

RBS
 
Upvote 0
You must log in or register to reply here.

Similar Threads

  • Article
B4A Class [B4X] GPSPolyMap - check if GPS location is inside a polygon
Replies
9
Views
8K
TILogistic
R
  • Question
Android Question point in polygon with spatialite
Replies
3
Views
3K
RB Smissaert
R
  • Article
Android Code Snippet [B4X] Find distance between two points (Lat/Lon)
Replies
9
Views
6K
mw71
M
D
  • Question
Android Question Polygon calculation
Replies
5
Views
4K
wonder
  • Article
Android Code Snippet Geo-Zone Determination (Point in Polygon)
2
Replies
25
Views
16K
ilan
Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…