Implicit Representation of Simple Polygons Using Monotone Formulas

This interactive WebGL reconstruction extends the implicit polygon representation from convex and star polygons to general simple polygons using a monotone MIN/MAX formula. Draw a simple polygon and press Compute Monotone Formula. The original polygon algorithm constructs a read-once MIN/MAX tree from the polygon half-spaces. The resulting Boolean representation can then be replaced by Rvachev or Akleman–Chen exact and approximate operations and explored interactively without changing the polygon or recomputing the tree.

Research basis: Akleman & Chen, “Constant Time Updateable Operations for Implicit Shape Modeling” (PDF)
DRAWING MODE: click successive vertices of a simple polygon. The red polygon is only the input polygon. When finished, press “Compute Monotone Formula.”
Monotone Formula. Draw a simple polygon and compute its read-once MIN/MAX tree. Each polygon half-space appears once in the monotone formula. The polygon and tree remain fixed until New polygon is selected.
Boolean Operations. MIN/MAX provides the Boolean representation. Rvachev and Akleman–Chen operations replace these Boolean combinations with continuous functional operations.
Display. Implicit Function uses bands to visualize the sign and magnitude of the continuous implicit function. Implicit Shape shows only the inside/outside region defined by its zero set.
Monotone Polygon Representation. The algorithm used to construct the monotone Boolean representation of a simple polygon follows D. Dobkin, L. Guibas, J. Hershberger, and J. Snoeyink (1988), “An Efficient Algorithm for Finding the CSG Representation of a Simple Polygon,” Computer Graphics, 22(4), 31–40.
Rvachev Operation. The Rvachev operation implemented here follows the formulation presented by A. Pasko, V. Adzhiev, A. Sourin, and V. Savchenko (1995), “Function Representation in Geometric Modeling: Concepts, Implementations and Applications,” The Visual Computer, 11, 429–446, based on Rvachev’s earlier work on R-functions.
Akleman–Chen Operations. The exact and approximate operations are described in E. Akleman and J. Chen (1999), “Constant Time Updateable Operations for Implicit Shape Modeling” (PDF).