Archived

This topic is now archived and is closed to further replies.

Reverse tessellating

This topic is 5239 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Reverse tessellation is the best way I can describe what I want to do. I have a set of convex polygons that are all adjoined, and together they form an arbitrary (i.e convex or concave) polygon. Naturally, the shape of this polygon is easily to determine with the human eye, however the computer has no idea. What I''m looking for is a way to combine as many of these smaller convex polygons into larger convex polygons, while still maintaining the full outer shape. When I first made the assumption that the outer shape was convex, the QuickHull algorithm worked perfectly, however after extensive testing with possible input data I realized that many times the outer shape was concave, in which case QuickHull resulted in overlapping polygons (not good). Now I need an algorithm for the general case. Someone I talked to suggested that I use the MiniMax algorithm with Alpha-Beta cutoffs, because it fit the description of my problem perfectly (says he at least). For starters, I''m trying to maximize the size of each output convex polygon (measured in the number of input polygons reverse tessellated for that output polygon) while minimizing the actual number of output polygons. At the same time, I want to prune the search with the cutoffs so that I don''t explore areas of the tree that can never produce results better than ones I''ve already found. The problem is that the MiniMax algorithm is commonly used for two-player games where a heuristic can be used to calculate the value of future "game states." I simply can''t see how I can apply the algorithm to my situation. The guy I talked said that instead of literal "moves," I remove common edges and test the resultant polygon. I suppose the depth-first searches are harder to visualize, but at any rate I can''t see how it would work. If this sounds a good solution to you, an exploration of how it would work in this context would make my day! Or if anyone has any other suggestions, algorithms, comments, concerns, etc., I''m all ears. Otherwise I''m stuck with my hack & slash method, which is only a few notches above brute force (and I predict will be very slow). On the issue of speed, it basically isn''t an issue at all The nature of the application is that of a tool or utility, and it''s better that I get the most accurate results rather than the quickest. But at the same time the user won''t want to sit around for hours while I perform a bubble sort on a 65536-element array (figuratively speaking, or course ). I''ve tried looking around at LOD articles and algorithms, however they focus primarily on splitting low-resolution polygons into smaller high-resolution polygons, and not the other way around. P.S. After I get this working, I''ll want to move on to three dimensions, but that''s a story for another post

Share this post


Link to post
Share on other sites
If you have a list of polygons instead of just a list of points, it should be easy.

Make a list of all edges from the list of polygons. Remove all instances of edges that appear more than once. The remaining edges form the convex polygon you want.

j

Share this post


Link to post
Share on other sites
I didn''t read the post thoroughly enough, so I missed what you actually wanted.

The answer I gave gives you the entire polygon, which isn''t necessarily convex. You could take that and then apply already known simplification techniques to get your answer.

That might be faster than what you''re already doing.

j

Share this post


Link to post
Share on other sites