convex-hull-go

README

2D Convex Hull API

Given a set of points in 2D space, this API will return a valid Convex Hull polygon using a Gift Wrapping algorithm written in Go.

Definition

A Convex Hull is calculated from a set of points (with n >= 3) and defines the minimum convex polygon so that any point of the set is either inside or at the border of the polygon. More informations on Wikipedia.

Why

Convex Hull is often used in video games, allowing to find simple collision polygon from complex shapes (see below sprite). This optimization allows to use simpler and faster algorithms without impacting user experience.

Furthermore, convex polygons are in some cases a good compromise between collision box simplicity and collision mesh accuracy.

Original sprite from LuizMelo, The Convex Hull is drawn in red, it can be used as a collision polygon.

Finding such polygon can be usefull in other fields like shape analysis, linear programming and even cooking.

Here are other usefull links to learn more about applications of Convex Hull:

Collision detection in video game physics

Applications of Convex Hull

How

There are multiple algorithms to determine a convex hull, the one I used in this program is the Gift Wrapping algorithm, whose time complexity is O(mn). Other algorithms can be found on this excellent pdf.

Example

For this example, we assume that the points are not collinear. I'm not going to detail the math here, but you can find more details on the code itself, on the Wikipedia page and on this video.

I made a tool to have a visual representation of the algorithm (you can find it in the /public folder). The screenshots below were taken from this tool.

Given this set of points:

The algorithm will first take the leftmost point (point with minimal x-value):

Then rotate an imaginary line around this point until it crosses another point:

By repeating this process until we get back to the starting point, we get the Convex Hull:

The API

The API is opened on port 8080 by default and has two routes:

GET / : A static web page containing a tool to experiment with the API.

POST /convex2d : The actual route that takes a list of points in the body (JSON format) and returns the list of points to construct the 2D Convex Hull (JSON format too).

Example of input:

{ "points": [
    { "x": 239, "y": 308},
    { "x": 305, "y": 241},
    { "x": 377, "y": 321},
    { "x": 300, "y": 365},
    { "x": 302, "y": 301}
]}

The API returns:

[
    { "x": 239, "y": 308 },
    { "x": 305, "y": 241 },
    { "x": 377, "y": 321 },
    { "x": 300, "y": 365 }
]

How to start the application

If you want to test the API and the tool that comes with it, there are two built versions that you can run: one Linux and one Windows version. You can run executables without any requirement, therefore you do not need Go to be installed.

The application will start the API on port 8080, and will close it when the application is terminated.

Linux

# Clone repo
git clone https://github.com/BaptisteMiq/convex-hull-go.git
cd convex-hull-go

# Start with
./convex-hull

Windows

git clone https://github.com/BaptisteMiq/convex-hull-go.git
cd convex-hull-go
start convex-hull.exe

or

Download ZIP and start convex-hull.exe.

If you want to build from source...

This program was written in Go 1.13.

You will first need to clone the repository:

git clone https://github.com/BaptisteMiq/convex-hull-go.git
cd convex-hull-go

Then install the required Go package (gin):

go get .

You can start the API with:

go run main.go

To build the app:

env GOOS=linux go build -trimpath   # Linux
env GOOS=windows go build -trimpath # Windows

The tool

This tool can be accessed at http://localhost:8080 (when launched locally).

Click on the canvas to add a point at mouse position. The API will be called automatically and the Convex Hull will be drawn.

Author

Made by Baptiste Miquel under the MIT license.