This repository contains algorithms for the convex partitioning of a pointset that were used for the CG:SHOP 2020 competition as well as the respective solutions.
All Algorithms were created and implemented by Benjamin Kahl, Semjon Kerner, Abbas Mohammed Murrey and Konstantin Jaehne, students of computer science at the Freie Universität Berlin as part of a course by Prof. Günter Rote.
A detailed explanation on our proceedings can be found in our course report here. You can find our final presentation for the course here.
The problem, as stated by this competition (see CG:SHOP 2020):
Given a set S of n points in the plane. The objective is to compute a plane graph with vertex set S (with each point in S having positive degree) that partitions the convex hull of S into the smallest possible number of convex faces. Note that collinear points are allowed on face boundaries, so all internal angles of a face are at most π
The algorithms are executed with presentation.py
usage: presentation.py [-h] [-a {wave,merged,pass,nested}] [-o] [-p] [-v] [-l LIMIT LIMIT] [-c COORD COORD] [-r [RNDM]] [-e EXPLICIT] file
positional arguments:
file - path to instance file
optional arguments:
-h, --help : Show this help message
-a {wave,merged,pass,nested}, --algorithm {wave,merged,pass,nested} : Choose algorithm to execute
-o, --overwrite : Overwrite existing solution if new one is better
-p, --plot : Show plot - Not recommended for large instances (matplotlib is slow)
-v, --verbose : Print some information
-l LIMIT LIMIT, --limit LIMIT LIMIT : Don't execute if amount of points is outside of limit
-c COORD COORD, --coordinates COORD COORD : Set coordinates of start point
-r [RNDM], --random [RNDM] : Set random seed
-e EXPLICIT, --explicit EXPLICIT : Amount of used start points in percent
We developed 4 Algorithms for this competition. With the exception of nested hulls, they are essentially evolutions of each other.
- Repeatedly creates convex hulls from unconnected vertices from outside to the inside.
- Connects these convex hulls respecting the constraints on convex faces.
- Removes unnecessary edges from the former convex hulls.
This algorithm performs very well on instances with many collinear points.
- Starting at one (random) point, it iteratively connects the closest point (by euclidean distance to the start point)
- The created graph will always maintain a convex hull after connecting a new point
- A point is connected to the most outer points on the convex hull and all points inbetween on the convex hull (except for points that are collinear on the convex hull)
- Edges between those Points on the convex hull are deleted when the resulting face will be convex
This algorithm is the fastest of all four.
We came up with the idea of starting at many start points, because we realized that Single Convex Wave produced suboptimal results on larger pointsets. Here we start multiple instances of Single Convex Wave at various locations and merge them into one whenever a collision occurs. However, the merging procedure is computationally expensive, suffers from poor code comprehensibility and produces large amounts number of edges.
This algorithm performs the worst in all aspects, but served as a stepping stone for the significantly improved Pass Based algorithm..
- This algorithm creates a polygon at given start points until all points were part of a polygon.
- Choosing start points smartly helped creating bigger polygons first. This was the intended effect.
- In contrast this algorithm does not keep convex hulls intact, leading to some following cleaning passes.
- The convex hull for all points is created.
- Islands, not connected to the convex hull, are detected and connected to the convex hull.
- Non-convex faces are repaired - those with inflex edges.
- Stray points are integrated.
- At last the algorithm tries all edges if they may be deleted, by comparing the angles to the adjacent faces.
This algorithm performed best on most instances. It takes longer than Nested Hulls and Single Convex Wave though. There is still a known bug in this algorithm, but it happens very seldom and on very large instances.. but since the competition is over, we will probably not maintain this algorithm further or fix any bugs.
Here are all four algorithms side by side on a 500 point instance:
We used Doubly-Connected Edge List (DCEL) as our main datastructure. It allowed fast traversal on the graph with reasonable overhead.
For Pass Based we calculated a set of start points for each instance. We considered multiple approaches, like clustering with kmeans or heatgrids. Eventually we settled with another approach on Delaunay Triangulation. This approach achieved very good start point distributions.
- A Delaunay triangulation is calculated on all instance points. This leaves us with a set I of edges in a triangulation.
- A second Delaunay triangulation is calculated on the midpoints of edges in I. This triangulation yields a set S of edges.
- The edges in S are ordered by the corresponding edges in I, in a way that the edge in S is directed from the midpoint of the longer edge in I to the midpoint of the shorter edge in I.
- For every midpoint the algorithm counts the outgoing edges in I and sorts the resulting list by the degree.
This approach chooses start points between all instance points in order to eliminate longer edges in a neighborhood of edges. That way bigger polygons shall be created first - not in area size, but in number of vertices. Sadly this algorithm didn't show as much of an effect on Pass Based as hoped.