c++algorithmvalidationcollectionsgeometry

How to validate rectangle positions in a repeated 4-role layout with axis-based spatial constraints?

I'm working with a list of rectangles and need to validate whether each one is in the correct position based on a fixed pattern and a set of geometric constraints.

In the input list there can be any number of rectangles (e.g. 3, 7, 20, etc.), rects follow a repeating role pattern, where each rectangle’s role is determined by index % 4. This modulo-4 pattern defines their expected spatial position, repeating every 4 elements in the list.

The roles assigned by index % 4 repeat in each group. While the role itself is determined purely by index, the rectangle’s actual position is expected to visually match that role

The final group may contain fewer than 4 rectangles if the list length is not divisible by 4. This is not considered an error — as long as the remaining rectangles in that last group still follow the expected role pattern and spatial rules. This exception applies only to the final group based on the input list length.

My Goal is to write a function that returns the indexes of rectangles that are in an incorrect position.

So a rect must not cross the extended axis line of a neighbor’s edge: X constraint: cannot cross the vertical axis extending from a neighbor's edge. Y constraint: cannot cross the horizontal axis extending from a pair's edge. Rectangles can vary in size, they are not required to be uniform. This is accounted for in the logic: all position validation is based on edges and axis-aligned constraints (not fixed dimensions). A rectangle is only considered invalid if it crosses a neighbor’s extended boundary lines, regardless of its size.

I need to evaluate, among the conflicting rects, which one is in the right place according to the pattern and which one isn’t.

In other words: Identify constraint violations between two rects. Determine which rect is in the correct pattern role based on its coordinates. Only return the index of the one that actually broke the rule by crossing into forbidden space.

If anyone has suggestions for improving this evaluation logic I’d be very grateful.

Solution

  • Here is some psuedo code to tackle the problem:

    - SET ytop average Y of even index rects  
- SET ybot average Y of odd index rects
- SET ydiv average of ytop and ybot
- LOOP over even indices
    IF y >= ydiv
       MARK invalid
- LOOP over odd indices
    IF y <= ydiv
       MARK invalid
- COPY even indices to vtop
   - SORT vtop into increasing X
   - LOOP over vtop
       IF index !=  prev index + 2 AND index != next index - 2
           MARK invalid
- COPY odd indices to vbot
   - SORT vbot into increasing X
   - LOOP over vbot
       IF index !=  prev index + 2 AND index != next index - 2
           MARK invalid
- LOOP over even indices
    - IF rect overlaps prev even or next even extended vertically
           MARK invalid
- LOOP over odd indices
    - IF rect overlaps prev odd or next odd extended vertically
           MARK invalid

    As usual with psuedo code there are some tricky little details that are glossed over.

    Here is the checking C++ code:

    int cSolver::findRows()
{
    int ytoprow = 0;
    for (int i = 0; i < myRects.size(); i += 2)
        ytoprow += myRects[i].myLoc.y;
    ytoprow /= myRects.size() / 2;
    int ybotrow = 0;
    for (int i = 1; i < myRects.size(); i += 2)
        ybotrow += myRects[i].myLoc.y;
    ybotrow /= myRects.size() / 2;
    return (ytoprow + ybotrow) / 2;
}

void cSolver::checkRow(
    int oddeven,
    std::vector<x_index_t> &vRow)
{
    // sort by x
    std::sort(
        vRow.begin(), vRow.end(),
        [](const x_index_t &a, const x_index_t &b)
        {
            return a.second < b.second;
        });

    int expectedIndex = oddeven - 2;
    for (int i = 0; i < vRow.size(); i++)
    {
        expectedIndex += 2;

        // check for past end of rectangle count
        if (expectedIndex >= myRects.size())
            break;

        // check for unexpected rect
        if (vRow[i].first != expectedIndex)
        {
            //std::cout << vRow[i].first << " at " << i << " expected " << expectedIndex << "\n";

            if (vRow[i + 1].first == expectedIndex)
            {
                // expected rectangle in next location
                // found rectangle is lost
                myRects[vRow[i].first].fValid = false;

                // delay expected rect till next location
                expectedIndex -= 2;
                continue;
            }
            if (vRow[i + 1].first == expectedIndex + 2)
            {
                // next expected rect appears in next location
                // found rectangle should be elsewhere
                // mark invalid
                myRects[vRow[i].first].fValid = false;

            }
            else if (vRow[i].first == expectedIndex + 2)
            {

                // next expected rect appears here
                // expected rect missing

                // adjust expectations up
                expectedIndex += 2;
            }
        }
    }
}
void cSolver::checkOverlaps()
{
    for (int i = 1; i < myRects.size() - 1; i++)
    {
        cRect &test = myRects[i];
        if (!test.fValid)
            continue;
        cRect& prev = myRects[i-2];
        if( prev.fValid)
        if (test.myLoc.x < prev.myLoc.x + prev.myDim.x)
        {
            test.fValid = false;
            continue;
        }
        if( i == myRects.size() - 2 )
            break;
        cRect& next = myRects[i+2];
        if( next.fValid)
            if( test.myLoc.x + test.myDim.x > next.myLoc.x )
                test.fValid = false;
    }
}
void cSolver::checkPositions()
{

    // check rectangles are in their correct row
    // mark those out of position as invalid
    int yrowdiv = findRows();
    for (int i = 0; i < myRects.size(); i += 2)
        myRects[i].fValid = (myRects[i].myLoc.y <= yrowdiv);
    for (int i = 1; i < myRects.size(); i += 2)
        myRects[i].fValid = (myRects[i].myLoc.y > yrowdiv);

    // index, x of top row rectangles
    std::vector<x_index_t> vTop;
    for (int i = 0; i < myRects.size(); i += 2)
        vTop.push_back(std::make_pair(i, myRects[i].myLoc.x));
    // index, x of top row rectangles
    std::vector<x_index_t> vBot;
    for (int i = 1; i < myRects.size(); i += 2)
        vBot.push_back(std::make_pair(i, myRects[i].myLoc.x));

    // check sequence of rectangles in both rows
    checkRow(0, vTop);
    checkRow(1, vBot);

    // check for vertical overlaps
    checkOverlaps();

    // display lost rectangles ( misplaced )
    for (int i = 0; i < myRects.size(); i++)
        if (!myRects[i].fValid)
            myLost.push_back( i );
}

    The output looks like this when run on your second example

    enter image description here

    The complete application code is at https://codeberg.org/JamesBremner/LostRectangles

    The pre-built binary application is available at https://codeberg.org/JamesBremner/LostRectangles/releases