×

A robust method for calculating the simplicity and orientation of planar polygons. (English) Zbl 0742.65105

Many graphics systems, like the wire frame models, require the use of planar polygons and some shading algorithms. The construction of such polygon must conform to a precise set of rules so that the modeler can form the expected model. Computational difficulties can arise when determining whether a planar polygon is simple, in particular when two or more sides are almost parallel.
The main purpose is to present algorithms that will classify a polygon as being or not being ill-defined (in the sense that the rendering is unexpected). For this it is necessary to test whether pairs of line segments intersect by solving ill-conditioned systems of equations. The algorithm of this paper is different in that it does not produce the actual points of intersection of the segments of the polygon, rather it produces only the needed information as to whether or not the segments intersect. Computationally, this is reflected in the fact that the function associated with the algorithm is essentially two valued, which is an important factor in its numerical stability.
Another algorithm is designed to solve the problem of deciding whether a simple contour is oriented clockwise or counter-clockwise.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI

References:

[1] Foley, J. D.; Van Dam, A., Fundamentals of Interactive Computer Graphics (1984), Addison-Wesley: Addison-Wesley Reading, MA
[2] Mortenson, M. E., Geometric Modeling (1985), Wiley: Wiley New York
[3] Rogers, D. F., Procedural Elements for Computer Graphics (1985), McGraw-Hill: McGraw-Hill New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.