7
$\begingroup$

Let's assume we have a planar domain whose boundary can be described with a polynomial curve (like Bezier curves). Now assume that you want to produce a discretization of the boundary, i.e. you want to produce a polygon by sampling the polynomial defining the boundary of the domain. How can I produce a boundary that incurs in a error lower than some user provided tolerance? A measure of the error could be something like.

$$ \sum_{\text{sides}}\int_0^1 ||\operatorname{line}(x_j,x_{j+1},t) - \partial\Omega_j(t)||^2 dt $$

That is, the square error of the polygon (whose sides are straight lines from vertex $x_i$ to $x_{i+1}$) with respect to the polynomial domain whose sides are represented by the parametrization $\partial\Omega_j(t)$. Each side is parametrized in the interval $t \in [0,1)$.

I am trying to improve the shape2polygon function of the GNU/Octave package geometry.

EDIT: The idea is to produce a polygonal representation of the original domain with the given error, with as few vertices as possible.

Thanks

EDIT:

  • I have implemented an GNU/Octave non-recursive version of the Ramer-Douglas-Peucker algorithm to simplify polylines and polygons. simplifypolyline.m and simplifypolygon.m.
  • I have implemented an GNU/Octave non-recursive version of the algorithm in L. H. de Figueiredo (1993). "Adaptive Sampling of Parametric Curves". Graphic Gems III. This function performs adaptive sampling of a parametrized planar curve. curve2polyline.m. The extension to polynomial domains will be in shape2polygon.m.
$\endgroup$
  • $\begingroup$ Hi JuanPi. Let me see if I understand your question correctly. Are you asking how to sample the points on the boundary of the domain to produce a minimal eror in your defined norm? If so, have you tried sampling a large number of equispaced points along $\partial\Omega_j(t)$? $\endgroup$ – Paul Apr 11 '12 at 15:35
  • $\begingroup$ Expanding on Paul's question, it does seem like you can simply keep sampling your curve until you reach your tolerance. Are you looking to minimize the number of sides used to obtain the tolerance? $\endgroup$ – James Custer Apr 11 '12 at 15:42
  • $\begingroup$ Thank you for your interest! I am changing the question cause indeed is it confusing. The question is how to convert from the polynomial representation to a polygonal representation (i.e. polynomials of order 1) and doing it preserving the shape, or as I wrote with given error. The question is really how to sample the sides intelligently (maybe based on curvature?). Of course uniform sampling could be done, but produces a polygon with too many edges and vertices; and to reproduce a curve with high curvature one needs many points increasing the sampling all over the boudary. $\endgroup$ – JuanPi Apr 12 '12 at 11:05
3
$\begingroup$

You want to perform an adaptive sampling of the boundary curve.

For Bézier curves, use the de Casteljau algorithm recursively until the control points are approximately collinear. See for instance Adaptive Subdivision of Bezier Curves from the Anti-Grain Geometry project.

For general curves, see for instance Adaptive sampling of parametric curves, in Graphics Gems V, 1995.

$\endgroup$
  • $\begingroup$ Thank you very much! I checked the ps you provide and there is no 1995 paper there. The closest is Curve tesselation criteria through sampling. Graphic Gems III 1992. Is that the one you meant? I am reading the website you provide. Very interesting. Thanks. $\endgroup$ – JuanPi Apr 12 '12 at 15:10
  • $\begingroup$ @JuanPi, also here: ariel.chronotext.org/dd/defigueiredo93adaptive.pdf $\endgroup$ – lhf Apr 12 '12 at 18:11
  • $\begingroup$ Thank you, I found it. Very useful. I implemented something similar, since recursions are painfully slow in Octave. $\endgroup$ – JuanPi Apr 13 '12 at 7:30
3
$\begingroup$

The problem of simplifying a polygon is well-studied. The Douglas-Peucker algorithm is among the most popular methods. It can be implemented to run in time O(n log n). See the Wikipedia article on this algorithm.

$\endgroup$
  • $\begingroup$ I don't think this is what he is looking for given the wording of the question (although the simplifypolygon function name does confuse things a bit). The Douglas-Peucker algorithm starts with a curve composed of line segments. $\endgroup$ – James Custer Apr 12 '12 at 2:19
  • $\begingroup$ Thank you for this pointer. Is not directly related to the question but is related to the simplifypoligon function. I am sorry for creating the confusion, but I am very happy you provided this pointer. Thanks $\endgroup$ – JuanPi Apr 12 '12 at 11:10
1
$\begingroup$

The question to me is simply whether you want to have the minimal number of vertices, or whether you're just interested in a small number of vertices.

I'd use the obvious, greedy adaptation algorithm: you start with a small number of vertices and get a poor boundary approximation. Let's say you have $N$ segments in this step. Then for each segment $i,i=1\ldots N$ of your polygonal approximation, you compute the error $e_i$ of this one segment, and if $e_i>\frac{tol}{N}$ then you insert a new vertex along the boundary and split the segment into two. Iterate this until all segments have an error less than $\frac{tol}{N}$ and you have a boundary approximation with an overall error equal to or less than $tol$.

$\endgroup$
  • $\begingroup$ Hi Wolfgang Bangereth, thanks. That is exactly what the algorithm from Figueiredo is doing. $\endgroup$ – JuanPi Apr 14 '12 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.