CODEWITHSUNDEEP
algorithmgeometrypolygon
jpreed00
jpreed00

Reputation: 893

What is an algorithm for estimating a given shape using a polygon with N vertices?

I have a random shape. I want to turn it into a polygon with N vertices. Is there an algorithm that chooses the best N vertices to estimate a given shape?

For example, I have this shape:

shape

Given an N, say 20, what is the algorithm to choose 20 points along the perimeter of this shape to generate a best-fit polygon?

Something like this:

shape2 shape3

Upvotes: 2

Views: 496

Answers (3)

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

There is a considerable literature on the topic, which goes under the key phrase polygonal chain approximation. Here is an early work, whose subsequent 111 citations may be of more use than the original:

Melkman, A. and O'Rourke, J., "On polygonal chain approximation," in Computational Morphology, Ed. G.T. Toussaint, Elsevier, North-Holland, 1988: 87-95.

Upvotes: 4

user1196549
user1196549

Reputation:

Use the Douglas-Peucker algorithm for polyline simplification.

It has best case O(N Log N) behavior, and (unfortunately) O(N²) in the worst case. There is a more complex variant called DPHull, with a guaranteed O(N Log N) worst case. See "Speeding Up the Douglas-Peucker Line-Simplication Algorithm" by Hershberger & Snoeyink.

Upvotes: 1

Gene
Gene

Reputation: 47020

The thinning algorithm we discussed in comments works on a curved polyline, which is usually a chain of pixel coordinates, but doesn't have to be. It eliminates points that are "unnecessary" to render the curve within some given tolerance. Let P_0 and P_n-1 be the polyline end points and Eps be the tolerance. We will produce a subsequence of these points as follows:

function thin(P, I, J)
  return [] if J <= I + 1
  let P_k, I < k < J be a point at farthest 
      distance D from line through P_I and P_J
  return [] if D <= Eps
  return thin(P, I, k) | [P_k] | thin(P, k, J)

The result is then [P_0] | thin(P, 0, n-1) | [P_n-1].

The distance calculation is standard stuff. dist(P, A, B) of P from line through A and B is abs(unitperp(B - A) dot (P - A)). In turn, perp(v) = [-v_y, v_x], unit(v) = v / sqrt(v dot v), finally unitperp(v) = unit(perp(v)). Of course in the real calculation you want to compare distance squared rather than actual distance to avoid square root calculations for a bit of speed advantage.

You have a closed polygon, so you'll have pick any point Q as both P_0 and P_N with the rest between. The result will be either [Q] | thin(P, 0, n-1) or just thin(P, 0, n-1) depending on whether Q is farther than Eps from the line between the end points of thin(P, 0, n-1) or not.

Upvotes: 1

Related Questions