Android Question Polygon around multiple lat/lon points

[RB Smissaert]

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

 

[Sandman]

I don't have any code, but I do have an idea on how I'd try to solve it. Let me know if you want me to describe it, no meaning if you're not interested.

 

[MasterGy]

Hello! I have already created a 1-bit (two-color) bitmap with different shapes scattered around. And the program looked for them all, went around them, and wrote out the x, y circle travel positions. If we start from this, we may need to draw the shape on a bitmap with a higher resolution and move it around.

 

[RB Smissaert]

I don't have any code, but I do have an idea on how I'd try to solve it. Let me know if you want me to describe it, no meaning if you're not interested.

Sure, I am interested.

RBS

 

[RB Smissaert]

Hello! I have already created a 1-bit (two-color) bitmap with different shapes scattered around. And the program looked for them all, went around them, and wrote out the x, y circle travel positions. If we start from this, we may need to draw the shape on a bitmap with a higher resolution and move it around.

I am interested in your code.
Note I am passing a list of lat/lng types (points on the map) and need in return another list of lat/lng types describing a polygon tightly surrounding those map points.

RBS

 

[MasterGy]

I am interested in your code.
Note I am passing a list of lat/lng types (points on the map) and need in return another list of lat/lng types describing a polygon tightly surrounding those map points.

RBS

ok share the position of the points and I will try to find a solution for you to get the position of the district points!

 

[RB Smissaert]

ok share the position of the points and I will try to find a solution for you to get the position of the district points!

It is just a list of lat/lngs (as a type). You can just take any sample you want.

RBS

 

[MasterGy]

no problem, send it and we'll see

 

[RB Smissaert]

no problem, send it and we'll see

OK, attached a list of Lat/Lng values.

RBS

 

[MasterGy]

I was curious about the layout. I will try to deal with it in the next few days.

 

[Sandman]

Sure, I am interested.

Ok, so this would be the principle:

Start with a polygon with four points that match the corners of the image. All four points are considered movable.

Then it's just a case of running this small loop:

For each movable point in our polygon:
- Move it 1 unit toward polygon center.
- If the changed line intersects a latlong point:
- Add another point to our polygon at intersecting location and mark it as unmovable.
- Add two new movable points as neighbours to the newly added unmovable points, at center of segment.
- If the changed line intersects a previous line in the polygon, move the polygon point back to previous position and mark it as unmovable. (So we don't "tie off" sections and make islands.)

Example conditions for when to stop the loop:
- Number of polygon segments are high enough.
- Enough time has passed.
- Median segment length is below a certain value.
...or whatever makes sense in your case.

And to illustrate, this is sort of what it would look like with the image @MasterGy posted:
(rotated and cropped to not eat too much space here)

red dots = movable points
purple dots = red dots, but shows that they were added as effect of added green dot (I chose this color poorly, check the images manually if you really want to see where the purple dots are)
green dots = unmovable points


Start at the corners:

Narrowing in, nothing happening yet:

First unmovable points added, and purple dots inbetween:

More unmovable points added, more purple dots added:

More unmovable points added, more purple dots added:

More unmovable points added, more purple dots added:

At this point I started losing my sanity trying to do this by hand. I hope it illustrates the concept well enough. (And I'm certain I've made multiple mistakes when I drew dots, but it should be correct enough to show how it would work.)

 

[RB Smissaert]

Ok, so this would be the principle:

Start with a polygon with four points that match the corners of the image. All four points are considered movable.

Then it's just a case of running this small loop:

For each movable point in our polygon:
- Move it 1 unit toward polygon center.
- If the changed line intersects a latlong point:
- Add another point to our polygon at intersecting location and mark it as unmovable.
- Add two new movable points as neighbours to the newly added unmovable points, at center of segment.
- If the changed line intersects a previous line in the polygon, move the polygon point back to previous position and mark it as unmovable. (So we don't "tie off" sections and make islands.)

Example conditions for when to stop the loop:
- Number of polygon segments are high enough.
- Enough time has passed.
- Median segment length is below a certain value.
...or whatever makes sense in your case.

And to illustrate, this is sort of what it would look like with the image @MasterGy posted:
(rotated and cropped to not eat too much space here)

red dots = movable points
purple dots = red dots, but shows that they were added as effect of added green dot (I chose this color poorly, check the images manually if you really want to see where the purple dots are)
green dots = unmovable points


Start at the corners:
View attachment 158504


Narrowing in, nothing happening yet:
View attachment 158505

First unmovable points added, and purple dots inbetween:
View attachment 158506

More unmovable points added, more purple dots added:
View attachment 158507


More unmovable points added, more purple dots added:
View attachment 158508


More unmovable points added, more purple dots added:
View attachment 158509


At this point I started losing my sanity trying to do this by hand. I hope it illustrates the concept well enough. (And I'm certain I've made multiple mistakes when I drew dots, but it should be correct enough to show how it would work.)

Thanks, that sounds like a simple approach and it will be an interesting exercise to code that.
Just 2 questions spring to mind, related to the Java code in the mentioned link:
https://github.com/mapbox/concaveman
1. Will it be quicker to translate that Java code to B4A code?
2. What will run quicker, code based on your idea or code based on that Java code?
I am away for 5 days from today, but will give both a go and report back.

RBS

 

[Sandman]

Sorry, I have no idea. I don't really know Java so I can't help you out there.

One more thing I thought of, I'm being very hand-wavy with the concept of "center of polygon", so that's an exercise for you to figure out what that is. (There are several different answers to it, depending on your needs.)

What I wanted to leave you with is that it might make sense to add nervousness to the center so it's not static at the exact same position all the time. That would probably make the shrinkwrap go further into some narrow areas, is my gut feeling.

I'd love to see the results if you actually do code this. And please consider adding a little bit of code to make a snapshot every time you move a point so you can assemble the images to an animated gif later. Both for your understanding of how well the algorithm works, but also for our entertainment - I imagine it will look cool.

 

[RB Smissaert]

Sorry, I have no idea. I don't really know Java so I can't help you out there.

One more thing I thought of, I'm being very hand-wavy with the concept of "center of polygon", so that's an exercise for you to figure out what that is. (There are several different answers to it, depending on your needs.)

What I wanted to leave you with is that it might make sense to add nervousness to the center so it's not static at the exact same position all the time. That would probably make the shrinkwrap go further into some narrow areas, is my gut feeling.

I'd love to see the results if you actually do code this. And please consider adding a little bit of code to make a snapshot every time you move a point so you can assemble the images to an animated gif later. Both for your understanding of how well the algorithm works, but also for our entertainment - I imagine it will look cool.

> I'd love to see the results if you actually do code this.
Will do.

> And please consider adding a little bit of code to make a snapshot
I can just add an optional/variable sleep, and show altered line, so you can see in slow motion what happens.

Have a feeling that the concaveman approach will be a lot faster.

RBS

 

[William Lancee]

There are several members of this forum who are really good at "wrapping" Java code. So I hope they are inspired to give it a try.
I am familiar with the convex and concave hull algorithms, but I have not implemented them. It is a well-researched topic.

I had the same thought as @Sandman - using the shrinkwrap principle. I used it in the past for turning arbitrary shapes into clickable buttons.
https://www.b4x.com/android/forum/t...scellaneous-image-shapes-into-buttons.140309/
He describes it very well. Shrinkwrap can be sucked from the inside (vacuum) or pushed from the outside (heat).
Rather then pushing the surrounding polygon towards the center, I started at the center and moved outwards keeping track of the last point passed.
After a rotational sweep of the whole field, the saved points form the hull and are in the right sequence.

This method is one pass and is extremely fast - 26 msecs for 8773 points.

But as @Sandman points out the method has downsides:
1. it is sensitive to the choice of center

And my one pass approach which has computational complexity of Ω(n) has two more limitations
2. it does not work with all shapes
3. it generates polygons with hundreds of sides

But if you want a fast way of outlining a field of points, this method works well.

I am adding this to the conversation because I find it an interesting topic and because I would like to keep the discussion going
(even if the OP is away for a few days).

P.S. I would love to see the animated version of @Sandman 's idea.

The code is compact and straight forward.

Private Sub shrinkwrap(pts As List) As List
    Dim ps As List
    ps.initialize
    bc.CopyPixelsFromBitmap(cv.CreateBitmap)
    Dim argb As ARGBColor
 
'sweep at delta degree angles (0 to 359) find point at furthest distance from center - limit the radius to surrounding rectangle
    Dim minLeftTop As point = Createpoint(Root.Width, Root.Height)
    Dim maxRightBottom As point = Createpoint(0, 0)
    For Each pt As point In pts
        If pt.x < minLeftTop.x Then minLeftTop.x = pt.x
        If pt.y < minLeftTop.y Then minLeftTop.y = pt.y
        If pt.x > maxRightBottom.x Then maxRightBottom.x = pt.x
        If pt.y > maxRightBottom.y Then maxRightBottom.y = pt.y
    Next
    Dim r As B4XRect
    r.Initialize(minLeftTop.x, minLeftTop.y, maxRightBottom.x, maxRightBottom.y)
    Dim center As point = Createpoint(.5 * (minLeftTop.x + maxRightBottom.x), .5 * (minLeftTop.y + maxRightBottom.y))

    Dim maxRadius As Float = distance(center, minLeftTop)
    For angle = 0 To 359 Step 1
        Dim savePt As point = Createpoint(0, 0)
        For radius = 5 To maxRadius Step 5
            Dim x As Float = center.x + radius * CosD(angle)
            Dim y As Float = center.y + radius * SinD(angle)
            bc.GetARGB(x, y, argb)
            If argb.r < 50 And argb.g < 50 And argb.b < 50 Then savePt = Createpoint(x, y)
        Next
        If savePt.x > 0 Or savePt.y > 0 Then ps.Add(savePt)
    Next
    Return ps
End Sub

The attached demo (150 lines of code) generates the points for testing purpose (any letter or icon can be generated).

 

[Sandman]

I had the same thought as @Sandman - using the shrinkwrap principle. I used it in the past for turning arbitrary shapes into clickable buttons.
https://www.b4x.com/android/forum/t...scellaneous-image-shapes-into-buttons.140309/
He describes it very well.

Thanks, that's kind of you. (Also, I had no idea that it's an established principle. At least I suspect it is, as you call it "the shrinkwrap principle".)

it is sensitive to the choice of center

I see you specify the center in your code. Did you consider adding nervousness to the center, and re-calculating it every iteration? Then again, perhaps it's not really applicable to your principle, as you don't do iterations the same way as my proposal. Perhaps it wouldn't change much?

 

[William Lancee]

@Sandman

'Shrink wrap' used as a term for concave hulls has been used before. I meant the idea rather than a principle. But words are important.

If you run the demo on an asymmetrical shape like "P" you'll see that the choice of the center of the encompassing rectangle is not good.
Using the centroid of points is better, but still not ideal. What if there are two or more masses connected in an oblong way?

I suppose you could make the center as a moving element that can be perturbed to find an optimal position. That will really slow things down.

If the purpose is simply to surround the shape then it doesn't matter too much. But if you want to do a "tight" shrink wrap of asymmetrical shapes you'll have to go with the established Concave Hull algorithms. I noticed that there also JavaScript versions on GitHub.

I am also curious how @MasterGy will do it.

 

[MasterGy]

I tried it.

The calculation is a bit slow, but it can be further optimized (calculate and discard the options that you definitely don't need to calculate in the future). The method seems to work. It first creates the largest possible fence and then subtracts from it based on an adjustable value.

I organized the fence-creating part into a separate code module, so as an 'engine', it can be easily integrated into other projects.

Adding points:
frame_maker.N = 0 'Here we delete the previous points (initialization, reset)
frame_maker.add_points(x,y) 'here we load all the points in a loop

The number of points can be queried at any time (frame_maker.N)

Then we create the fence with frame_maker.way(accurary). the polygon that the task is about.
If 'accurary' is 0, we get the largest possible fence. 1,2,3...and more, we are getting more and more indentations.

After this has run, we can query the fence.

frame_maker.hull_c 'this is the number of points that make up the fences. There are so many pieces
frame_maker.hull(index) . We get the index of the array that stores the positions of the points that make up the fence. points are stored in frame_maker.points(index,0). 0 X, 1, Y. This is what we uploaded at the beginning.

We can also query the range values
frame_maker.limit(x)
x:
0: smallest x value of points
1: maximum x value of points
2: x-direction extension
3: smallest y value of points
4: maximum y value of points
5: y-direction extension

After running frame_maker.way, we can create a 'bitmap' image of the entire operation. We can take a picture to see. What we see.
frame_maker.bitmapcreation(width,height) creates a 'bitmap' object with the given image size and draws on it what we can see in the example program. (circles, lines) This is a kind of feedback, display.

 

[personalapps]

Just to make all aware: I came across Turf.js open source geospatial library : https://turfjs.org/docs/api/concave. It has tons of functions and can be used directly in webview or you can host the function in nodejs environment as API. I recently used it as API to calculate Voronoi optimal points. Image from the example given on their documentation page:

 

[William Lancee]

@MasterGy

I liked to work with B4J and so I transferred your code. It works perfectly - and fast, 2 to 20 msecs per hull computation.
Your code is compact, and I can read each line. But for the life of me, I can't figure out how you're doing it - I'll study it more.

Can you outline the algorithm you use?