New feature: Arc filter

[aewallin]

An arc-filter in python, developed for slic3r:
http://wiki.linuxcnc.org/cgi-bin/wiki.pl?LinesToArcs

If this algorithm is good, it should be converted to c++, extended to handle all planes (XY, XZ, YZ), and added to opencamlib.

[Harvie]

I've recently added arc fiter to my fork of bCNC:
https://github.com/Harvie/bCNC/

https://github.com/Harvie/bCNC/blob/master/lib/bpath.py

See these two methods:

	def arcFit(self, prec=0.5, numseg=10):
	def mergeLines(self, prec=0.5):

Currently it only works only for flat 2D toolpaths (no Z coordinate support). But i think it can make you understand basic principles of arc fitting. It's quite easy:

1.) You take two lines and try to approximate where their orthogonals intersect each other and how far this intersection is. That gives you parameters of arc: center, radius and CW/CCW direction.
2.) You check that endpoints and middle points of original lines are distant within specified tolerance from that arc.
3.) You try to "eat" as many subsequent lines that fit to this arc while moving arc further and further away, while still testing if the fit is up to tolerance.
4.) Every time you eat new line, you have to recalculate the arc parameters (center and radius). I just calculate these for all pairs of lines and then calculate the mean of the results. Then i test if newly found arc does still fit within tolerance. Otherwise i continue to using old parameters which fit correctly and continue eating more lines until there's line that cannot fit into this arc.

Also i use similar algorithm to fit/merge lines with very small tolerance before i start fitting arcs, that's especially important when arcfiting STL slices and other shapes, where one line can be split to two as result of triangulation.

So basicaly you need three basic building blocks:

1.) method to merge lines that are almost parallel
2.) method to approximate arc parameters from array of two or more lines
3.) method to test if array of one or more lines fit within tolerance of arc defined by these parameters

In 3D you will also need to check if the Z ramp is constant. Eg. if first line is 10mm long in XY plane and travels -3mm in Z direction, you have to make sure that when you add another 30mm (XY) segment, it will travel another -9mm in Z. So the ramp angle remains constant.
This can be easily added to functions which approximate parameters and test the fit.