# fit a small number of lines to an shape outline

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

## 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 border finding 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 on other sites
It seems that you try to find a convex hull of a point set. There're several algorithm to solve this problem: clicky

##### Share on other sites
Quote:
 Original post by Ashaman73It 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.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633298
• Total Posts
3011249
• ### Who's Online (See full list)

There are no registered users currently online

×