4 ms·
Original rectangles are not required. What's important is only that the new rectangles cover the exact same portions of the plane as the original rectangles. Th
by gruseom 17y ago
Original rectangles are not required. What's important is only that the new rectangles cover the exact same portions of the plane as the original rectangles. This rules out computing the convex hull and then decomposing, because that would fill in any holes, i.e. the new rectangles would be covering space that the old rectangles didn't cover, which won't work.
Maybe I can explain this more fully. We are doing computationally-intensive processing of different regions of the plane. The order in which the regions get processed is unpredictable. We need to quickly, precisely and compactly answer the question: "which regions have been processed so far"?
Suppose you hire a guy to paint your wall. He's very anal (or, let's be modern about it, has Asperger's) and only ever paints in axis-parallel rectangles. He's easily distracted and liable to paint rectangles in arbitary locations, so the process doesn't proceed in any linear way, but he does cover the wall eventually. Paint is expensive, so you instruct him never to paint over the same area twice. Our problem is to efficiently answer the question, "What portions of the wall have been painted so far?"
Obviously we could just keep a list and add each new rectangle as it gets painted. But as the wall gets filled in, many painted areas will blend together. We'd like to keep the list as small as possible, i.e. we want the painted-so-far rectangles to be as large as possible. If we didn't care about that, we could just divide the wall into pixels and track the state of each.
It's not a disaster if we paint a few spots twice, but it's really bad to mark an area as painted if it hasn't been. That's why we can't ignore holes in the bounding polygon, i.e. space between painted rectangles. (Edit: actually no, it is bad if we paint the same spot twice. Imagine that the paint explodes if you do that. :))
The painting analogy can be extended to include color. In the original problem, we're painting the wall with a single color and all we care about is painted vs. not-painted. But if we introduce multiple colors, then we want to track not just "which areas are painted" but "which areas are painted blue and which areas are painted yellow". We still want to answer that question with as few rectangles as possible, but now we're not allowed to merge blue areas with yellow areas. That being said, a non-color solution would get us a long way.
NP complete problems are found everywhere in this space, no question about it. But there are also often useful results around approximations and heuristics. We don't need the optimal set, just small enough to make what we're doing fast.
Edit: the above also sheds light on why spatial indexing structures like R-trees don't work for this out of the box (though maybe they can be adapted to do so). These structures let you add rectangles and find them again. But they don't merge rectangles. If our painter takes a fancy to one-centimeter squares and decides to paint a thousand of them all in a row, an R-tree would end up with a thousand rectangles, even though the total painted area is a single n-by-1 rectangle at every step. Something like an R-tree with a "compaction" phase would be close to what we need, but maybe not close enough, because insertion into an R-tree is expensive.
- keefe 17y agoI'm writing this between moments @ my job so it is a bit rambling... I end up talking about similar problems I've worked on, suggest an interface and then in the end address the particular problem and what modifications of convex hull I think could be used to solve the original problem we were discussing including holes. Before I get into all that I want to point at this article on StackOverflow dealing with triangularization of a polygon with holes http://stackoverflow.com/questions/406301/polygon-triangulation-with-holes http://stackoverflow.com/questions/406301/polygon-triangulat... and point out the typical algorithm used in triangularization, http://en.wikipedia.org/wiki/Delaunay_triangulation http://en.wikipedia.org/wiki/Delaunay_triangulation This paper also looks promising but I haven't read it : http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WG3-4BVPRY5-1&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=8cf8e1775c4672a08acda0eaab0ab695 http://www.sciencedirect.com/science?_ob=ArticleURL&_udi... This is relatively similar to the problem I worked on where a dose curve had to be decomposed into rectangles to minimize dose delivery time. A paper on shape rectangularization from my advisor that addresses this is here http://www.springerlink.com/content/t2555274j2k16641/ http://www.springerlink.com/content/t2555274j2k16641/ but I suspect other resources will be more immediately useful. The constraints were more interesting in terms of here is a patient represented as a set of voxels and here is the prescription and tolerance of each so improper decomposition could lead to exceeding tolerance of a critical structure, but I digress... My understanding of this is that what you would like to have in your system is a data structure representing an arbitrary, complex polygon derived from the intersection of a set of rectangles such that the data structure can be queried with some rectangle and answer with another set of rectangles that indicates that the unpainted portion of the original rectangle. So something like : PaintHistory{ //returns a polygon or set of rectangles indicating //regions to be painted Rectangle[] findUnpaintedSubregion(Rectangle); //adds the given rectangle to the internal representation //of the painted area void paintRectangle(Rectangle); } So, you would want to query findUnpaintedRectangle as fast as possible and receive your set of rectangles to pain which could then be added I assume you already have such an interface that you are currently backing with some naive scheme. I think building such a structure could involve all kinds of clever data structures depending on your exact constraints. If the paint really "blows up" then it doesn't seem approximations are appropriate, but I am reminded of the barnes-hut algorithm (for computing the N-body problem, http://www.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html http://www.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26... ) and its use of the quadtree data structure to divide up the plane http://en.wikipedia.org/wiki/Quadtree http://en.wikipedia.org/wiki/Quadtree , but I am not sure if that is useful in this particular case. Originally, we were talking about the related problem of decomposing the intersection of a set of rectangles into a set of non-overlapping rectangles that completely cover the area covered by the original set of rectangles and no more. I think solving this problem efficiently (n log n) would suggest a data structure that could give more efficient real time querying. "...This rules out computing the convex hull and then decomposing, because that would fill in any holes..." I think all this means is that the convex hull is not sufficient in itself. If you have the points in the convex hull and a set of points representing each hole, then rectangularization should be easy because the convex hull should be rectilinear. What about this algorithm : 1) Compute the set of points which are intersections of rectangles or their corner points. Here is a fast algorithm for this : http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorit... 2) Compute the convex hull of these points to give a containing polygon. 3) Compute the set of all polygons that represent holes in the convex hull polygon. I think this is a well studied problem, but you can imagine a number of naive solutions and then optimize them. For example, any polygon representing such a hole must be composed of corner points or intersection points, which are in the set we already identified. Do a plane sweep in increasing x direction and parse through the source rectangles, discarding points covered by other rectangles and points on the convex hull. This could probably be done as a slight modification of step 1. Definitely a tricky part, but I think a solvable problem... 4) At this point you have a set of points representing the rectilinear polygon that is a convex hull and you have a set of points representing each rectilinear polygonal hole in the convex hull. So, now you just have to decompose this complex polygon into rectangles - I think if you just draw vertical and horizontal lines at each point and compute intersections, that should lead to a rectangularization with minimal cleanup and you are done. I hope some of that is helpful, certainly not a link to a complete solution but all that comes to the top of my head now....