Area-Construction Algorithms Using Tangent Circles

  • Ching-Shoei Chiang Computer Science and Information Management, Soochow University, Taipei, Taiwan
  • Hung-Chieh Li Computer Science and Information Management, Soochow University, Taipei, Taiwan
Keywords: medial-axis transform, hermite curve, bezier curve, computer-aided geometric design


Computer aided geometric design employs mathematical and computational methods for describing geometric objects, such as curves, areas in two dimensions (2D) and surfaces, and solids in 3D. An area can be represented using its boundary curves, and a solid can be represented using its boundary surfaces with intersection curves among these boundary surfaces. In addition, other methods, such as the medial-axis transform, can also be used to represent an area. Although most researchers have presented algorithms that find the medial-axis transform from an area, a algorithm using the contrasting approach is proposed; i.e., it finds an area using a medial-axis transform. The medial-axis transform is constructed using discrete points on a curve and referred to as the skeleton of the area. Subsequently, using the aforementioned discrete points, medial-axis circles are generated and referred to as the muscles of the area. Finally, these medial-axis circles are blended and referred to as the blended boundary curves skin of the area; consequently, the boundary of the area generated is smooth.


C. S. Chiang, “The medial Axis transform of the region defined by circles and Hermit Curve,” International Conference on Computer Science and Engineering (ICCSE), July 22-24 2015.

L. Cinque, S. Levialdi, and A. Malizia, “Shape description using cubic polynomial Bezier curves,” Pattern Recognition Letters, vol. 19, pp. 821-828, 1998.

H. M. Yang, J. J. Lu, and H. J. Lee, “A Bezier curve-based approach to shape description for Chinese calligraphy characters,” Proceedings of the Sixth International Conference on Document Analysis and Recognition, pp. 276-280, 2001.

C. S. Chiang and L. Y. Hsu, “Describing the edge contour of Chinese calligraphy with circle and cubic Hermite Curve,” 2013 Computer Graphics Workshop, July 2013.

H. H. Chang and H. Yan, “Vectorization of hand-drawn image using piecewise cubic Bezier curves fitting,” Pattern Recognition, vol. 31, no. 11, pp. 1747-1755, 1998.

H. Cao and A. C. Kot, “Lossless data embedding in electronic inks,” IEEE Transactions on Information Forensics and Security, vol. 5, no. 2, pp. 314-323, 2010.

L. Cao, Z. Jia, and J. Liu, “Computation of medial axis and offset curves of curved boundaries in planar domains based on the Cesaro’s approach,” Computer Aided Geometric Design, vol. 26, no. 4, pp. 444-454, 2009.

P. Qin and C. Chen, “Simulation model of flower using the integration of L-systems with Bezier surfaces,” International Journal of Computer Science and Network Security, vol. 6, no. 2, pp. 65-68, 2006.

G. L. Orick, K. Stephenson, and C. Collins, “A linearized circle packing algorithm,” Computational Geometry 64, pp. 13-29, 2017.

O. Angel, T. Hutchcroft, A. Nachmias, and G. Ray, “Unimodular hyperbolic triangulations: circle packing and random walk,” Inventiones mathematicae 206.1, pp. 229-268, 2016.

K. E. Stange, “The sensual Apollonian circle packing,” Expositiones Mathematicae 34.4, pp. 364-395, 2016.

How to Cite
C.-S. Chiang and H.-C. Li, “Area-Construction Algorithms Using Tangent Circles”, Adv. technol. innov., vol. 5, no. 2, pp. 126-134, Apr. 2020.