ref: 334479a45c246efcf92f6e5d0e782f11f6117cef
parent: fcfc068be973277679492de19cf0bc52eed03db0
author: Halfwit <michaelmisch1985@gmail.com>
date: Sun Sep 23 11:40:41 PDT 2018
Working on the Readme. It's meandering towards something understandable and concrete, but there's a long way to go. Signed-off-by: Halfwit <michaelmisch1985@gmail.com>
--- a/README.md
+++ b/README.md
@@ -1,6 +1,6 @@
# Bin Packing Meets Window Management
-* CURRENTLY BROKEN *
+## * CURRENTLY BROKEN *
The previous state this was left in shouldn't really be ran anywhere, as it's too intensive for sane use - so I've pushed the new design through to master. Please don't use this until 0.1 release.
This is a small project used in tandem with [hwwm](https://github.com/halfwit/hwwm) to lay out my windows in a way that I want
@@ -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.
-## Programming notes
+## Layout
-We use a list of points to define a face, the face and bounding box that it bisects representing all available space to place subsequent windows (rectangles).
-
Examples:
```
@@ -41,17 +39,17 @@
| | |
| | |
|------------------| |
- | |
- | |
- | |
- | |
- | |
- | |
+ | . |
+ | . |
+ | . |
+ | . |
+ | . |
+ | . |
|-----------------------------------------------|
- Points are (18,0) (18,7) and (0,7)
+
```
-This essentially creates 3 new points of interest in our available space. The top right, bottom right, and bottom left points of the window we just placed - we're going to keep track of these, and these alone.
+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.
```
|------------------|----------------------------|
@@ -61,41 +59,45 @@
| | |
| | |
|----------------|-| |
- | | |
- | | |
- | Win #2 | |
- | | |
- |----------------| |
- | |
+ | | . |
+ | | . |
+ | Win #2 | . |
+ | | . |
+ |----------------| . |
+ | . |
|-----------------------------------------------|
- Points are (18,0) (18,7) (16,7) (16,12) (0,12)
+ We can see the bounding box doesn't need to expand to
+ accomidate the second window here
```
-Notice we removed the point (0,7) - this requires explanation.
+As we'll fill up the vertical space fairly fast, we inevitably will require moving the bounding box to accomidate new windows.
+When we stack the windows, we arrive at some ambiguity about how far to expand the bounding box, to accomidate the next window. We can do it one of two ways:
```
- |------------------|-----------|----------------|
- | | | |
- | | Win #3 | |
- | Win #1 | | |
- | |-----------| |
- | | |
- |----------------|-| |
- | | |
- | | |
- | Win #2 | |
- | | |
- |----------------| |
- | |
- |-----------------------------------------------|
+ |------------------|-----------|----------------| |------------------|----------------------------|
+ | | | | | | . |
+ | | Win #3 | | | Win #1 | . |
+ | Win #1 | | | | | . |
+ | |-----------| | | | . |
+ | | . | | | . |
+ |----------------|-| . | |----------------|-|---------| |
+ | | . | | | | |
+ | | . | | | Win #3 | |
+ | Win #2 | . | | Win #2 | | |
+ | | . | | |-----------| |
+ |----------------| . | |----------------| . |
+ | . | | . |
+ |-----------------------------------------------| |-----------------------------------------------|
```
-Placing window #3 would see that there is a point, (0,7) with enough space both horizontally and vertically to fit and overlap window #2. Previous versions of binpack checked for windows occupying the same space explicitely, but this is an expensive operation. using and updating an accurate list of applicable points is a means to an end to have a highly efficient packing algorithm.
+The first option just takes the right-most point, and adds the width of window #3. This assures it'll fit. (there's also a test done to ensure that the bounding box we define isn't wider than the actual screen we're using; so for example in a 1920x1080 window, we'll never try to draw windows that go beyond 1920)
+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.
-## Two special cases here require further consideration
+Two special cases here require further consideration:
-```
+```
|----------------|------| |-------------|x|--|
| | | | |x| |
| #1 | | | |x| |
@@ -108,11 +110,9 @@
```
-### First window
-
+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.
-### Second window
-
+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.