Re: Hello World! - One more user/developer/volunteer
Posted by
dxli on
Dec 29, 2011; 8:40pm
URL: https://forum.librecad.org/Hello-World-One-more-user-developer-volunteer-tp5108505p5108589.html
Hi Martin,
The idea of Voronoi diagram:
http://en.wikipedia.org/wiki/Voronoi_diagrama Voronoi cell defines neighbourhood of each of given points. To get "Offset" for all given points, the offset of each (circles here) is drawn within the attached Voronoi cell up to cell boundaries, an O(N) process. Voronoi algorithm clearly simplifies the intersection problem of offset contours. To consider intersections between offset of each point is of O(N^2) by a naive algorithm. Of course, to generate Voronoi diagrams from N given points is an O(N log N) process, so, the overall complexity of offset by Voronoi is O(N log N), compared with O(N^2) by naive intersections.
The idea of Voronoi diagrams can be extended to include lines/arcs/circles, as well as points, and the extension is required for offset support in LibreCAD.
Anders is working on his openvoronoi as shown in his comments within:
http://blog.librecad.org/2011/11/experimental-offset-support-in-librecad/Please make your changes and send in pull requests by github. I don't have the permission to add you the LibreCAD group (rw access to LibreCAD/LibreCAD repository). Ries is in charge of that. He can give you write access to
librecad.org too.
Thanks,
On Thu, Dec 29, 2011 at 3:21 PM, tin-pot [via LibreCAD]
<[hidden email]> wrote:
Hello Dongxu,
Am 2011-12-29 21:04, schrieb dxli [via LibreCAD]:
> do you really mean Qt-3.4.1? I'm pretty sure we are actively adapting to
> newest Qt versions, for example, we assume Qt version being at least at
> Qt-4.5, and only check Qt versions when at least Qt-4.6 needed.
Ups, sorry, that was a typo: Of course it is Qt-4.3.1 :-)
Okay, I will write about this "MSVC build" there.
> Have a look at LibreCAD spline methods: rs_spline.h/cpp. We need some
> cleanup. If possible, we want NURBS (openNURBS ?) support for spline.
> For example, we need to provide spline fit. The only "draw spline"
> method in LibreCAD is drawing splines by control points. We may want to
> provide drawing spline fit of given points.
I see. I'll have a look at it.
You mean Martin Held's Vroni (I think is the name?) tool?
AFAIK this is commercialized, ie not available for a GPL'd
project. As far as offsetting an analytical contour goes
(line segments and circular arcs, maybe even conic arcs),
I think one could go along without a full Voronoi diagram.
(The crucial point in Held's algorithm is robustness.)
I'm going to check my colloction of papers on those matters ...
> Also, some easier engine work. For example, to implement ray (a line
> with a start point and infinite in one direction).
That sounds not too complicated, and a good occasion to learn
about LibreCAD internals, good idea.
I'm also thinking about some low-level improvements in the
engine, maybe post about it soon.
Greetings
Martin
--
Dongxu Li, Ph.D.