0

I have been working on a game engine and for it every hitbox is made from a bunch of small rectangles on the 2D quadrant plane. What I would love to have is a function takes in a hitbox and then returns a new hitbox which covers the same shape and area but with the fewest possible number of rectangles. I have found several solutions which decrease the number but nothing which guarantees the absolutely fewest number of rectangles. Here is a few examples of me solving this problem by hand.

Examples of the problem...

Edit: Thanks to Klaus Gütter for linking a solution from another thread. Sorry for the duplicate. As for an implementation in C# i recommend checking out this github repo.

RandomiaGaming
  • 1
  • 2
  • 1
    Does this answer your question? [Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping](https://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles-without). Also useful: http://library.utia.cas.cz/separaty/2012/ZOI/suk-rectangular%20decomposition%20of%20binary%20images.pdf – Klaus Gütter Mar 09 '22 at 07:13
  • If you are implementing a game engine you should probably be using some kind of hierarchical-structure to optimize the hit-testing. That way the number of boxes should be less important. There is also the concept of [concave hull](https://stackoverflow.com/questions/83593/is-there-an-efficient-algorithm-to-generate-a-2d-concave-hull) – JonasH Mar 09 '22 at 07:46

0 Answers0