A Method of Determining the Direction of Two Dimensional Curves

Abstract:

Two-dimensional curves are represented by a list of vertices and other parameters that control the shape or curvature of the segments. In computer programming to deal with closed two-dimensional curves, it is often required to know the direction of the curve, which is reflected by the sequence of the vertex data. It can be anticlockwise or clockwise. This paper presents a robust, linear algorithm to determine the direction of a closed two-dimensional curve, by computing the total angular change of a tangent vector travelling along the curve for a complete cycle. A new, robust linear algorithm is proposed for the determination of the positional relationship of a point to a two-dimensional curve. For curves that consist of line and arc segments, which are most commonly used in engineering applications in computer aided design, the paper presents algorithms and procedures for solving the above problems.

• Periodical: Advanced Materials Research (Volume 980)
• Pages: 159-164
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.980.159
• Online since: June 2014
• Authors: F. Wang*, R.K.F. Abdelmaguid, H.M.A. Hussein
• Keywords: Computational Geometry, Computer Algorithms, Direction of Two-Dimensional Curves

References

[1] F. Wang, SM-Design: SMCAD User's Guide, Published by Gintic Institute of Manufacturing Technology, Singapore. (1998).

[2] F. Wang, Development of a state-of-the-art CAD for sheet metal progressive dies: SMCAD, Proceedings of CAD/CAM/CAE for Internet & Intranet, Temasek Polytechnic, Singapore. (1998) 28-29.

[3] P. Zhou, Editor, Algorithm Design and Analysis, Text book for higher education, Mechanical Engineering Publisher, Beijing, (1998).

[4] R. Sedgewicw, Algorithms in C++, Addison-Wesley Pub. Company, Geometric Algorithms, pp.347-401.

[5] M.I. Shamos, D. Hoey, Closest-point problems, presented in 16th, Annual Symposium on Foundations of Computer Sciences, IEEE. (1975).

DOI: 10.1109/sfcs.1975.8

[6] M.I. Shamos, D. Hoey, Geometric intersection problems, presented in 17th Ann. Symposium on Foundations of Computer Sciences, IEEE. (1976).

DOI: 10.1109/sfcs.1976.16

[7] F.P. Preparata, M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag. (1985).

[8] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verger. (1987).

[9] J.D. Boissonnat, M. Teillaud, Effective computational geometry for curves and surfaces, Springer-Verlag, Berlin, Heidelberg. (2006).

DOI: 10.1007/978-3-540-33259-6

[10] J.A. Baerentzen, J. Gravesen, F. Anton, H. Aanaes, Guide to computational geometry processing, Foundations, Algorithms, and Methods, Springer-Verlag, London. (2012).