approximating arbitary shapes with segments
i'm looking for a method to approximate arbitrary vector graphic shapes (circles, rects, bezier curves, etc.) with line segments. does anybody know the proper search terms for an algorithm doing that? greets, amir
On Mon 03.11.14 17:33, Amir Hassan wrote:
i'm looking for a method to approximate arbitrary vector graphic shapes (circles, rects, bezier curves, etc.) with line segments.
does anybody know the proper search terms for an algorithm doing that?
Depending on how you exactly phrase the problem, this is a tough problem in computational geometry. But in practice you could probably sample your curve densely and then apply a simplification algorithm a la Ramer-Douglas-Peuker algorithm, see also wikipedia. Cheers, Stefan
On Mon, Nov 03, 2014 at 05:33:39PM +0100, Amir Hassan wrote:
i'm looking for a method to approximate arbitrary vector graphic shapes (circles, rects, bezier curves, etc.) with line segments.
does anybody know the proper search terms for an algorithm doing that?
piece-wise linear approximation. For most geometrical Objects this is rather simple to do: Circle (or segment): just subdivide the Angle (n*2pi/N) Bezier curves: there is a subdivision algorithm Rectangles, Polygones: nothing to do. If those objects exist as a function, you can simply evaluate those functions for n/N, i.e. f(n/N) and connect the resulting N+1 points with lines. Best, Herbert
greets, amir
_______________________________________________ Metalab mailing list Metalab@lists.metalab.at https://lists.metalab.at/mailman/listinfo/metalab
On Mon 03.11.14 18:23, Herbert Poetzl wrote:
On Mon, Nov 03, 2014 at 05:33:39PM +0100, Amir Hassan wrote:
i'm looking for a method to approximate arbitrary vector graphic shapes (circles, rects, bezier curves, etc.) with line segments.
does anybody know the proper search terms for an algorithm doing that?
piece-wise linear approximation.
For most geometrical Objects this is rather simple to do:
That depends on how you precisely formulate the problem. What about this: Given a polygonal line with n segments and an eps > 0. Find another polygonal line with a minimal number of segments such that the (symmetric) Hausdorff distance between both is at most eps. See for instance: http://www.worldscientific.com/doi/abs/10.1142/S0218195996000058 Best Stefan
This sounds a bit like the "genetic algorithm approximating the mona lisa with rectangles" a few years back. Depending on what you're using it for, there may be some original research involved :) can't wait to see the result tbh 2014-11-03 17:33 GMT+01:00 Amir Hassan <amir@viel-zu.org>:
i'm looking for a method to approximate arbitrary vector graphic shapes (circles, rects, bezier curves, etc.) with line segments.
does anybody know the proper search terms for an algorithm doing that?
greets, amir
_______________________________________________ Metalab mailing list Metalab@lists.metalab.at https://lists.metalab.at/mailman/listinfo/metalab
On Nov 3, 2014, at 20:33 PM, Amir Hassan <amir@viel-zu.org> wrote:
i'm looking for a method to approximate arbitrary vector graphic shapes (circles, rects, bezier curves, etc.) with line segments.
See ClipperLib (http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Fun...) for a Ramer-Douglas-Peuker-esque algorithm implementation. -Marius
Teilnehmer (5)
-
Amir Hassan -
Herbert Poetzl -
Marius Kintel -
Philip Poten -
Stefan Huber