Android Question Polygon around multiple lat/lon points

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
 

RB Smissaert

Well-Known Member
Licensed User
Longtime User
Have checked this now (in my OSM map app, actually it is a medical app) and indeed the C-shaped collection of points causes the bug you described, where the indentation is missed.
This is when the tightness factor (fAcc) is low, eg 1.
I don't think it is a major problem in my app, but I may go with your slower code.

RBS
Even with a high tighness factor (3) it doesn't do the C indent. Also with such a high factor it gets quite slow.
Luckily, I don't think it causes problems.

RBS
 
Upvote 0

MasterGy

Member
Licensed User
Even with a high tighness factor (3) it doesn't do the C indent. Also with such a high factor it gets quite slow.
Luckily, I don't think it causes problems.

RBS
Yes. That's why I wanted to suggest version 2. Version 2 (which works fine) can be sped up even further by running 'make_triangles' on multiple threads. Using multiple 'theeds'. What system does the program run on? Android phone?
 
Upvote 0

RB Smissaert

Well-Known Member
Licensed User
Longtime User
Yes. That's why I wanted to suggest version 2. Version 2 (which works fine) can be sped up even further by running 'make_triangles' on multiple threads. Using multiple 'theeds'. What system does the program run on? Android phone?
For now only on Android, likely only phones.

RBS
 
Upvote 0

MasterGy

Member
Licensed User
For now only on Android, likely only phones.

RBS
That's good. If you don't like version 2 because of its speed, I can make the triangle generation (which takes a lot of time) happen on multiple threads, and it will probably be even faster than version 1, which is admittedly wrong on strongly concave shapes .
 
Upvote 0

RB Smissaert

Well-Known Member
Licensed User
Longtime User
That's good. If you don't like version 2 because of its speed, I can make the triangle generation (which takes a lot of time) happen on multiple threads, and it will probably be even faster than version 1, which is admittedly wrong on strongly concave shapes .
Not sure now, which the version is that avoids the C shape, no indent bug.
Could you post that .bas code module and also the Main module?
I was testing with a .csv of 1103 lat/lng values and got OutOfBounds exceptions, maybe because arrays were Dimmed with fixed values of the first dimension.
Will try again with a much smaller amount of lat/lng values.
Thanks.

RBS
 
Upvote 0

emexes

Expert
Licensed User
surround the points tightly

My gut is telling me that the tightest solution will be the one with minimum area, and if you are optimizing for that, then it is starting to look a lot like the Travelling Sales Person problem, which doesn't bode well if you need the absolute best solution.

1731977214374.png


( from https://www.b4x.com/android/forum/threads/kids-vs-travelling-salespeople.136017 )
 
Last edited:
Upvote 0

RB Smissaert

Well-Known Member
Licensed User
Longtime User
My gut is telling me that the tightest solution will be the one with minimum area, and if you are optimizing for that, then it is starting to look a lot like the Travelling Sales Person problem, which doesn't bode well if you need the absolute best solution.

View attachment 158757

( from https://www.b4x.com/android/forum/threads/kids-vs-travelling-salespeople.136017 )
It doesn't have to be the tightest possible border. It just needs to give a good idea where the area is, how large it is and roughly what shape it is.
A simple bounding box won't do though, especially if I am showing neighbouring areas as that would give somewhat confusing views.
All this is on an OSM map.
I am thinking now that maybe the very easiest solution is just to show the map points and not the surrounding border, possibly with interconnecting lines.

RBS
 
Upvote 0

RB Smissaert

Well-Known Member
Licensed User
Longtime User
Super!

Convex heaps easier.

But the scenic route through more intricate approaches has certainly been interesting.

Especially that post about doing 9000 points in 30 milliseconds - that's pretty impressive, given that it's probably initially doing two 9000-point sorts.
Looking at this now, which should be easy to convert to B4A code:
If somebody has this already in B4A then I would be happy to look at that though.

RBS
 
Upvote 0

Brian Dean

Well-Known Member
Licensed User
Longtime User
Try Copilot - looks too good to be true, though.
B4X:
Sub ConvexHull(points As List) As List
    ' Sort points by x-coordinate (and by y-coordinate if x is the same)
    points.SortType("x", True)
    points.SortType("y", True)
    
    Dim lower As List
    lower.Initialize
    For Each p As Map In points
        While lower.Size >= 2 And CrossProduct(lower.Get(lower.Size - 2), lower.Get(lower.Size - 1), p) <= 0
            lower.RemoveAt(lower.Size - 1)
        Wend
        lower.Add(p)
    Next
    
    Dim upper As List
    upper.Initialize
    For i = points.Size - 1 To 0 Step -1
        Dim p As Map = points.Get(i)
        While upper.Size >= 2 And CrossProduct(upper.Get(upper.Size - 2), upper.Get(upper.Size - 1), p) <= 0
            upper.RemoveAt(upper.Size - 1)
        Wend
        upper.Add(p)
    Next
    
    ' Remove the last point of each half because it's repeated at the beginning of the other half
    lower.RemoveAt(lower.Size - 1)
    upper.RemoveAt(upper.Size - 1)
    
    ' Concatenate lower and upper hulls
    lower.AddAll(upper)
    Return lower
End Sub

Here is how to use it, apparently . . .

B4X:
Dim points As List
points.Initialize
points.Add(CreatePoint(0, 0))
points.Add(CreatePoint(1, 1))
points.Add(CreatePoint(2, 2))
points.Add(CreatePoint(0, 2))
points.Add(CreatePoint(2, 0))

Dim hull As List
hull = ConvexHull(points)
For Each p As Map In hull
    Log("Point: (" & p.Get("x") & ", " & p.Get("y") & ")")
Next

Sub CreatePoint(x As Double, y As Double) As Map
    Dim point As Map
    point.Initialize
    point.Put("x", x)
    point.Put("y", y)
    Return point
End Sub
 
Upvote 0

RB Smissaert

Well-Known Member
Licensed User
Longtime User
Try Copilot - looks too good to be true, though.
B4X:
Sub ConvexHull(points As List) As List
    ' Sort points by x-coordinate (and by y-coordinate if x is the same)
    points.SortType("x", True)
    points.SortType("y", True)
   
    Dim lower As List
    lower.Initialize
    For Each p As Map In points
        While lower.Size >= 2 And CrossProduct(lower.Get(lower.Size - 2), lower.Get(lower.Size - 1), p) <= 0
            lower.RemoveAt(lower.Size - 1)
        Wend
        lower.Add(p)
    Next
   
    Dim upper As List
    upper.Initialize
    For i = points.Size - 1 To 0 Step -1
        Dim p As Map = points.Get(i)
        While upper.Size >= 2 And CrossProduct(upper.Get(upper.Size - 2), upper.Get(upper.Size - 1), p) <= 0
            upper.RemoveAt(upper.Size - 1)
        Wend
        upper.Add(p)
    Next
   
    ' Remove the last point of each half because it's repeated at the beginning of the other half
    lower.RemoveAt(lower.Size - 1)
    upper.RemoveAt(upper.Size - 1)
   
    ' Concatenate lower and upper hulls
    lower.AddAll(upper)
    Return lower
End Sub

Here is how to use it, apparently . . .

B4X:
Dim points As List
points.Initialize
points.Add(CreatePoint(0, 0))
points.Add(CreatePoint(1, 1))
points.Add(CreatePoint(2, 2))
points.Add(CreatePoint(0, 2))
points.Add(CreatePoint(2, 0))

Dim hull As List
hull = ConvexHull(points)
For Each p As Map In hull
    Log("Point: (" & p.Get("x") & ", " & p.Get("y") & ")")
Next

Sub CreatePoint(x As Double, y As Double) As Map
    Dim point As Map
    point.Initialize
    point.Put("x", x)
    point.Put("y", y)
    Return point
End Sub
Looks way simpler than that VBA code, but will give it a try.
RBS
 
Upvote 0

RB Smissaert

Well-Known Member
Licensed User
Longtime User
Try Copilot - looks too good to be true, though.
B4X:
Sub ConvexHull(points As List) As List
    ' Sort points by x-coordinate (and by y-coordinate if x is the same)
    points.SortType("x", True)
    points.SortType("y", True)
   
    Dim lower As List
    lower.Initialize
    For Each p As Map In points
        While lower.Size >= 2 And CrossProduct(lower.Get(lower.Size - 2), lower.Get(lower.Size - 1), p) <= 0
            lower.RemoveAt(lower.Size - 1)
        Wend
        lower.Add(p)
    Next
   
    Dim upper As List
    upper.Initialize
    For i = points.Size - 1 To 0 Step -1
        Dim p As Map = points.Get(i)
        While upper.Size >= 2 And CrossProduct(upper.Get(upper.Size - 2), upper.Get(upper.Size - 1), p) <= 0
            upper.RemoveAt(upper.Size - 1)
        Wend
        upper.Add(p)
    Next
   
    ' Remove the last point of each half because it's repeated at the beginning of the other half
    lower.RemoveAt(lower.Size - 1)
    upper.RemoveAt(upper.Size - 1)
   
    ' Concatenate lower and upper hulls
    lower.AddAll(upper)
    Return lower
End Sub

Here is how to use it, apparently . . .

B4X:
Dim points As List
points.Initialize
points.Add(CreatePoint(0, 0))
points.Add(CreatePoint(1, 1))
points.Add(CreatePoint(2, 2))
points.Add(CreatePoint(0, 2))
points.Add(CreatePoint(2, 0))

Dim hull As List
hull = ConvexHull(points)
For Each p As Map In hull
    Log("Point: (" & p.Get("x") & ", " & p.Get("y") & ")")
Next

Sub CreatePoint(x As Double, y As Double) As Map
    Dim point As Map
    point.Initialize
    point.Put("x", x)
    point.Put("y", y)
    Return point
End Sub
At least 2 problems with that code:
CrossProduct
While Wend

RBS
 
Upvote 0

Brian Dean

Well-Known Member
Licensed User
Longtime User
At least 2 problems with that code:
Yes - I am looking at it now. A bit surprising as I have found Copilot to be quite good at coordinate geometry, and this (the convex hull) is a well-known problem. But it seems to have missed this one.
 
Upvote 0

emexes

Expert
Licensed User
Yes - I am looking at it now. A bit surprising as I have found Copilot to be quite good at coordinate geometry, and this (the convex hull) is a well-known problem. But it seems to have missed this one.

It took me a few iterations but eventually with CoPilot prompt:

using b4j, and remembering that do-while-loops must have test on the do line and not on the loop line, and remembering that not-condition tests should be stated with brackets around the condition eg not(condition), and remembering that "elseif" should be two separate words ie "else if", and remembering that arrays are zero-based eg for dim a(n) the last element is a(n - 1) ie the array dimension size must be one larger than the maximum element index that will be used, and that if you are going to access a(x - 1) then the array should be dimensioned to dim a(x), and that if you are going to access a(y) then the array should be dimensioned to dim a(y+1), then please write a sample program to find the convex hull of a list of n points in x() and y()

it came back with cheery and optimistic news:

Absolutely! Here is a complete B4J sample program to find the convex hull of a list of n points in x() and y(), taking into account all your specifications:

and once I deleted the call to AppStartLoop it actually ran, but only returned two hull points:

Log output:
Waiting for debugger to connect...
Program started.
Hull Point: (0.0, 0.0)
Hull Point: (3.0, 0.0)

So... close, but no cigar.

But still every day I learn something new. Today I learned that in B4J that:

B4X:
Dim sorted As Boolean
Do While Not sorted
Loop

is a syntax error :oops: and needs brackets 🤔 eg:

B4X:
Dim sorted As Boolean
Do While Not(sorted)
Loop
 
Last edited:
Upvote 0

RB Smissaert

Well-Known Member
Licensed User
Longtime User
It took me a few iterations but eventually with CoPilot prompt:



it came back with cheery and optimistic news:



and once I deleted the call to AppStartLoop it actually ran, but only returned two hull points:

Log output:
Waiting for debugger to connect...
Program started.
Hull Point: (0.0, 0.0)
Hull Point: (3.0, 0.0)

So... close, but no cigar.

But still every day I learn something new. Today I learned that in B4J that:

B4X:
Dim sorted As Boolean = False
Do While Not sorted
Loop

is a syntax error :oops: and needs brackets 🤔 eg:

B4X:
Dim sorted As Boolean = False
Do While Not(sorted)
Loop
I took this C++ code ( is it OK to put this in code block, as it is not B4A code?):

B4X:
// A C++ program to find convex hull of a set of points. Refer
// https://www.geeksforgeeks.org/orientation-3-ordered-points/
// for explanation of orientation()
#include <bits/stdc++.h>
using namespace std;
 
struct Point
{
    int x, y;
};
 
// 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
int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);
 
    if (val == 0) return 0;  // collinear
    return (val > 0)? 1: 2; // clock or counterclock wise
}
 
// Prints convex hull of a set of n points.
void convexHull(Point points[], int n)
{
    // There must be at least 3 points
    if (n < 3) return;
 
    // Initialize Result
    vector<Point> hull;
 
    // Find the leftmost point
    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;
 
    // Start from leftmost point, keep moving counterclockwise
    // until reach the start point again.  This loop runs O(h)
    // times where h is number of points in result or output.
    int p = l, q;
    do
    {
        // Add current point to result
        hull.push_back(points[p]);
 
        // Search for a point 'q' such that orientation(p, q,
        // x) is counterclockwise for all points 'x'. The idea
        // is to keep track of last visited most counterclock-
        // wise point in q. If any point 'i' is more counterclock-
        // wise than q, then update q.
        q = (p+1)%n;
        for (int i = 0; i < n; i++)
        {
           // If i is more counterclockwise than current q, then
           // update q
           if (orientation(points[p], points[i], points[q]) == 2)
               q = i;
        }
 
        // 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'
        p = q;
 
    } while (p != l);  // While we don't come to first point
 
    // Print Result
    for (int i = 0; i < hull.size(); i++)
        cout << "(" << hull[i].x << ", "
              << hull[i].y << ")\n";
}
 
// Driver program to test above functions
int main()
{
    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
                      {3, 0}, {0, 0}, {3, 3}};
    int n = sizeof(points)/sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

And came up with this B4A code (passing a list of lat/lng types):

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)
        
        If dVal = 0 Then Return 0 ' collinear
        
        Return IIf(dVal > 0, 1, 2) ' clock or counterclock wise
        
    End Sub

    '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.
    
    Log("iP: " & iP & ", iLeft: " & iLeft)

    Do While 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)

    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

I passed it a list of tLL types that are in a reversed (mirror image) C shape.
It went all well till about halfway but then it kind of turned back.
It did complete though with no errors.
4416 points returning a border list of 20 points.
Not bad for a first attempt!

RBS

RBS
 
Upvote 0

emexes

Expert
Licensed User
then it kind of turned back.

I eyeballed your code and can't see any mistranslations.

I thought I'd found a problem with finding the left-most point, but turned out the problem was with me. :rolleyes:

Are there any duplicate points in your data? I could imagine that causing a random turn-back.
 
Upvote 0

RB Smissaert

Well-Known Member
Licensed User
Longtime User
I took this C++ code ( is it OK to put this in code block, as it is not B4A code?):

B4X:
// A C++ program to find convex hull of a set of points. Refer
// https://www.geeksforgeeks.org/orientation-3-ordered-points/
// for explanation of orientation()
#include <bits/stdc++.h>
using namespace std;
 
struct Point
{
    int x, y;
};
 
// 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
int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);
 
    if (val == 0) return 0;  // collinear
    return (val > 0)? 1: 2; // clock or counterclock wise
}
 
// Prints convex hull of a set of n points.
void convexHull(Point points[], int n)
{
    // There must be at least 3 points
    if (n < 3) return;
 
    // Initialize Result
    vector<Point> hull;
 
    // Find the leftmost point
    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;
 
    // Start from leftmost point, keep moving counterclockwise
    // until reach the start point again.  This loop runs O(h)
    // times where h is number of points in result or output.
    int p = l, q;
    do
    {
        // Add current point to result
        hull.push_back(points[p]);
 
        // Search for a point 'q' such that orientation(p, q,
        // x) is counterclockwise for all points 'x'. The idea
        // is to keep track of last visited most counterclock-
        // wise point in q. If any point 'i' is more counterclock-
        // wise than q, then update q.
        q = (p+1)%n;
        for (int i = 0; i < n; i++)
        {
           // If i is more counterclockwise than current q, then
           // update q
           if (orientation(points[p], points[i], points[q]) == 2)
               q = i;
        }
 
        // 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'
        p = q;
 
    } while (p != l);  // While we don't come to first point
 
    // Print Result
    for (int i = 0; i < hull.size(); i++)
        cout << "(" << hull[i].x << ", "
              << hull[i].y << ")\n";
}
 
// Driver program to test above functions
int main()
{
    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
                      {3, 0}, {0, 0}, {3, 3}};
    int n = sizeof(points)/sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

And came up with this B4A code (passing a list of lat/lng types):

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)
       
        If dVal = 0 Then Return 0 ' collinear
       
        Return IIf(dVal > 0, 1, 2) ' clock or counterclock wise
       
    End Sub

    '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.
   
    Log("iP: " & iP & ", iLeft: " & iLeft)

    Do While 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)

    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

I passed it a list of tLL types that are in a reversed (mirror image) C shape.
It went all well till about halfway but then it kind of turned back.
It did complete though with no errors.
4416 points returning a border list of 20 points.
Not bad for a first attempt!

RBS

RBS
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
 
Upvote 0
Top