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

 

[MasterGy]

@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?

Thanks Williams!

And thanks for the interest, I'll try to describe how I started.

First of all, what is the smallest polygon that encloses the points? I considered this an important starting point because there is only 1 solution. So I'll start with that. This is 'step1' in the attached drawing.
It looks for the highest point Y, and compares the angle between the other points (atan2). The reference angle of the next point found will be the angle of the previous section. It measures up to that. Accordingly, it continues to search for the point with the smallest angle difference. And so on. If the next found point is the starting point, then the fence construction is over.

After that, I started experimenting with what method could be used to insert another fence point between two adjacent fence points. I tried several variations.
-fence-Points from size based on distance,
- the distance from the geometric center between two fence points,
-distance from the section (i.e. distance parallel to the section)

It worked with all of them, but they had a common flaw: even with a very small 'accurary', there were many points that, based on the conditions, were true for two sections. So then whoever finds it first will be inserted? Therefore, the direction of the investigation was visible in the section construction, they were not aesthetic. In addition, if the new fence section was installed in a non-ideal order, pruning also occurred.

I was wondering what the condition could be for which 1 point could correspond to only one section of the fence, or none at all. 2 or more compliances are no longer good!
The basis of the idea is that the sum of the 2 sides of a triangle can never be less than or equal to the 3rd side of the triangle. Therefore, as long as there is no parallel fence wall facing us (like the two sides of an i-letter), and as long as 'accurary' is not too much, 1 point will only correspond to one section. It is clearly visible in the drawing. the length of the fence section multiplied by 'accurary'. And if this value is smaller than the sum of the distances of the two points of the fence section of the examined point, then it is suitable. And there is a good chance that it will suit him. The higher the 'accurary', the deeper it will search, the further it will go.

So you run this along the fence. And again and again. Until you finally find no more free points. If there is no other point that fits, then the work is finished.

However, the larger the 'accurary', the greater the angle two sections will form, and in this case it may happen that the new fence sections are formed in such a sequence that they intersect each other. It's wrong, ugly, and confusing. In order for the thing to work even with a large 'accurary', I added that a new fence section is only created (actually 1 section disappears and 2 new ones are created) if two fence sections do not intersect after installation. 'isinstersection' sub examines the intersection of two sections. In this way, I rule out these errors, and it is also ethically good. The 'isintersection' sub runs many times and has many operations. If we use a small 'accurary', it can be eliminated, and then the processing will be faster. But it has to be very 'accurary'.

 

[William Lancee]

@MasterGy
Thanks, that helps a lot.

Step 1 is finding what is typically called a convex hull. I like your metaphor of a "fence" - as a youth I worked on a farm and spend a lot of time mending fences.
Almost all algorithms for a Concave Hull start with a Convex Hull, so that's good. It is also the basis for the algorithm referenced by the OP. Your code for that is fast and it works.

Step 2 is the tricky part, as your experimentation shows. Deep concave shapes will require a lot of steps. In your code, 100% accuracy is sometimes not enough.

You'll find a very useful PDF discussing the issues of 'digging' into the Convex Hull.

 

[MasterGy]

@MasterGy
Thanks, that helps a lot.

Step 1 is finding what is typically called a convex hull. I like your metaphor of a "fence" - as a youth I worked on a farm and spend a lot of time mending fences.
Almost all algorithms for a Concave Hull start with a Convex Hull, so that's good. It is also the basis for the algorithm referenced by the OP. Your code for that is fast and it works.

Step 2 is the tricky part, as your experimentation shows. Deep concave shapes will require a lot of steps. In your code, 100% accuracy is sometimes not enough.
View attachment 158565

You'll find a very useful PDF discussing the issues of 'digging' into the Convex Hull.

It's great that you tested it, because I didn't even think about that. Indeed, such forms do not work well. You can increase 'accurary' in the code as you like, but it is not a good solution, because the outside and inside of the horseshoe will be different. I will still think of a solution to rule out this problem.