This seems like a very tough problem! I would approach it by first defining two routines:
diffArea(fig, target)
computes the difference area betweenfig
andtarget
decomp(fig, p1, p2, s1, s2)
computes the two figures that can be built by replacing all the segments betweenp1
andp2
with a pair of segments of shapess1
ands2
. For instance, if there were four segments between pointsp1
andp2
infig
, thendecomp(fig, p1, p2, s1, s2)
returns the two figures that are generated by replacing those four segments with appropriately scaled versions ofs1
ands2
. There's only one way to scales1
ands2
to fill the space betweenp1
andp2
(because we're in 2-d space), and the two figures come from either ordering thems1 -> s2
ors2 -> s1
.
Given these two routines, I think an iterated local search procedure might work well. You would have the following steps:
- Set
fig
to a large bounding shape aroundtarget
- For every pair of vertices
(p1, p2)
infig
(starting with pairs with 1 segment between, then 2 segment between, ...) and for every pair(s1, s2)
of shapes:- Compute
fig1
andfig2
usingdecomp(fig, p1, p2, s1, s2)
- Let
e_fig
be the number of edges infig
ande_new
by the number of edges infig1
andfig2
- If
w1 * e_new + w2 * diffArea(fig1, target) < w1 * e_fig + w2 * diffArea(fig, target)
, replacefig
withfig1
- If
w1 * e_new + w2 * diffArea(fig2, target) < w1 * e_fig + w2 * diffArea(fig, target)
, replacefig
withfig2
- Compute
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.