A robust method for calculating the simplicity and orientation of planar polygons (Q1183524)

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.