__simple__algorithm for decomposing a rectilinear polygon into a non-overlapping rectangular cover. I stress simple when I say it because I'll be implementing the solution in Second Life which has an extremely limited scripting language. (Although scripts do have access to a pretty decent geometric and math API, memory and storage flexibility is quite limited).

**Edited in thumbnail. We're getting a few graphics in here**Assume that the polygon in Figure 1 is perfectly rectilinear. Figure 2 shows a (fairly ideal) solution to the problem. Figure 3 is incorrect. While the entire polygon is indeed covered, there are overlaps, and this will not be acceptable given the type of geometry I'll be outputting. Figure 4 is also incorrect because the entire polygon isn't covered. I just cannot think of a good solution here, and I've been playing with it for some time. The problem seems pretty simple at first glance, so maybe I'm just missing something. I am

__not__looking to necessarily output the minimal or optimal set of covering rectangles. Although that would be nice, the simplicity of the algorithm is most important. That being said, converting the given polygon into more than, say, 8-10 rectangles would be a blatant misuse of resources. Anybody have any ideas? [help] -Dave [Edited by - DMatovich on August 19, 2007 2:48:12 AM]