6

I'm trying to render polygons, but they can only be rendered using axis-aligned rectangles. So, I' looking for an algorithm that can basically fill in a polygon using the least possible amount of rectangles. If it helps reduce the amount, the rectangles are allowed to overlap each other.

I've already implemented this fill algorithm, which mostly suffices. The downfall is that it restricts rectangles to each pixel row. I ultimately want to reduce the amount of rectangles as much as possible.

  • I assume from the question that that the polygon is pixelated? a vector based polygon won't be able to be filled with any finite number of axis aligned rectangles except in special cases... – Chris Oct 11 '11 at 10:33

2 Answers2

1

Pixel representation of polygon is same as rectilinear polygon and you can partition it quite fast. See answer to this question.

Community
  • 1
  • 1
Ante
  • 5,350
  • 6
  • 23
  • 46
0

Removing that restriction (that each rectangle have a height of one pixel) helps in some special cases when the polygon is made of big rectangles, but not at all in the general case.

How about this: use that algorithm, but extend each rectangle upward and downward as much as you can, and when all of the rectangles are in place, eliminate redundant ones.

There is still a little bit of room for improvement, in that the order in which you eliminate redundant rectangles might matter in some very rare cases, but honestly I don't think it's worth worrying about for a practical solution.

Beta
  • 96,650
  • 16
  • 149
  • 150
  • When I think about it, I could just treat the rows as a bunch of rectangles, and then apply methods suggested in [this question](http://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles). –  Oct 11 '11 at 10:36