Decompose a rectangle with holes

Question

I have a large rectangle, from which I want to subtract several smaller rectangles. How can I calculate the resulting geometry as a list of rectangles?

EX: In this image, the red rectangle is the rectangle I want to subtract from, and the black rectangles are the subtractions. The green rectangles would be one valid result set.

The rectangles are always axis-aligned and their Left, Top, Width, and Height is always a whole number
The subtractions might intersect each other
The resulting rectangles should not intersect each other
The result set doesn't need to be minimal

Example method signature:

public static IEnumerable<Rectangle> Subtract(this Rectangle bounds, IList<Rectangle> subtractions)

You use a "Path" (of Shape). You create a GeometryGroup and assign it to Path.Data. Then you add RectangleGeometries to GeometryGroup.Children. That, and any subsequent changes are reflected in the Group's "Bounds" property (a Rect); which encloses all the geometry with any offset within Path. — Gerry Schmitz
– Gerry Schmitz, Commented Feb 20 at 20:57
The origin of a shape is the top left corner. X-Axis positive is left to right. Y-Axis positive is from top to bottom. Most people get errors an forget Y-Axis is top to bottom. — jdweng
– jdweng, Commented Feb 20 at 22:42

Idle_Mind · Accepted Answer · 2025-02-21 18:12:41Z

0

Here's an approach using Region, GraphicsPath, and GetRegionScans(). It should get you pretty close to an answer:

Code:

public partial class Form2 : Form
{

    GraphicsPath gp = new GraphicsPath();
    List<Rectangle> recs = new List<Rectangle>();

    public Form2()
    {
        InitializeComponent();
    }

    private void Form2_Load(object sender, EventArgs e)
    {
        GraphicsPath redGP = new GraphicsPath();
        Rectangle red = new Rectangle(new Point(12, 44), new Size(396, 323));
        redGP.AddRectangle(red);
        Region result = new Region(redGP);          


        List<Rectangle> subtractions = new List<Rectangle>();
        subtractions.Add(new Rectangle(new Point(114, 99), new Size(77, 78)));
        subtractions.Add(new Rectangle(new Point(92, 231), new Size(166, 66)));
        subtractions.Add(new Rectangle(new Point(239, 27), new Size(140, 102)));
        subtractions.Add(new Rectangle(new Point(348, 7), new Size(84, 96)));
        foreach (Rectangle sub in subtractions)
        {
            GraphicsPath subGP = new GraphicsPath();
            subGP.AddRectangle(sub);
            Region subRgn = new Region(subGP);
            result.Exclude(subRgn);
        }

        RectangleF[] scans = result.GetRegionScans(new Matrix());
        gp.AddRectangles(scans);
        gp.CloseAllFigures();

        foreach (RectangleF recF in scans)
        {
            Rectangle r = Rectangle.Round(recF);
            r.Inflate(-1, -1);
            recs.Add(r);
        }                        
    }

    private void pictureBox1_Paint(object sender, PaintEventArgs e)
    {                        
        e.Graphics.FillPath(Brushes.Green, gp);
        using(Pen p = new Pen(Brushes.Red, 5))
        {
            e.Graphics.DrawRectangle(p, Rectangle.Round(gp.GetBounds()));
        }            
        foreach (Rectangle rec in recs)
        {
            e.Graphics.DrawRectangle(Pens.Black, rec);
        }
    }
    
}

answered Feb 21 at 18:12

Idle_Mind

39.3k3 gold badges31 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Vg0 Feb 21 at 20:44

I assume that's System.Drawing.Region? If so, that class doesn't seem to be available in .net6.0

Idle_Mind Feb 21 at 21:53

It's definitely available, but depending on the type of project you start with, you may need to add some imports. Scroll to the Bottom of this page (Applies to).

Idle_Mind Feb 24 at 20:48

Did you figure it out @Vg0?

Collectives™ on Stack Overflow

Decompose a rectangle with holes

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related