Cover a polygonal line using the least given rectangles while keeping her continuity

Question

Given a list of points forming a polygonal line, and both height and width of a rectangle, how can I find the number and positions of all rectangles needed to cover all the points?

The rectangles should be rotated and may overlap, but must follow the path of the polyline (A rectangle may contain multiple segments of the line, but each rectangle must contain a segment that is contiguous with the previous one.)

Do the intersections on the smallest side of the rectangle, when it is possible, would be much appreciated.

All the solutions I found so far were not clean, here is the result I get:

You should see that it gives a good render in near-flat cases, but overlaps too much in big curbs. One rectangle could clearly be removed if the previous were offset.

Actually, I put a rectangle centered at width/2 along the line and rotate it using convex hull and modified rotating calipers algorithms, and reiterate starting at the intersection point of the previous rectangle and the line.

You may observe that I took inspiration from the minimum oriented rectangle bounding box algorithm, for the orientation, but it doesn't include the cutting aspect, nor the fixed size.

Thanks for your help!

Answer 1

I modified k-means to solve this. It's not fast, it's not optimal, it's not guaranteed, but (IMHO) it's a good start. There are two important modifications:

1- The distance measure

I used a Chebyshev-distance-inspired measure to see how far points are from each rectangle. To find distance from points to each rectangle, first I transformed all points to a new coordinate system, shifted to center of rectangle and rotated to its direction:

Then I used these transformed points to calculate distance:

d = max(2*abs(X)/w, 2*abs(Y)/h);

It will give equal values for all points that have same distance from each side of rectangle. The result will be less than 1.0 for points that lie inside rectangle. Now we can classify points to their closest rectangle.

2- Strategy for updating cluster centers

Each cluster center is a combination of C, center of rectangle, and a, its rotation angle. At each iteration, new set of points are assigned to a cluster. Here we have to find C and a so that rectangle covers maximum possible number of points. I don’t now if there is an analytical solution for that, but I used a statistical approach. I updated the C using weighted average of points, and used direction of first principal component of points to update a. I used results of proposed distance, powered by 500, as weight of each point in weighted average. It moves rectangle towards points that are located outside of it.

How to Find K

Initiate it with 1 and increase it till all distances from points to their corresponding rectangles become less than 1.0, meaning all points are inside a rectangle.

The results

Iterations 0, 10, 20, 30, 40, and 50 of updating cluster centers (rectangles):

Solution for test case 1:

Trying Ks: 2, 4, 6, 8, 10, and 12 for complete coverage:

Solution for test case 2:

P.M: I used parts of Chalous Road as data. It was fun downloading it from Google Maps. The I used technique described here to sample a set of equally spaced points.

Answer 2

It’s a little late and you’ve probably figured this out. But, I was free today and worked on the constraint reflected in your last edit (continuity of segments). As I said before in the comments, I suggest using a greedy algorithm. It’s composed of two parts:

1. A search algorithm that looks for furthermost point from an initial point (I used binary search algorithm), so that all points between them lie inside a rectangle of given w and h.

2. A repeated loop that finds best rectangle at each step and advances the initial point.

The pseudo code of them are like these respectively:

function getBestMBR( P, iFirst, w, h )
    nP = length(P);
    iStart = iFirst;
    iEnd = nP;
    while iStart <= iEnd
        m = floor((iStart + iEnd) / 2);
        MBR = getMBR(P[iFirst->m]);
        if (MBR.w < w) & (MBR.h < h) {*}
            iStart = m + 1;
            iLast = m;
            bestMBR = MBR;
        else
            iEnd = m - 1;
        end
    end
    return bestMBR, iLast;
end

function getRectList( P, w, h )
    nP = length(P);
    rects = [];
    iFirst = 1;
    iLast = iFirst;
    while iLast < nP
        [bestMBR, iLast] = getBestMBR(P, iFirst, w, h);
        rects.add(bestMBR.x, bestMBR.y, bestMBR.a];
        iFirst = iLast;
    end
    return rects;

Solution for test case 1:

Solution for test case 2:

Just keep in mind that it’s not meant to find the optimal solution, but finds a sub-optimal one in a reasonable time. It’s greedy after all.

Another point is that you can improve this a little in order to decrease number of rectangles. As you can see in the line marked with (*), I kept resulting rectangle in direction of MBR (Minimum Bounding Rectangle), even though you can cover larger MBRs with rectangles of same w and h if you rotate the rectangle. (1) (2)