Finding all the Combinations – N Rectangles inside the Square

I am a beginner in Computational Geometry (Combinatorics) using Wolfram Mathematica and I need help from experts in the field.

How can I compute all the possible combinations: 6 Rectangles inside the Square (10×10) using Wolfram Mathematica?

Considering that the RESTRICTIONS of the problem are:

1) No Rectangle Can Overlap  2) The 6 rectangles may be vertical or horizontal 

See the image examples of possible and accepted solutions: Image-Accepted-Solutions-Examples

OUTPUT – Vector 100 elements by line (TEXT FILE):

0,1,1,0,0, . . . , 0,0,6,6,6 (Note: Image Example 01)
1,1,1,0,0, . . . , 0,0,0,4,4 (Note: Image Example 02)
0,0,5,5,0, . . . , 0,0,1,1,1 (Note: Image Example 03)
0,0,0,2,2, . . . , 0,0,0,0,0 (Note: Image Example 04)
0,0,0,0,2, . . . , 0,0,0,0,0 (Note: Image Example 05)
6,6,6,0,0, . . . , 0,4,4,4,0 (Note: Image Example 06)
Continue Combination…

Note: Please, do not put mathematical formulas. I would like the source code in Wolfram Mathematica that processes the input data (execute combinatorics task respecting the restrictions) and writes the direct output for text file to each iteration due to combinatorial explosion problems (Memory Overflow). Being that the detailed text output it is the example above: "OUTPUT – Vector 100 elements by line"

Complete proof of PAC learning of axis-aligned rectangles

I have already read PAC learning of axis-aligned rectangles and understand every other part of the example.

From Foundations of Machine Learning by Mohri, 2nd ed., p. 13 (book) or p. 30 (PDF), I am struggling to understand the following sentence of Example 2.4, which is apparently the result of a contrapositive argument:

… if $ R(\text{R}_S) > \epsilon$ , then $ \text{R}_S$ must miss at least one of the regions $ r_i$ , $ i \in [4]$ .

i.e., $ i = 1, 2, 3, 4$ . Could someone please explain why this is the case?

The way I see it is this: given $ \epsilon > 0$ , if $ R(\text{R}_S) > \epsilon$ , then $ \mathbb{P}_{x \sim D}(\text{R}\setminus \text{R}_S) > \epsilon$ . We also know from this stage of the proof that $ \mathbb{P}_{x \sim D}(\text{R}) > \epsilon$ as well. Beyond this, I’m not sure how the sentence above is reached.

Visualizing a directory structure as a tree map of rectangles

There’s this nice tool called WinDirStat which lets you scan a directory and view files in a rectangular tree map. It looks like this:


The size of each block is related to the file size, and blocks are grouped by directory and coloured distinctly according to the top level directory. I’d like to create a map like this in Mathematica. First I get some file names in the tree of my Mathematica installation and calculate their sizes:

fassoc = FileSystemMap[FileSize, File[$  InstallationDirectory], Infinity, IncludeDirectories -> False]; 

Level Infinity ensures it traverses the whole tree. I could also add 1 to ensure the association is flattened, but I want the nesting so I can assign total sizes per directory.

I can find the total size which I’ll need to use to scale the rectangles:

QuantityMagnitude[Total[Cases[fassoc, Quantity[_, _], Infinity]], "Bytes"] 

My idea is to recursively apply this total. In theory I could use this to do something like this with a tree graph and weight the vertices by size, but I want to convert this into a map of rectangles like in WinDirStat. While the colour is obvious – each level 1 association and all its descendants gets a RandomColor[] – I’m not sure how I should go about positioning the rectangles in a Graphics. Any ideas?

Find the key points of the outer layer of n overlapping rectangles – Divide and Conquer

Given a set of $ n$ rectangles depicted as: $ [Li, Ri, Hi]$ whereby the corners of the $ i-th$ rectangle are – $ (Li, 0), (Ri,0), (Li, Hi)$ and $ (Ri, Hi)$ .

The goal is to print all of the key points of the outer layer of the $ n$ overlapping rectangles (given in a list).

Key points $ (Xj, Yj)$ are the points that collectively portray the outer layer of the rectangles – look at the example below:

Given the two blocks [4, 13, 4] and [2, 7, 10] the output should be: [2,0], [2,10], [7,10], [7,4], [13,4] and [13,0] (The points that are marked red).

This should be done in $ O(nlogn)$ time where $ n$ is the number of buildings (rectangles).

enter image description here

I have tried to solve this problem by –

(1) Sorting the blocks by priority: $ Li$ then $ Ri$ then $ Hi$ .

(2) Compare any two blocks: $ [Li, Ri, Hi]$ and $ [Li+1, Ri+1, Hi+1]$ (15 different cases like Li==Li+1 and Hi< Hi+1 and stuff like this).

(3) Remove/add points according to condition (using AVL)

This works in some cases, but in others it fails miserably. I think this can be solved by Convex Hull algorithms, we have only learned the divide and conquer method so far – but I cannot link between this question and this method. I hope you can help me with this one!

Thank you

Data structure for finding nearest rectangles from current rectangle

For my project I can have 0-500 squares. The difference in diameter of the squares is 3 times at most. The squares can move at max 3 squares worth a second. About 1 square is added and about 1 square is deleted every second.

Each square gets the positions of the 5 closest squares around it. What data structure is should I be using for this? I’m also going to be doing collision detecting between squares as well.

Finding if the x and y coordinate is within a view is enclosed by two intersecting rectangles, in java [closed]

Say I have this view with two subviews A and B, A and B has a color property mColor,

enter image description here

I want a function in the parent view that has this signature: int getColor(int x, int y), which for any given x and y coordinate, return the color at that position, if the x and y coordinates land and the two shapes are overlapped, return the average color of A and B

The problem I am running into is i see myself doing a lot of conditional checks, checking if A is left of B or if A is right of B etc. I feel like I am missing some key intuition

I have a Point class that handles the coordinates”

public class Point {     private final int mX;     private final int mY;      public Point(int mX, int mY) {         this.mX = mX;         this.mY = mY;     }      public int getX() {         return mX;     }      public int getY() {         return mY;     } } 

Here is my subview class:

public class Chart  {      private int mColor;     private Point mTopLeft;     private Point mBottomRight;      public Point getTopLeft() {         return mTopLeft;     }      public Point getBottomRight() {         return mBottomRight;     }      public Chart(int mColor, Point topLeft, Point bottomRight) {         this.mColor = mColor;         this.mTopLeft = topLeft;         this.mBottomRight = bottomRight;     }      public int getColor() {         return mColor;     }      public Point getTopRightCorner() {         return new Point(getBottomRight().getX(), getTopLeft().getY());     }      public Point getBottomLeftCorner() {         return new Point(getTopLeft().getX(), getBottomRight().getY());     } } 

My parent view class:

public class View {      private Chart mChartA;     private Chart mChartB;      public View(Chart chartA,                 Chart chartB) {         mChartA = chartA;         mChartB = chartB;     }      public boolean doChartsOverlap() {         boolean isOverlapped = true;          if(isChartALeftOfChartBInX() || isChartARightOfChartBInX()) {             isOverlapped = false;         }          if(isChartABottomOfChartBInY() || isChartATopOfChartBInY()) {             isOverlapped = false;         }         return isOverlapped;     }      public final boolean isChartALeftOfChartBInX() {         return mChartA.getBottomRight().getX() <= mChartB.getTopLeft().getX();     }      public final boolean isChartARightOfChartBInX() {         return mChartA.getTopLeft().getX() >= mChartB.getBottomRight().getX();     }      public final boolean isChartATopOfChartBInY() {         return mChartA.getBottomRight().getY() <= mChartB.getTopLeft().getY();     }      public final boolean isChartABottomOfChartBInY() {         return mChartA.getTopLeft().getY() >= mChartB.getBottomRight().getY();     }      public void setChartA(Chart mChartA) {         this.mChartA = mChartA;     }      public void setChartB(Chart mChartB) {         this.mChartB = mChartB;     } } 

Cover marked squares with rectangles with optimal tradeoff

I’m trying to solve this problem where I have to cover all the squares in a N x N grid with rectangles with a tradeoff between cost and computation. These are the constraints:

  • Fields are rectangular, but may be of any width or height
  • Rectangles may cover any cell whether marked or not
  • Must be rectangular
  • Must be axis-aligned with the grid (i.e., not diagonal)
  • Rectangles cannot overlap
  • Each rectangle costs 10 + 5 per unit of area covered

Some possible solutions are given below:

enter image description here

I would ideally want to create a random array and test out the code for this. Grid can be any size with any number of marked squares, and the tradeoff is cost vs computation

Finidng edges of convexhull from rectangles

Interesection of rectangles

  1. Green Boxes = rectangles
  2. red dots = edge points
  3. red lines = to be generated from convex hull algorithm

I have a problem with creating the convex hull algorithm. I want to select or collect all the edges from these rectangles and draw convex hull around through these edges (See red dots from the Image). To make my algorithm more efficient, I don’t know how to deselect or eliminate the points (X black points) inside all rectangles.

Could someone give me a solution for this?

Thanks in advance

Designing an algorithm: arrange rectangles of varying sizes, in a pre-defined order, into an approximate box

– List of rectangles (height x width).
– Maximum width and height of result.

Arrange the rectangles, without changing the order of the list, to be as close to a square as possible. The items should go top down, left to right. If all items can’t fit within the width and height result, then ignore the max width.

Example 1: A list of squares: 1, 2, 3, 4, would be arranged as:

1 3 2 4 

Example 2: A list of squares, except #2 is a rectangle with twice the height:

1 3 2 4 2 5 

Example 3: A list of squares, except #2 is a rectangle with twice the width:

1   4 2 2 5 3   6 

Obviously the real applications are not that neat, and shouldn’t be expected to form perfect final results, just get as close as reasonably possible. Performance is not critical, but it can’t be terrible as this will be run every frame (so brute forcing is too much). “Reasonably close” results that capture the spirit are fine – if a human couldn’t immediately spot an improvement to be made it’s adequate.

Any thoughts are appreciated.

How to identify a continuous shape and break it into minimum number of rectangles?

The input in this case is going to be coordinates in 2D of the vertices of the shape. There will be no curves, but the shape can have holes. The algorithm or program needs to identify the continuous shape and break it into rectangles. The number of rectangles so created has to be optimized too.

I did read about spatial segmentation, but I am confused how to implement it. Any suggestions or help will be greatly appreciated.