Full Text:   <3195>

CLC number: TP39

On-line Access: 

Received: 2006-04-03

Revision Accepted: 2006-04-17

Crosschecked: 0000-00-00

Cited: 0

Clicked: 5537

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
Open peer comments

Journal of Zhejiang University SCIENCE A 2006 Vol.7 No.7 P.1115-1123


An efficient method for tracing planar implicit curves

Author(s):  YU Zheng-sheng, CAI Yao-zhi, OH Min-jae, KIM Tae-wan, PENG Qun-sheng

Affiliation(s):  Computer Science School, Hangzhou Dianzi University, Hangzhou 310018, China; more

Corresponding email(s):   yuzhengsheng@tom.com, taewan@snu.ac.kr

Key Words:  Planar implicit curve, Curve tracing, Continuation method, Geometric modeling

YU Zheng-sheng, CAI Yao-zhi, OH Min-jae, KIM Tae-wan, PENG Qun-sheng. An efficient method for tracing planar implicit curves[J]. Journal of Zhejiang University Science A, 2006, 7(7): 1115-1123.

@article{title="An efficient method for tracing planar implicit curves",
author="YU Zheng-sheng, CAI Yao-zhi, OH Min-jae, KIM Tae-wan, PENG Qun-sheng",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T An efficient method for tracing planar implicit curves
%A YU Zheng-sheng
%A CAI Yao-zhi
%A OH Min-jae
%A KIM Tae-wan
%A PENG Qun-sheng
%J Journal of Zhejiang University SCIENCE A
%V 7
%N 7
%P 1115-1123
%@ 1673-565X
%D 2006
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2006.A1115

T1 - An efficient method for tracing planar implicit curves
A1 - YU Zheng-sheng
A1 - CAI Yao-zhi
A1 - OH Min-jae
A1 - KIM Tae-wan
A1 - PENG Qun-sheng
J0 - Journal of Zhejiang University Science A
VL - 7
IS - 7
SP - 1115
EP - 1123
%@ 1673-565X
Y1 - 2006
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2006.A1115

This paper presents a method for tracing a planar implicit curve f(x, y)=0 on a rectangular region based on continuation scheme. First, according to the starting track-point and the starting track-direction of the curve, make a new function F(x, y)=0 where the same curve with f(x, y)=0 is defined. Then we trace the curve between the two domains where F(x, y)>0 and F(x, y)<0 alternately, according to the two rules presented in this paper. Equal step size or adaptive step size can be used, when we trace the curve. An irregular planar implicit curve (such as the curve with large curvatures at some points on the curve), can be plotted if an adaptive step size is used. Moreover, this paper presents a scheme to search for the multiple points on the curve. Our method has the following advantages: (1) it can plot C0 planar implicit curves; (2) it can plot the planar implicit curves with multiple points; (3) by the help of using the two rules, our method does not need to compute the tangent vector at the points on the curve, and directly searches for the direction of the tracing curve; (4) the tracing procedure costs only one of two evaluations of function f(x, y)=0 per moving step, while most existing similar methods cost more evaluations of the function.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Barnhill, R.E., Farin, G., Jordan, M., Piper, B.R., 1987. Surface/surface intersection. Computer Aided Geometric Design, 4(1-2):3-16.

[2] Bresenham, J.E., 1965. Algorithm for computer control of a digital plotter. IBM Systems Journal, 4(1):25-30.

[3] Bresenham, J.E., 1977. A linear algorithm for incremental digital display of circular arcs. Comm. ACM, 20(2):100-106.

[4] Cai, Y.Z., 1990. Numerical Control Rendering Using Positive-negative Method. Zhejiang University Press, Hangzhou.

[5] Chandler, R.E., 1988. A tracking algorithm for implicitly defined curves. IEEE Computer Graphics and Applications, 8(2):83-89.

[6] Cohen, E., 1976. A method for plotting curves defined by implicit equation. Computer Graphics (SIGGRAPH’76), 10(2):263-265.

[7] Lennon, W.J., Jordan, B.W., Holm, B.C., 1973. An improved algorithm for the generation of nonparametric curves. IEEE Transactions on Computers, C-22:1052-1060.

[8] Lopes, H., Oliverira, J.B., de Figueiredo, L.H., 2002. Robust adaptive polygonal approximation of implicit curves. Computer & Graphics, 26(6):841-852.

[9] Martin, R., Shou, H., Voiculescu, I., Bowyer, A., Wang, G., 2002. Comparision of interval methods for plotting algebraic curves. Computer Aided Geometric Design, 19(7):553-587.

[10] Shou, H.H., Martin, R.R., Wang, G.J., Bowyer, A., Voiculescu, I., 2005. A Recursive Taylor Method for Algebraic Curves and Surfaces. In: Dokken, T., Jüttler, B. (Eds.), Computational Methods for Algebraic Spline Surface (COMPASS). Springer, p.135-155.

[11] van Aken, J., 1984. An efficient ellipse-drawing algorithm. IEEE Computer Graphics and Applications, 3:24-35.

[12] van Aken, J., Novak, M., 1985. Curve-drawing algorithms for raster displays. ACM Transactions on Graphics, 4(2):147-169.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE