Concave hull generator
Unite all dots under the smallest possible area. It comes with a simple demo for the Unity game engine using just gizmos.
How it works
The program has only two easy steps:
- Set a convex hull from a set of points (In the program they are the
Nodeobjects). It is very important that they all have an unique
idvalue. The hull should be a list of
Lineobjects (each line is defined by two
Nodeobjects). If you already have a set of lines you can skip the step (They don’t need to form a convex hull)
- Set a concave hull from a list of
You only need to set two constants before running the program:
- concavity : This sets how sharp you want the concave angles to be. It goes from
-1(not concave at all. in fact, the hull will be left convex) up to
+1(very sharp angles can occur. Setting concavity to
+1might result in 0º angles!)
concavityis defined as the cosine of the concave angles.
- scaleFactor : This sets how big is the area where concavities are going to be searched. The bigger, the more sharp the angles can be. Setting it to a very high value might affect the performance of the program. This value should be relative to how close to each other the points to be connected are.
For more info you can check the
Init.cs file and follow the demo 😃
Inspired by Implementation of a fast and efficient concave hull algorith, the concave hull is reached through the iteration of four basic steps:
- We find the points close to the longest edge of a hull. The distance is directly related to the value of
- We measure the angle (in reality the cosine of this angle) of every point related to this segment.
- We will select the point that gives us the widest angle/smallest cosine. If the value of the cosine is superior to the value of
concavitywe will discard this point.
- The newly found point will be used to divide the segment into two new ones. The process will be repeated until no more divisions are made.