Smallest Quadrilateral around polygon — OZONE Asylum, home of the Mad Scientists

OZONE

Smallest Quadrilateral around polygon

This page's ID: 28569

Edit Post

Who can edit a post?	The poster and administrators may edit a post. The poster can only edit it for a short while after the initial post.

Your User Name:
Your Password:
Login Options:	Remember Me On This Computer

Your Text: Insert Slimies » Insert UBB Code » Close Last Tag \| All Tags UBB Help	[quote]I'm segmenting regions that once where rectangular ( square actually), but might have been shot at any angle.[/quote] I just want to make sure that you know the "Z-near" plane of projection doesn't pass through the square? If so, the projected shape could be an open polygon extending to infinity. Here's an idea I'll throw out there - there's probably something wrong with it, and it's probably not optimal. What if you start with the convex hull of the polygon, and then: While the number of sides of the polygon is greater than 4, find the side which, when "removed", causes the smallest increase in area of the polygon and "remove" it. "Removing" a side of the polygon means taking the two sides adjacent to it and extending them towards each other until they intersect, eliminating the side in question. (This can't be done when the two adjacent sides point away from each other.) ----- If the original polygon is a triangle, the smallest quadrilateral that encloses it is undefined (as it approaches a triangle shape enclosing the triangle, it gets smaller but if you actually make it into the triangle it's not a quadrilateral anymore). Hope that helps... [edit: no, this has flaws, because it can only generate a quadrilateral where each side shares a side with the original convex hull; there are cases where this doesn't represent the best case.] [url=http://www.slimeland.com/] [img]http://www.slimeland.com/misc/ozonemetalslimesig.gif[/img] [/url] [small](Edited by [url=http://www.ozoneasylum.com/user/5]Slime[/url] on 10-25-2006 10:22)[/small] Loading...
Options:	Enable Slimies Enable Linkwords

« Backwards — Onwards »

Show Forum Drop Down Menu