I feel like there is an algorithm for this fill technique

Question

0.00/5 (No votes)

See more:

Hey kids, here's a brain teaser!

I have a full screen - say 800x480 at 16-bit color.

Therein, I have a 32kB window. This window allows me the memory to create up to a 128x128 bitmap at 16-bit color. Or 64x256. Or any rectangular region with that same area or less.

Creating rectangles using all available area is the ideal choice, but less area also works.

For a given screen, there are already rectangles of various sizes populating it at various locations, of various sizes, any area and potentially overlapping each other (but uncommon to do that). These rectangles must be filled *around* and otherwise untouched.

The goal is to fill the entire screen with as few rectangles as possible, each up to 32kB (128x128) in area.

C# and C++ are acceptable to answer in.

What I have tried:

The following gives me close to optimal output on the single test case I've run. If anyone can think of a way to improve it, let me know.

C++

#include <Arduino.h>
#include <ttgo.hpp>
#include <htcw_data.hpp>
using namespace arduino;
using namespace gfx;
using rect_list_t = data::simple_vector<srect16>;

rect_list_t control_rects;
rect_list_t fill_rects;
void add_split_rects(const srect16* rects, size_t rects_count, const srect16 cmp) {
    for(size_t i = 0;i<rects_count;++i) {
        const srect16& r = rects[i];
        for(const srect16* it = control_rects.cbegin();it!=control_rects.cend();++it) {
            if(cmp!=*it) {
                if(r.intersects(*it)) {
                    srect16 out_rects[4];
                    size_t out_size=r.split(*it,4,out_rects);
                    add_split_rects(out_rects,out_size,*it);    
                } else {
                    srect16 sr=r.crop((srect16)lcd.bounds());
                    // just draw it and store it as is
                    draw::rectangle(lcd,sr,color_t::white); 
                    fill_rects.push_back(sr);
                }
            }
        }
    }
}
void make_fill_rects() {
    // first pass

    // fill in the areas where the other rects weren't
    // up to 128x128 in size
    for(int y=0;y<lcd.dimensions().height;y+=128) {
        for(int x=0;x<lcd.dimensions().width;x+=128) {
            srect16 r(spoint16(x,y),ssize16(128,128));
            for(const srect16* it = control_rects.cbegin();it!=control_rects.cend();++it) {
                if(r.intersects(*it)) {
                    // here we punch a rect sized hole in another rect
                    // which returns up to 4 rects in response
                    srect16 out_rects[4];
                    size_t out_size=r.split(*it,4,out_rects);
                    add_split_rects(out_rects,out_size,*it);
                } else {
                    // make sure it's within screen bounds
                    r=r.crop((srect16)lcd.bounds());
                    // just draw it and store it as is
                    draw::rectangle(lcd,r,color_t::white); 
                    fill_rects.push_back(r);
                }
            }
        }
    }
}

// this is basically main() in normal C++
void setup() {
    Serial.begin(115200);
    lcd.initialize();
    lcd.rotation(3);
    draw::filled_rectangle(lcd,lcd.bounds(),color_t::black);
    // just add some random rects to the screen
    int ctl_count = rand()%5;
    for(int i = 0;i<ctl_count;++i) {
        srect16 r(
            spoint16(rand()%lcd.dimensions().width,rand()%lcd.dimensions().height),
            spoint16(rand()%lcd.dimensions().width,rand()%lcd.dimensions().height));
        r.normalize_inplace();
        draw::rectangle(lcd,r,color_t::red);
        control_rects.push_back(r);
    }
    make_fill_rects();
}
void loop() {
    dimmer.wake();
}

Posted 6-Jul-23 18:55pm

honey the codewitch

Updated 8-Jul-23 5:30am

v7

Add a Solution

Comments

Graeme_Grant 7-Jul-23 2:31am

So you have irregular areas to fill based on pre-drawn, possible random, rectangles, with the possibility of overlapping each other.

Each fill rectangle can only be a max size of 32kB (128 x 128 pixels x 2bytes for 16bit color); dimensions may alter but max 32KB in size.

You want a fill formula with minimum rectangles?

honey the codewitch 7-Jul-23 8:49am

Yeah. Only thing is the rect locations aren't technically random, but they are for this purpose. IRL they are laid out controls.

honey the codewitch 7-Jul-23 14:31pm

To be clear the pre-drawn untouchable rectangles may be larger than 128x128 in area. It's just fill rectangles where I'm limited to that - the ones i have to create. Other than that yes, that is my issue. Like I said I looked at the tile problem demonstration and description and it doesn't quite fit my problem. Almost, but because it doesn't a different algorithm is needed. Someone suggested a kd-tree might be useful for this, but i don't know. I've only ever used that animal for nearest color matching.

BillWoodruff 7-Jul-23 13:46pm

"a 32kB window. This window allows me the memory to create up to a 128x128 bitmap at 16-bit color. Or 64x256. Or any rectangular region with that same area or less.

Creating rectangles using all available area is the ideal choice"

This means rectangles will be different sizes ... constrained by minimum/maximum requirements ?

honey the codewitch 7-Jul-23 14:32pm

there's effectively no minimum but since the idea is to minimize the number of rectangles needed, each rectangle needs to be as big as possible, limited to 32KB in area.

BillWoodruff 7-Jul-23 14:25pm

What "doesn't work" if your first pass does not allow overlaps ?

Can you use Win GDI/+ calls and objects here ?

honey the codewitch 7-Jul-23 14:42pm

It can allow overlaps in theory, it's just suboptimal as it will draw to the display twice in some areas when once would have done. I can't use Win GDI/+ calls because this is not tied to windows. In fact the codebase is primarily meant for little IoT widgets. It *will* run on a PC, but there's little sense in doing it except for prototyping. That said, my graphics library is, while not quite as full featured as GDI+, it's at least in spitting distance in a lot of ways. The API is very rich, and I can take advantage of it.

3 solutions

Solution 3

Your articles have helped me immensely before and so I will gladly contribute back again!

I happen to have code for something similar to your teaser (NOTE: not entirely written by me but with a lot of help from a co-worker/friend a while back). I did some adjustments and it compiled fine, see the example fiddles here, the 1st one - HoneyTheCodeWitchSample [^] with no checking for existing rectangles, the second - HoneyTheCodeWitch2 [^] for existing rectangles.

The first returned 18 tiles and the second 7 tiles -

First example -

C#

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main(string[] args)
    {
        // Screen dimensions
        int screenWidth = 800;
        int screenHeight = 480;

        // Initialize a list to store the rectangles
        List<Rectangle> rectangles = new List<Rectangle>();

        // Start filling the screen
        FillScreen(screenWidth, screenHeight, rectangles);

        // Print the results
        Console.WriteLine("Number of rectangles used: " + rectangles.Count);
        foreach (Rectangle rectangle in rectangles)
        {
            Console.WriteLine("Rectangle: X=" + rectangle.X + ", Y=" + rectangle.Y + ", Width=" + rectangle.Width + ", Height=" + rectangle.Height);
        }
    }

    static void FillScreen(int screenWidth, int screenHeight, List<Rectangle> rectangles)
    {
        // Calculate the number of 128x128 rectangles that fit in the available window
        int maxRectanglesX = screenWidth / 128;
        int maxRectanglesY = screenHeight / 128;

        // Loop through the screen in a grid pattern
        for (int y = 0; y < maxRectanglesY; y++)
        {
            for (int x = 0; x < maxRectanglesX; x++)
            {
                // Calculate the position of the current rectangle
                int rectangleX = x * 128;
                int rectangleY = y * 128;

                // Create a rectangle with the calculated position and dimensions
                Rectangle rectangle = new Rectangle(rectangleX, rectangleY, 128, 128);

                // Check if the new rectangle overlaps with any existing rectangles
                bool overlaps = CheckOverlap(rectangle, rectangles);

                // If it doesn't overlap, add it to the list
                if (!overlaps)
                {
                    rectangles.Add(rectangle);
                }
            }
        }
    }

    static bool CheckOverlap(Rectangle newRectangle, List<Rectangle> rectangles)
    {
        foreach (Rectangle existingRectangle in rectangles)
        {
            // Check if the new rectangle overlaps with any existing rectangles
            if (newRectangle.Intersects(existingRectangle))
            {
                return true; // Overlap found, so return true
            }
        }

        return false; // No overlap found, so return false
    }
}

public class Rectangle
{
    public int X { get; set; }
    public int Y { get; set; }
    public int Width { get; set; }
    public int Height { get; set; }

    public Rectangle(int x, int y, int width, int height)
    {
        X = x;
        Y = y;
        Width = width;
        Height = height;
    }

    public bool Intersects(Rectangle other)
    {
        // Check if the current rectangle intersects with another rectangle
        return !(X + Width <= other.X || other.X + other.Width <= X || Y + Height <= other.Y || other.Y + other.Height <= Y);
    }
}

with an output as -

Output

Number of rectangles used: 18
Rectangle: X=0, Y=0, Width=128, Height=128
Rectangle: X=128, Y=0, Width=128, Height=128
Rectangle: X=256, Y=0, Width=128, Height=128
Rectangle: X=384, Y=0, Width=128, Height=128
Rectangle: X=512, Y=0, Width=128, Height=128
Rectangle: X=640, Y=0, Width=128, Height=128
Rectangle: X=0, Y=128, Width=128, Height=128
Rectangle: X=128, Y=128, Width=128, Height=128
Rectangle: X=256, Y=128, Width=128, Height=128
Rectangle: X=384, Y=128, Width=128, Height=128
Rectangle: X=512, Y=128, Width=128, Height=128
Rectangle: X=640, Y=128, Width=128, Height=128
Rectangle: X=0, Y=256, Width=128, Height=128
Rectangle: X=128, Y=256, Width=128, Height=128
Rectangle: X=256, Y=256, Width=128, Height=128
Rectangle: X=384, Y=256, Width=128, Height=128
Rectangle: X=512, Y=256, Width=128, Height=128
Rectangle: X=640, Y=256, Width=128, Height=128

The second example -

C#

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main(string[] args)
    {
        // Screen dimensions
        int screenWidth = 800;
        int screenHeight = 480;

        // Initialize a list to store the existing rectangles
        List<Rectangle> existingRectangles = new List<Rectangle>
        {
            new Rectangle(100, 100, 200, 100),
            new Rectangle(400, 200, 150, 150),
            new Rectangle(600, 300, 100, 50)
        };

        // Initialize a list to store the filled rectangles
        List<Rectangle> filledRectangles = new List<Rectangle>();

        // Start filling the screen
        FillScreen(screenWidth, screenHeight, existingRectangles, filledRectangles);

        // Print the results
        Console.WriteLine("Number of rectangles used: " + filledRectangles.Count);
        foreach (Rectangle rectangle in filledRectangles)
        {
            Console.WriteLine("Rectangle: X=" + rectangle.X + ", Y=" + rectangle.Y + ", Width=" + rectangle.Width + ", Height=" + rectangle.Height);
        }
    }

    static void FillScreen(int screenWidth, int screenHeight, List<Rectangle> existingRectangles, List<Rectangle> filledRectangles)
    {
        // Calculate the number of 128x128 rectangles that fit in the available window
        int maxRectanglesX = screenWidth / 128;
        int maxRectanglesY = screenHeight / 128;

        // Loop through the screen in a grid pattern
        for (int y = 0; y < maxRectanglesY; y++)
        {
            for (int x = 0; x < maxRectanglesX; x++)
            {
                // Calculate the position of the current rectangle
                int rectangleX = x * 128;
                int rectangleY = y * 128;

                // Create a rectangle with the calculated position and dimensions
                Rectangle newRectangle = new Rectangle(rectangleX, rectangleY, 128, 128);

                // Check if the new rectangle intersects with any existing rectangles
                bool overlaps = false;
                foreach (Rectangle existingRectangle in existingRectangles)
                {
                    if (newRectangle.Intersects(existingRectangle))
                    {
                        overlaps = true;
                        break;
                    }
                }

                // If it doesn't overlap, add it to the list of filled rectangles
                if (!overlaps)
                {
                    filledRectangles.Add(newRectangle);
                }
            }
        }
    }
}

public class Rectangle
{
    public int X { get; set; }
    public int Y { get; set; }
    public int Width { get; set; }
    public int Height { get; set; }

    public Rectangle(int x, int y, int width, int height)
    {
        X = x;
        Y = y;
        Width = width;
        Height = height;
    }

    public bool Intersects(Rectangle other)
    {
        // Check if the current rectangle intersects with another rectangle
        return !(X + Width <= other.X || other.X + other.Width <= X || Y + Height <= other.Y || other.Y + other.Height <= Y);
    }
}

And the output -

Output

Number of rectangles used: 7
Rectangle: X=384, Y=0, Width=128, Height=128
Rectangle: X=512, Y=0, Width=128, Height=128
Rectangle: X=640, Y=0, Width=128, Height=128
Rectangle: X=640, Y=128, Width=128, Height=128
Rectangle: X=0, Y=256, Width=128, Height=128
Rectangle: X=128, Y=256, Width=128, Height=128
Rectangle: X=256, Y=256, Width=128, Height=128

I hope this will point you in the right direction, thanks for your previous help!

UPDATE

C++

#include <iostream>
#include <vector>

struct Rectangle {
    int X;
    int Y;
    int Width;
    int Height;

    Rectangle(int x, int y, int width, int height)
        : X(x), Y(y), Width(width), Height(height)
    {
    }

    bool Intersects(const Rectangle& other) const
    {
        // Check if the current rectangle intersects with another rectangle
        return !(X + Width <= other.X || other.X + other.Width <= X || Y + Height <= other.Y || other.Y + other.Height <= Y);
    }
};

void FillScreen(int screenWidth, int screenHeight, std::vector<Rectangle>& existingRectangles, std::vector<Rectangle>& filledRectangles)
{
    // Initialize a vector of available spaces with the full screen size
    std::vector<Rectangle> availableSpaces = { Rectangle(0, 0, screenWidth, screenHeight) };

    // Loop through each available space
    for (const Rectangle& availableSpace : availableSpaces)
    {
        // Find the best fitting rectangle within the available space
        Rectangle bestFit;
        bool foundFit = false;

        // Loop through each existing rectangle
        for (const Rectangle& existingRectangle : existingRectangles)
        {
            // Check if the existing rectangle intersects with the available space
            if (existingRectangle.Intersects(availableSpace))
                continue;

            // Check if the existing rectangle is a better fit than the current best fit
            if (existingRectangle.Width <= availableSpace.Width && existingRectangle.Height <= availableSpace.Height)
            {
                // Update the best fit
                bestFit = existingRectangle;
                foundFit = true;
                break;
            }
        }

        // If a best fit was found, add it to the filled rectangles and update the available spaces
        if (foundFit)
        {
            filledRectangles.push_back(bestFit);

            // Calculate the remaining available spaces by splitting the current available space
            std::vector<Rectangle> newAvailableSpaces;

            // Calculate the remaining space above the best fit
            if (bestFit.Y - availableSpace.Y > 0)
            {
                Rectangle topSpace(availableSpace.X, availableSpace.Y, availableSpace.Width, bestFit.Y - availableSpace.Y);
                newAvailableSpaces.push_back(topSpace);
            }

            // Calculate the remaining space below the best fit
            if (availableSpace.Y + availableSpace.Height - bestFit.Y - bestFit.Height > 0)
            {
                Rectangle bottomSpace(availableSpace.X, bestFit.Y + bestFit.Height, availableSpace.Width, availableSpace.Y + availableSpace.Height - bestFit.Y - bestFit.Height);
                newAvailableSpaces.push_back(bottomSpace);
            }

            // Calculate the remaining space to the left of the best fit
            if (bestFit.X - availableSpace.X > 0)
            {
                Rectangle leftSpace(availableSpace.X, bestFit.Y, bestFit.X - availableSpace.X, bestFit.Height);
                newAvailableSpaces.push_back(leftSpace);
            }

            // Calculate the remaining space to the right of the best fit
            if (availableSpace.X + availableSpace.Width - bestFit.X - bestFit.Width > 0)
            {
                Rectangle rightSpace(bestFit.X + bestFit.Width, bestFit.Y, availableSpace.X + availableSpace.Width - bestFit.X - bestFit.Width, bestFit.Height);
                newAvailableSpaces.push_back(rightSpace);
            }

            // Update the available spaces
            availableSpaces = newAvailableSpaces;
        }
    }
}

int main()
{
    // Screen dimensions
    int screenWidth = 800;
    int screenHeight = 480;

    // Initialize a vector to store the existing rectangles
    std::vector<Rectangle> existingRectangles = {
        Rectangle(100, 100, 200, 100),
        Rectangle(400, 200, 150, 150),
        Rectangle(600, 300, 100, 50)
    };

    // Initialize a vector to store the filled rectangles
    std::vector<Rectangle> filledRectangles;

    // Start filling the screen
    FillScreen(screenWidth, screenHeight, existingRectangles, filledRectangles);

    // Print the results
    std::cout << "Number of rectangles used: " << filledRectangles.size() << std::endl;
    for (const Rectangle& rectangle : filledRectangles)
    {
        std::cout << "Rectangle: X=" << rectangle.X << ", Y=" << rectangle.Y << ", Width=" << rectangle.Width << ", Height=" << rectangle.Height << std::endl;
    }

    return 0;
}

Posted 7-Jul-23 0:04am

Andre Oosthuizen

Updated 8-Jul-23 7:19am

v3

Comments

honey the codewitch 7-Jul-23 8:52am

I'm plus +5 ing this for the sheer effort. It may solve my problem but I need to try it. It certainly looks like it works. It will take a minute to test everything so I am accepting this solution in the interim to keep people from posting more solutions. I may reject it after-the-fact if it doesn't solve the problem. No matter what happens, thank you very much for this.

Andre Oosthuizen 7-Jul-23 9:07am

You're welcome, I hope this is what you were looking for.

honey the codewitch 7-Jul-23 9:18am

I'm setting it up in C++ now, with visualization for checking. I'll let you know how it goes. It may be a bit, as I'm still waking up, drinking coffee, and poking at it periodically at the moment. Thanks again. :)

honey the codewitch 7-Jul-23 9:24am

It's not quite what I need. The issue is it that it needs to fill in irregular sections that aren't 128x128, but may be 32x200 for example. In your code you simply don't put in the rect if it overlaps. This actually gets me my first pass so your solution is partially correct. Basically what I need is another pass to go through and fill in the blank spots. However, this still won't yield optimal results, but it gets me closer.

BillWoodruff 7-Jul-23 13:41pm

Excellent on-topic response: +5

Andre Oosthuizen 8-Jul-23 6:52am

Thanks Bill!

Andre Oosthuizen 8-Jul-23 7:16am

With some help from Google and a friend, I have converted the code (Learning curve for me as well :)) to C++. This is not my forte, I have not tested the code so it might bug out on you. The code will look for already placed rectangles, irrespective of sizes and will then fill the areas needed as the best fit for each available space -

honey the codewitch 8-Jul-23 9:20am

your comment got cut off. Maybe "improve" your existing solution with the code. And thanks again. This is getting interesting.

honey the codewitch 8-Jul-23 11:33am

I've added some code in What You Tried. I think gets me really close. There may be ways I can optimize it though.

Andre Oosthuizen 8-Jul-23 13:19pm

I think the code were too large for comments, I added the code to the solution.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Graeme_Grant · Accepted Answer · 2023-07-06T20:35:00

Solution 1

First thought:
1. get a mask of the blank area
2. split into rectangular regions
3. then split those based on the 32KB limitation

Maybe do vertical, then horizontal splits, then compare counts for optimal outcome.

[thinking about how to code the sample, will update soon].

Posted 6-Jul-23 20:35pm

Graeme_Grant

Updated 6-Jul-23 20:37pm

v2

Comments

CPallini 7-Jul-23 6:01am

5.

BillWoodruff 7-Jul-23 13:47pm

where "mask" is ?

Patrice T · Accepted Answer · 2023-07-06T20:54:00

Solution 2

Quote:
I feel like there is an algorithm for this fill technique

Yes, there is an algorithm, and it is not unique. This is a tiling problem, every tiler solve similar problems every day.

Note that an algorithm is not linked to a programming language.
Your jobs is to create your own algorithm and then to translate to a program.

For a rectangle of H*W, and using a round() function than round upper:
If you can't reshape the tiles: number of tiles needed = round(H/128) * round(W/128)
if you can reshape the tiles, theorical minimum number of tiles needed = round(H/128 * W/128)
After than, your answer depend on how you are good at avoiding overlap.

Here, we help you to fix your work, but you need to tell what you have done.

[edit]
Not easy to craft an algorithm when most simple solutions are already optimum.

Simple filling with tiles 128*128 needs 28
Theorical optimum needs 24
Tiles of 480*34 needs 24
Tiles of 800*20 needs 24

Do you have sample sizes that need aleast 2 different shapes for optimum ?
Here is my code for xHarbour

dBase

WH= 480
WL= 800
TS= 128
cls
? "Simple filling with tiles "+str(TS,,,.T.)+"*"+str(TS,,,.t.)+" needs "+ str(rsup(WH/TS)*rsup(WL/TS),,,.t.)
? "Theorical optimum needs "+str(rsup(WH/TS*WL/TS),,,.t.)

TH= WH
TL= int(TS*TS/TH)
TQ= rsup(WL/TL)
? "Tiles of "+str(TH,,,.t.)+"*"+str(TL,,,.t.)+" needs "+str(TQ,,,.t.)

TH= WL
TL= int(TS*TS/TH)
TQ= rsup(WH/TL)
? "Tiles of "+str(TH,,,.t.)+"*"+str(TL,,,.t.)+" needs "+str(TQ,,,.t.)
return

function RSup(x)
	* round to upper value
	if int(x)=x
		rep=int(x)
	else
		rep=int(x)+1
	endif
	return rep

Posted 6-Jul-23 20:54pm

Patrice T

Updated 8-Jul-23 8:28am

v3

Comments

CPallini 7-Jul-23 6:02am

5.

honey the codewitch 7-Jul-23 9:37am

Thank you for pointing me to the algo. After looking it up: https://www.geeksforgeeks.org/tiling-problem-using-divide-and-conquer-algorithm/ it seems like it almost describes my problem but not quite, because the filled in tiles occupy locations that are regular in size and location - they fit in the grid. My existing rectangles do not fit in a grid, so the algorithm I linked to won't work. I could subdivide into smaller grids so that the existing rects take up multiple grid spaces, but the problem with that is the grid is very small and I'd need to recombine small rects into larger rects, which is a problem in and of itself. Once again, thank you for pointing me to this algorithm, even if it's not quite what I need.

Patrice T 7-Jul-23 12:47pm

Hi Honey,
Happy to learn that my solution lead you to useful things.

I have a problem with you.
- On 1 side you wrote numerous article and got awards for many of them., and you are MVP for years. This make me think you are seasoned programmer.
- On the other side, you seems to chock on rather simple questions (mostly student homework level).
What did I missed ?

BillWoodruff 7-Jul-23 14:18pm

"Happy to learn that my solution lead you to useful things. I have a problem with you ... you seems to chock on rather simple questions (mostly student homework level).
What did I missed ?"

You missed that that this a technical QA thread ?

honey the codewitch 7-Jul-23 14:28pm

The algorithm isn't sufficient. The reason that I didn't know the name of it is probably because I never went to school for any of this. Being self-taught, there are holes in my knowledge large enough to drive a truck through. Oh well.

BillWoodruff 8-Jul-23 23:09pm

"Being self-taught, there are holes in my knowledge"

Some of the most brilliant programmers i worked with at Adobe were self-taught ... i was self taught, but, not brilliant :), however, i was uniquely valuable at times because i had a rare speciality.

Seems to me you are a relatively young Witch who has lots of time for filing in any "holes" with academic computer-science whatever.

BillWoodruff 7-Jul-23 13:49pm

"a 32kB window. This window allows me the memory to create up to a 128x128 bitmap at 16-bit color. Or 64x256. Or any rectangular region with that same area or less.

Creating rectangles using all available area is the ideal choice"

This means rectangles will be different sizes ... constrained by minimum/maximum requirements.

Patrice T 7-Jul-23 14:01pm

Hi Bill,
Why this comment ?
I already understood what you just said.

BillWoodruff 7-Jul-23 14:14pm

Your solution does not indicate you understand this, and is not a "solution" ... yet. Voted #3.

Patrice T 7-Jul-23 14:35pm

My solution is only leads because I took the question almost as a do my homework question.
I paid attention to member name only after posting my solution.

I have no knowledge of a named algorithm for this problem.

honey the codewitch 8-Jul-23 9:24am

The solution I need is actually a lot more complicated than what you described. I really should make something in MSPaint to visualize it but it would be rather time consuming and labor intensive. The issue comes from filling around the existing rects with irregular rects. It's The Tiling Problem, but with irregular tiles (not on the grid) - in fact, the Tiling Algorithm may work if I make the grid 1x1 but it would be inefficient.

Edit: I've added code in What You've Tried that works, but may be made more optimal.

BillWoodruff 8-Jul-23 23:30pm

imho, if you need Rects that are too big for a grid cell, then you don't want a grid. in code i've done i've used GDI GraphicsPath objects .Bounds property to maintain a list of Rects that have been screened for overlap and foinf outside the grid/frame/container. You can easily calculate a running total of area used (in the frame or container), and examine each new candidate ... then, the tricky part: find where to place small Rects so the frame is completely filled.

hope this is relevant. in my code i was generating Rects of random sizes and locations a specified number of times, until a certain percentage of frame area used was reached.