Shape algorithm with optimization

Question

I have a shape defined by straight line segments.

I want to simplify the shape to be constructed with straight lines but only with a finite set of slopes.

I want to minimize the amount of segments used and minimize the difference in area from the shape before and after.

I want to minimize these two things simultaneously with a user defined weight emphasizing minimizing one more than another.

minimize { J = w1(number of segments/length) + w2(difference area/length) }

Where w1 and w2 are both weights and length is the length of the new segment. I want an algorithm that does this. Any ideas?

Below I show a few pictures of how I might want it to work. Is there anything out in the literature that might help in writing an algorithm. Thanks!

Answer 1

This seems like a very tough problem! I would approach it by first defining two routines:

1. diffArea(fig, target) computes the difference area between fig and target
2. decomp(fig, p1, p2, s1, s2) computes the two figures that can be built by replacing all the segments between p1 and p2 with a pair of segments of shapes s1 and s2. For instance, if there were four segments between points p1 and p2 in fig, then decomp(fig, p1, p2, s1, s2) returns the two figures that are generated by replacing those four segments with appropriately scaled versions of s1 and s2. There's only one way to scale s1 and s2 to fill the space between p1 and p2 (because we're in 2-d space), and the two figures come from either ordering them s1 -> s2 or s2 -> s1.

Given these two routines, I think an iterated local search procedure might work well. You would have the following steps:

1. Set fig to a large bounding shape around target
2. For every pair of vertices (p1, p2) in fig (starting with pairs with 1 segment between, then 2 segment between, ...) and for every pair (s1, s2) of shapes:
   • Compute fig1 and fig2 using decomp(fig, p1, p2, s1, s2)
   • Let e_fig be the number of edges in fig and e_new by the number of edges in fig1 and fig2
   • If w1 * e_new + w2 * diffArea(fig1, target) < w1 * e_fig + w2 * diffArea(fig, target), replace fig with fig1
   • If w1 * e_new + w2 * diffArea(fig2, target) < w1 * e_fig + w2 * diffArea(fig, target), replace fig with fig2

Repeat this procedure until you've tested every pair of vertices and have found no improving replacements. This is obviously not going to give you an optimal solution, but I'd bet it will perform pretty well.

Answer 2

Well, in this case Pareto efficiency seems to be a good weight of a solution. At first glance it seems that using a discrete optimization would be apropriate. Choice of a particular algorithm depends on complexity of the figures to be shaped. For large and complex figures I would suggest using genetic algorithm.