# 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
`Node`

objects). It is very important that they all have an unique`id`

value. The hull should be a list of`Line`

objects (each line is defined by two`Node`

objects). 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
`Line`

objects.

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`+1`

might result in 0º angles!)`concavity`

is 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 😃

## Algorithm

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
`scaleFactor`

- 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
`concavity`

we 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.