Choice of optimization algorithm for distributing lines inside a shape

Question

Consider the follow representation of a concrete slab element with reinforcement bars and holes.

I need an algorithm that automatically distributes lines over an arbitrary shape with different holes.

The main constraints are:

1. Lines cannot be outside of the region or inside a hole
2. The distance between two side-by-side lines cannot exceed a variable D
3. Lines have to be positioned on a fixed interval I, i.e. y mod I = 0, where y is the line's Y coordinate.
4. Each available point inside the shape cannot be further from a line than D/2

I want to optimize the solution by minimizing the total number of lines N. What kind of optimization algorithm would suit this problem?

I assume most approaches involves simplifying the shape into a raster (with pixel height I) and disable or enable each pixel. I thought this was an obvious LP problem and tried to set it up with GLPK, but found it very hard to describe the problem using this simplified raster for an arbitrary number of lines. I also suspect that the solution space might be too big.

I have already implemented an algorithm in C# that does the job, but not very optimized. This is how it works:

1. Create a simplified raster of the geometry
2. Calculate a score for each cell using a complicated formula that takes possible line length and distances to other rods and obstacles into account.
3. Determine which needs reinforcement (where number of free cells in y direction > D)
4. Pick the cell with the highest score that needs reinforcement, and reinforce it as far as possible in -x and +x directions
5. Repeat

Depending on the complicated formula, this works pretty well but starts giving unwanted results when putting the last few lines, since it can never move an already put line. Are there any other optimization techniques that I should have a look at?

Pharmaceutics

What does lines have to be positioned on a fixed interval mean? Obviously, it does not mean that they all have the same distance between each other (your example would contradict this). Is there a requirement on the horizontal width of the lines? I.e. what is stopping you from making very short lines only in the middle of the shape (which would give you the minimum number)? – Redcoat

@NicoSchertler It means that y mod I == 0 for each line, where y is the line's Y coordinate. You are right that I am missing a constraint here, so I added a 4th one: Each available point inside the shape cannot be further from a line than D/2. I edited the main question. The goal is that if a line collides with a hole, we want to put it next to the hole and keep its full length instead of having it cut in the middle. Hence the objective of minimizing N instead of minimizing the total length of the lines. – Pharmaceutics

In general there is no guaranteed solution of I > D, because then the space between parallel lines can be greater than D and their midpoint greater than D/2 away from each line -- is it also guaranteed that I <= D? – Ashia

"reinforce it as far as possible in -x and +x directions", so, can you explain why the first line on top of the rightmost square does not fully extends to the left ? – Highwrought

From your example, it appears that lines can be interrupted by holes. In this case, you simply put the lowest line at y = D/2; successive lines are parallel at a distance of D. This parameterizes as y = D(n + 1/2) for n = 0, 1, 2, ... What constraint isn't satisfied by this? – Exserviceman

@Ashia Yes, I <= D is guaranteed. – Pharmaceutics

@MassimilianoJanes The height of that hole is > D, so there has to be an extra line above. There is another rule saying that if a line has a break and is joint by another line, they need to overlap by a certain distance. But right now I want to focus on the main problem, i.e. the distribution of the lines, I think the overlap is something that might be easier to do it as a post-routine. – Pharmaceutics

@Exserviceman They can be interrupted by holes, but this is what I want to avoid. I want to minimize the number of lines that get interrupted by a hole. – Pharmaceutics

Answer 1

I'm not sure what follows is what you want - I'm fairly sure it's not what you had in mind - but if it sounds reasonable you might try it out.

Because the distance is simply at most d, and can be anything less than that, it seems at first blush like a greedy algorithm should work here. Always place the next line(s) so that (1) as few as possible are needed and (2) they are as far away from existing lines as possible.

Assume you have an optimal algorithm for this problem, and it places the next line(s) at distance a <= d from the last line. Say it places b lines. Our greedy algorithm will definitely place no more than b lines (since the first criterion is to place as few as possible), and if it places b lines it will place them at distance c with a <= c <= d, since it then places the lines as far as possible.

If the greedy algorithm did not do what the optimal algorithm did, it differed in one of the following ways:

1. It placed the same or fewer lines farther away. Suppose the optimal algorithm had gone on to place b' lines at distance a' away at the next step. Then these lines would be at distance a+a' and there would be b+b' lines in total. But the greedy algorithm can mimic the optimal algorithm in this case by placing b' lines at displacement a+a' by choosing c' = (a+a') - c. Since c > a and a' < d, c' < d and this is a legal placement.

2. It placed fewer lines closer together. This case is actually problematic. It is possible that this places k unnecessary lines, if any placement requires at least k lines and the farthest ones require more, and the arrangement of holes is chosen so that (e.g.) the distance it spans is a multiple of d.

So the greedy algorithm turns out not to work in case 2. However, it does in other cases. In particular, our observation in the first case is very useful: for any two placements (distance, lines) and (distance', lines'), if distance >= distance' and lines <= lines', the first placement is always to be preferred. This suggests the following algorithm:

PlaceLines(start, stop)

    // if we are close enough to the other edge,
    // don't place any more lines.
    if start + d >= stop then return ([], 0)

    // see how many lines we can place at distance
    // d from the last placed lines. no need to
    // ever place more lines than this
    nmax = min_lines_at_distance(start + d)

    // see how that selection pans out by recursively
    // seeing how line placement works after choosing
    // nmax lines at distance d from the last lines.
    optimal = PlaceLines(start + d, stop)
    optimal[0] = [d] . optimal[0]
    optimal[1] = nmax + optimal[1]

    // we only need to try fewer lines, never more
    for n = 1 to nmax do

        // find the max displacement a from the last placed
        // lines where we can place n lines.
        a = max_distance_for_lines(start, stop, n)

        if a is undefined then continue

        // see how that choice pans out by placing
        // the rest of the lines
        candidate = PlaceLines(start + a, stop)
        candidate[0] = [a] . candidate[0]
        candidate[1] = n + candidate[1]

        // replace the last best placement with the
        // one we just tried, if it turned out to be
        // better than the last
        if candidate[1] < optimal[1] then
            optimal = candidate

    // return the best placement we found
    return optimal

This can be improved by memoization by putting results (seq, lines) into a cache indexed by (start, stop). That way, we can recognize when we are trying to compute assignments that may already have been evaluated. I would expect that we'd have this case a lot, regardless of whether you use a coarse or a fine discretization for problem instances.

I don't get into details about how max_lines_at_distance and max_distance_for_lines functions might work, but maybe a word on these.

The first tells you at a given displacement how many lines are required to span the geometry. If you have pixelated your geometry and colored holes black, this would mean looking at the row of cells at the indicated displacement, considering the contiguous black line segments, and determining from there how many lines that implies.

The second tells you, for a given candidate number of lines, the maximum distance from the current position at which that number of lines can be placed. You could make this better by having it tell you the maximum distance at which that number of lines, or fewer, could be placed. If you use this improvement, you could reverse the direction in which you're iterating n and:

1. if f(start, stop, x) = a and y < x, you only need to search up to a, not stop, from then on;
2. if f(start, stop, x) is undefined and y < x, you don't need to search any more.

Note that this function can be undefined if it is impossible to place n or fewer lines anywhere between start and stop.

Note also that you can memorize separately for these functions to save repeated lookups. You can precompute max_lines_at_distance for each row and store it in a cache for later. Then, max_distance_for_lines could be a loop that checks the cache back to front inside two bounds.

Diablerie

Now this is one detailed answer, thanks! I'm going to need some time to study greedy algorithms and really understand your algorithm, but I will get back to you soon! – Pharmaceutics