ref: 09530b328b31c8fb68eef21c542e8ab66d17bb36
parent: 334479a45c246efcf92f6e5d0e782f11f6117cef
author: Halfwit <michaelmisch1985@gmail.com>
date: Sun Sep 23 12:06:36 PDT 2018
More work on the readme Signed-off-by: Halfwit <michaelmisch1985@gmail.com>
--- a/README.md
+++ b/README.md
@@ -7,10 +7,8 @@
It uses a relaxed variant of the 2D Bin Pack, with a caveat that the rectangles have variable sizes.
The algorithm will try to lay out windows within the given space up to the max for each rectangle.
-## Layout
+## Explanation
-Examples:
-
```
Our window
|-----------------------------------------------|
@@ -27,6 +25,7 @@
| |
| |
|-----------------------------------------------|
+
```
We place the first window inside, starting at (0,0) (top left, this is graphics after all)
@@ -35,9 +34,9 @@
|------------------|----------------------------|
| | |
| | |
+ | Win #1 | |
| | |
| | |
- | | |
|------------------| |
| . |
| . |
@@ -49,8 +48,10 @@
```
-The dots here represent the total bounding-box that we'll attempt to place more windows into. This is done for one simple reason: when we attempt to stack windows vertically first, the aesthetic is far better.
+The dots here represent a bounding-box. What the bounding box does, is define a sub-section of windows that we'll attempt to place more windows into. This is done for one simple reason: when we attempt to stack windows vertically first, the aesthetic is far better. This algorithm would work with a horizontal limit, but tends to work poorly when you have no bounding boxes at all; you get a stack of windows that looks like a staircase, and very silly.
+So when we attempt to place our second window here, it won't be able to fit into the space beside win #1; it has to go below it. (Note, the algorithm will attempt to put the window beside first; this fills up odd cases where you have a narrow window, underneath a rather wide window; you'd much rather have two narrow windows stacked beside eachother, than on top of eachother)
+
```
|------------------|----------------------------|
| | |
@@ -95,24 +96,53 @@
The second option goes through our point list, and finds the point which will allow us to expand the bounding box the least, while still fitting the window for both width and height.
We choose the second option, and future versions of binpack will flag the choice to the users' preference outright.
+This will work for most all combinations of windows; but there are a few caveats which result in weird, overlapping layouts if not dealt with.
+
Two special cases here require further consideration:
```
- |----------------|------| |-------------|x|--|
- | | | | |x| |
- | #1 | | | |x| |
- | | #3 | | #1 |x|#3|
- |------------|---| | | |x| |
- | |xxx| | | |x| |
- | #2 |---|--|---| |---------------| |
- | | #4 | | #2 |--|
- |------------|------| |---------------|
+ |-------------------|-----|---------------------| |------|
+ | | | | | |
+ | | | | |Win #4|
+ | | | | | |
+ | Win #1 | Win | | |------|
+ | | #3 | |
+ | | | |
+ | | | |
+ |----------------|--| | |
+ | |xx|-----| |
+ | Win #2 | |
+ | | |
+ | | |
+ |----------------|------------------------------|
```
-First window:
-In the case of placing window #4, we test previous points for >= y && >= x than a point we're testing. An example where this would be true is the bottom lef
-t corner of window #3 - we attempt to place with our point starting on the same y access as the bottom of #3. In this case it fits. We could even test point 2, and since it's a point on the same axis, we know there's something likely obstructing.
+Here, if we wanted to place a 4th window we'll run in to a problem. Since we use an array of points to define where we have windows, the top-right of Win #2 would mistakingly report it had ample space to place the window, resulting in overlap between Win #4 and Win #3. The obvious, right way is to have it beside Win #2, and below Win #3. To do this, we need to make sure we don't consider the space demarkated by the x's.
-Second window:
-First we test #3 to fit, against the secont point (which is the bottom right of #1). It doesn't fit, as #2 is blocking. We now test future points for >= x && >= y points. The top right of #2 meet both reqs, We use that same x axis to place window 3.
+```
+ |--------------------|-------|------------------|
+ | | | |
+ | | Win #3| |
+ | | | |
+ | Win #1 | | |
+ | |--|----| |
+ | |xx| | |
+ | |xx|Win | |
+ | |xx| #4 | |
+ |--------------------|--| | |
+ | |----| |
+ | Win #2 | |
+ | | |
+ |-----------------------|-----------------------|
+
+```
+
+Similar issue is seen here. As we attempt to place the 4th window, we'll run in to a problem of overlapping. We'll test the point where bottom left of window #3, and window #1 meet, and it'll seem to have ample vertical space to place the window. We need to make sure we don't consider the space demarkated by the x's again, but only in the case where a window won't fit inside them.
+
+## Points
+
+To address the above issues, the first variant of binpack kept a running tally of all windows, and explicitely checked all windows for collisions. That was expensive, slow, and full of edge cases.
+To attempt to mitigate this, we're going to use an array of points, each point denoting the bottom right edge of a window. Using these points, we'll be able to extrapolate the entire working face of windows we've packed, inspect whether there's collisions relatively cheaply, and finally completely remove the need to hold each window in memory for subsequent comparisons.
+
+* The above section will be updated, based on the success of the algorithm changes in practice.