What are degenerate polygons?

Question

What are degenerate polygons? How does one check whether a given pair of polygons is degenerate or not?

Answer 1

A polygon is degenerate if some of its vertices lie on each other. e.g the triangle (0,0),(0,1),(0,0) is degenerate. It has 3 sides, and 3 vertices, but two of vertices repeat. It's possible to repeat a vertex multiple times (for example (0,0),(0,0),(0,0) is another degenerate triangle). By definition, checking whether a polygon is degenerate or not is easy.

But what are the uses of degenerate polygons? One application from graphic acceleration (3D drawing) is as follows:

In 3D drawing GPUs normally use triangulation to render images. The (simple) reason for using triangles is because they are simplest possible 2D objects so don't need much hardware.

If we want to draw a complex 3D image, by this GPU limitation, we have to decompose it into multiple triangles. But if we call the GPU to render each triangle separately, it would be very slow (because of the number of calls). So the triangle strip is used to reduce the number of calls to the GPU. A good explanation of triangle strips can be found on Microsoft Documentation: Triangle Strips, also you can see the wiki for: Triangle Strip.

But the problem arises when we want to draw two separate objects in one strip. In this case degenerate triangles help. The GPU can detect the degenerate triangles and skip their drawing. So we can connect two separate strips with one degenerate triangle.

In general if we have $n$ different components, such that we already have their corresponding triangle strips, we can draw them all by just one call to the GPU. This causes to extra memory usage, but it is a trade off between the number of calls to the GPU for rendering and the overhead of using an extra, degenerate triangle.

Answer 2

As others have noted, it depends. Generally speaking, a polygon is non-degenerate if it has no anomalous points, but this just pushes the problem back one step; what is "anomalous"?

The real answer is that a polygon is degenerate if it violates the specification. The slightly rude answer is that a polygon is degenerate if it is an edge case which your algorithm can't handle.

Here's an example from the world of GIS. The OGC Simple Features Specification has a very careful definition of what makes a polygon "valid". Quoting from Section 6.1.11.1:

The assertions for Polygons (the rules that define valid Polygons) are as follows:

a) Polygons are topologically closed;

b) The boundary of a Polygon consists of a set of LinearRings that make up its exterior and interior boundaries;

c) No two Rings in the boundary cross and the Rings in the boundary of a Polygon may intersect at a Point but only as a tangent, e.g. $$\begin{align*} & \forall P \in \hbox{Polygon}, \forall c_1, c_2 \in \hbox{P.Boundary}, c_1 \ne c_2,\\ & \forall p, q \in \hbox{Point},\,p,q \in c_1, p \ne q,\\ & \left[ p \in c_2 \right] \Rightarrow \left[ \exists \delta > 0 | \left[\left|p-q\right|<\delta\right]\ \Rightarrow \left[ q \not\in c_2 \right] \right] \end{align*}$$;

Note: This last condition says that at a point common to the two curves, nearby points cannot be common. This forces each common point to be a point of tangency.

d) A Polygon may not have cut lines, spikes or punctures e.g.: $\forall P \in \hbox{Polygon}, P = \hbox{P.Interior.Closure}$;

e) The interior of every Polygon is a connected point set;

f) The exterior of a Polygon with 1 or more holes is not connected. Each hole defines a connected component of the exterior.

In the above assertions, interior, closure and exterior have the standard topological definitions. The combination of (a) and (c) makes a Polygon a regular closed Point set.

Answer 3

A degenerate polygon is one that has zero area. The answer chosen above does not fully define a degenerate polygon. Consider the case of a square with two identical vertices. This could be defined as one or two non-degenerate triangles.