thoughts.md

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