Concave Hull taking all points of the polygon on the boundary

3
votes

In my work, I have to enclose some random group of points in a boundary. Convex hull was taking extra space and was not tightest shape so I modified it to relax the edges in following way:

i) Draw convex hull for the given number of points.

ii) Now for each point not on the convex hull boundary check if it can be added to the boundary (of course that changes the boundary shaping), while making sure none of the given points lies outside of the new polygon shape. (Point in Polygon algorithm)

iii) If all the points lie inside the polygon repeat step 2 for some other point.

iv) If no more point can be included on the boundary, stop.

Now, the issue is at any sample test set, all the points are getting included in the boundary. My doubts are:

i) Is this a concave hull?

ii) How is this different from, if I simply arrange the given points in anticlockwise order and draw and polygon through all of them instead of first drawing a convex hull?

iii) Is it true that for any given number of points, I can draw a non self intersection polygon through them, such that all the points lie on the boundary of the polygon?

enter image description here

enter image description here

enter image description here

enter image description here

1
c++mathematical-optimizationconvex-hull
May be a Sweep line algorithm could help. – Scheff's Cat
I wouldn't call this "concave". I believe this is called "non-intersecting" or "not self-intersecting". – Scheff's Cat
Could you please share source code about getting result image "what I am actually getting" . We are expecting the result same as image "what I am actually getting". Thanks – Banng

1 Answers

0
votes

Assuming you are interested in a 2D polytope (it can be n-D; it's just easier to explain and visualize 2D!), you need to find the four Pareto frontiers of a set of points, which result in the 'non-dominated' hull you are looking for. Why four frontiers? Consider the example below

Four Pareto frontier example

Note that you need the four frontiers (max vs. max, min vs. max, max vs. min, and min vs. min) to fully define the polytope's edges. Furthermore, note that whether the hull is convex or not depends on your points. The example above shows a frontier that is not convex and not continuous, therefore, the polytope is not convex and not continuous either. The set of the four Pareto frontiers comprises the complete polytope shape.

If you are looking to implement this yourself, it isn't too bad and just requires comparing each point against each point to compare their axes and determine which point advances both axes in a favorable direction. This is called a pairwise comparison.

For an already coded solution in C++, this should be a good place to start https://github.com/kevinduh/pareto