# Algorithm to simplify 2D convex hull at the cost of extra area

Are there any algorithms related to the following problem that could be usefull for solving it?

I have a convex hull built on some point set. I would like to simplify it (reduce number of points) by still keeping its perimiter (or area) as small as possible. New simplified polygon should not intersect the original hull.

The basic idea I am trying to implement is to calculate for each point of a polygon perimeter added by removal of this point. And then remove the cheapest point (which removal adds minimum value to the perimiter).

So we keep iterating and removing points while added perimiter or area value is suitable and passes some creteria.

Here comes the problem:

When removing point p1 we introduce a new edge formed by previous point p0 and the next point p2. This new edge can be non-optimal or invalid (intersecting the original hull). So I would like to adjust points p0 and p2 along their edges to keep perimeter valid and small as possible.

How can I find these adjusted positions of p0 and p2 ? UPDATE:

I think my current problem is finding the optimal slope of the new (green) edge. But I am looking forward to any related suggestions and algorithms.

• Way better now, the example makes it quite clearer! – Doc Brown Jan 10 at 14:02
• Forget about slopes. These problems are best solved using vector arithmetic. Slopes and analytic geometry methods typically introduce unnecessary complexity. – Frank Hileman Jan 10 at 17:04

## 4 Answers

Consider the triangular areas we add to the polygon. To make the definition easier, let's call the line which defines the `p0` edge `e0` and the line which defines the `p2` edge `e2`.

``````e0 = p0 + u * s0 , where s0 is the slope of e0
e2 = p2 + v * s2 , where s2 is the slope of e2

area(p0p0'p1) = ||p0-p0'|| * distance(p1, e0)
``````

and

``````area(p2p2'p1) = ||p2-p2'|| * distance(p1, e2)
``````

`p2'` is given by the intersection of the line through `p0'` and `p1` with the e2. That means there is only one variable to optimize (how far away on e0 is p0'), with an upper bound (p2' can't be closer to the polygon than p2, or `v >= 0`) and a lower bound (p0' can't be closer to the polygon than p0, or `u >= 0`).

I think this should get you a nice quadratic optimization problem.

• Yes, looks like it can be solved using simple extremum search (Golden-section for example). I will give it a try, but I think there exists non-iterative mathematical solution. Thank you. – Anton Petrov Jan 10 at 16:02
• @AntonPetrov I was just too lazy to write down the computation on the PC. I also think there is a direct solution. – kutschkem Jan 10 at 16:12
• I did wrote optimization program and all solutions were lines either through (p0, p1) or through (p1, p2). So I stopped doing optimization and just pick one of these lines which suits better. I consider this is the best answer which helped me to move forward. Thank you! – Anton Petrov Jan 29 at 8:48

In my opinion it is probably easier to only consider adding points, instead of moving points, in this fashion:

For points A, B, C, D, find point B' such that ABCD is contained in AB'D and the area of AB'D is minimal

Finding B' is actually not so hard: Find the intersection of the lines defined by AB and CD, this is B'. replacing ABCD by AB'D adds the area of BB'C to the convex hull.

Then you can, following you initial intuition, greedily optimize by iteratively adding the B' points which add the least area. (or optimize in any other way)

• Warning, this approach only works if AB and CD are not parallel – kutschkem Jan 10 at 12:58
• This is exactly what I did in my first iteration on simplification problem. When this algorithm is applied iteratively it produces derivative edges non touching (!!!) initial polygon. Here comes my new problem of tighting these non optimal edges which I stated above. Please see my update. – Anton Petrov Jan 10 at 13:36
• @AntonPetrov Is that correct? No new edges are added, only existing edges made longer. In your proposed solution new edges are added. – kutschkem Jan 10 at 13:53
• Using your approach iteratively produces non-optimal polygon as I said in my previous comment. After thinking about it I changed approach and posted this question. – Anton Petrov Jan 10 at 14:05
• @AntonPetrov Your good solution in the example CAN be achieved by this approach, as long as you don't apply it greedily. Instead, you could code a variant of Dijkstra algorithm which stops when it encounters a solution with few enough edges. – kutschkem Jan 10 at 14:40

My suggestion, given p0, p1, p2... where we are going to delete p1:

``````v1 = p2 - p0
v2 = p1 - p0
v3 = project v2 over v1
v4 = v2 - v3
p0 = p0 + v4
p2 = p2 + v4
``````

The idea is that we will have a new segment from p0 to p2, and we will move towards p1 until it is ontop of it. This results in a polygon defined by less points, that has more area and that contains all the points the original had. This of course only works for convex polygons, which is what you have.

Edited multiple times, and I now realise this only handles some cases! -- See below

Here's the optimal position for your line: In this case, the new position of p2 is the intersection of the extended lines of the surrounding faces, or the stellation vertex. In many cases the faces of the optimal convex hull will coincide with faces of the original convex shape. You're choosing 6 of the original faces to keep as edges; two of these must be extended to meet at the new vertex.

In fact, for the shape you are trying to simplify, those aren't the optimal faces to keep. There's a better way to reduce the number of sides by 1: The triangle added here is substantially smaller than the triangle added in the example above. Finding the optimal solution is a matter of comparing all the different options and choosing whichever adds the least area. To reduce the number of faces to 5, this is the optimal solution: For 4 faces, this is the optimal solution: For 3 faces: Always you are choosing n faces to retain and possibly extend as outside edges, and simply choosing the best combination of faces to achieve the smallest resulting area.

There are cases that this approach is not optimal for.

For example, let's say we have a simple kite. It's quite clear there are only two possible sides we could drop according to my scheme described above, but there's clearly a better solution than either of those options:

And how would we deal with a rectangle? There are actually no faces we can simply discard, as in my technique above. Yet it is possible, nonetheless, to enclose it in a triangle.

I'll leave this answer here in case it helps toward a partial solution -- and in many cases it will give good results -- but I'm not happy with it as a complete solution.