Sign in to follow this  

fit a small number of lines to an shape outline

This topic is 2846 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

I'm running a simulation that gradually deforms a rectangle comprised of of specific grid points. So initially, I have a rectangle, at some small time later I have a rectangle with a single pixel defect, and a long time later it could be any shape. I'd like to find a polygon that would describe the shape of the border of the simulated shape. I can find the pixels which make up the border, so now I have a collection x,y of pixels that make up the border. I'd like to fit a minimum number of straight lines to these borders which accurately describe the shape. The lines can start at end at any point, but must form a closed (convex or concave) polygon. The way I was originally thinking of doing this didn't work, and I'll describe it here. If my original rectangle deforms to what the human eye would see approximately as a triangle, I'd like 3 lines to describe a triangle, whereas a [url=http://users.utcluj.ro/~tmarita/IPL/L6/PI-L6e.pdf]border finding[/url] algorithm might find a very large number of lines which accurately describe the shape. Obviously, there will be some parameter to balance accuracy vs number of lines. This leads me to think of an optimization problem, minimize N + \lambda \sum\limits_1^N ( (x(i),y(i)) - (line i @ closest point to x,y)^2 constrained by line(i) must connect to line(i+1) and line(n) connects to line(0). I could program this, but I don't know the positions of the line(i) endpoints ahead of time, so I don't think this method would be possible. Do you have any ideas? Given a pixelated border of a shape, how would I fit a minimum number of lines to the border under a prescribed accuracy?

Share this post


Link to post
Share on other sites
Quote:
Original post by Ashaman73
It seems that you try to find a convex hull of a point set. There're several algorithm to solve this problem: clicky


No, this is a completely different problem.

You could start with the detailed contour described in that PDF file, and then try to remove vertices that don't change things much. You need to define some metric to decide how good a fit is, and then have some threshold to determine if removing a vertex results in an acceptable departure from the shape or not.

Share this post


Link to post
Share on other sites

This topic is 2846 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this