Convex Hull
A convex hull of a shape is defined as:
Concave Hull
A concave hull is visualized using the red line in the image below (the blue line visualizes the convex hull). Intuitively, it is a polygon which embraces all the points, but has less (minimal?) area compared to the convex hull. As a result, the polygon's boundary length is longer.
A concave hull may be the solution for some real-world problems (e.g. finding the reasonable boundary of a city).
I have failed to find a proper definition, algorithm and practical solution for the notion of a Concave Hull. The Grass Wiki has some descriptions and images, and there is a commercial solution in concavehull.com.
Any ideas, algorithms and links?
أكثر...
A convex hull of a shape is defined as:
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X (Wikipedia)
Wikipedia visualizes it nicely using a rubber band analogy (image below), and there are some good algorithms to compute it.
Concave Hull
A concave hull is visualized using the red line in the image below (the blue line visualizes the convex hull). Intuitively, it is a polygon which embraces all the points, but has less (minimal?) area compared to the convex hull. As a result, the polygon's boundary length is longer.
A concave hull may be the solution for some real-world problems (e.g. finding the reasonable boundary of a city).
I have failed to find a proper definition, algorithm and practical solution for the notion of a Concave Hull. The Grass Wiki has some descriptions and images, and there is a commercial solution in concavehull.com.
Any ideas, algorithms and links?
أكثر...