mirror of
https://github.com/Astatin3/meteorbot-old.git
synced 2026-06-09 00:28:06 -06:00
33 lines
1.9 KiB
Markdown
33 lines
1.9 KiB
Markdown
|
## Brute force approaches
|
||
|
|
|
||
|
|
- Rect feasibility = number of empty spaces into which the rect fits
|
||
|
|
- Rect difficulty = 1 / rect feasibility
|
||
|
|
- Space feasibility = number of remaining input rectangles that fit into the space
|
||
|
|
- How to break ties for huge, initial spaces?
|
||
|
|
- How much one can insert until current rects AABB is expanded.
|
||
|
|
- The more one can insert, the more feasible the space is.
|
||
|
|
- In practice, will there be many ties?
|
||
|
|
- There shouldn't be many not be if the max_size is carefully chosen
|
||
|
|
- Determine difficulty recursively?
|
||
|
|
- e.g. sum all successful insertions and successful insertions after each successful insertion...
|
||
|
|
- ...quickly becomes exponential
|
||
|
|
- Minimum of all free dimensions generated by all insertion trials?
|
||
|
|
- Or some coefficient like pathological mult for rectangles?
|
||
|
|
- Space difficulty = 1 / space feasibility
|
||
|
|
- Algorithm: until no more spaces or no more rectangles
|
||
|
|
- Find the most difficult space
|
||
|
|
- among rects that fit...
|
||
|
|
- insert the one that generates least spaces or the most difficult space - this means that, into the most difficult space, the most difficult rect will be inserted
|
||
|
|
- In case of a perfectly fitting rect, this will be chosen
|
||
|
|
- in case of a partly fitting or a strictly smaller rect, insert the most difficult rect, e.g. one that leaves the most difficult spaces
|
||
|
|
- however, when splitting due to the rect being strictly smaller, split in the direction that generates a maximally feasible space
|
||
|
|
- complexity: we iterate every space, number of which will grow linearly as time progresses, and then we iterate each rect
|
||
|
|
|
||
|
|
## Old thoughts
|
||
|
|
|
||
|
|
- what about just resizing when there is no more space left?
|
||
|
|
- then iterate over all empty spaces and resize those that are touching the edge
|
||
|
|
- there might be none like this, though
|
||
|
|
- then we can ditch iterating orders
|
||
|
|
- we could then easily make it an on-line algorithm
|