Dartmouth Professor R. L. Scot Drysdale and colleagues have created an algorithm to efficiently approximate an open polygonal curve using as few circular arcs and biarcs as possible. The method was published this month in Computational Geometry-Theory and Applications.
In computational geometry, the word “approximation” can have different possible meanings. Drysdale defines an approximation as the smoothest curve that resembles the polygonal curve as well as goes through the given sets of points defined by the polygonal curve.
Before this method was developed, there were few ways to find out how close the approximation would be when compared to the actual curve. To solve this problem, Drysdale defined valid circular arcs and biarcs that can be used for approximation.
Drysdale used a “tolerance region” to define the boundaries for arcs. Then he divided the region according to the vertices of a curve. Finally, a line is drawn through the tolerance region.
“An arc has to go through each gate only once,” Drysdale said.
In order to form valid circular arcs, finding a center of a circle containing a starting point and a point in the next gate is vital. Drysdale computed the areas, called “wedges,” using perpendicular bisectors.
“As long as the centre is within the wedges, any valid circular arcs will work,” Drysdale said.
The goal is to find the overlapping area amongst the wedges to cover as many points as possible per valid circular arc – and to find the shortest possible path.
Yet, using the circular arcs only results in arbitrary vertices. To improve the usefulness of these verticies, Drysdale also developed the biarc algorithm.
“By using two circular arcs sharing a same tangent line, a smoother curve can be formed,” Drysdale explained.
This field of study has been considered important in industries where machinery movements are involved. According to Drysdale, it is an interesting optimization problem in that you strive to find the most efficient way to have a machine go through multiple points with less programming and fewer controls. Not only will this lead to smaller programs for a machine, but also a device can be operated in an energy- and cost-effective way.