@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'.