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

Question

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.

Answer 1

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.

Answer 2

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)

Answer 3

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.

Answer 4

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 p₂ 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.