Dynamic Set Difference of Simple Polygons Using Monotone Formulas

Two general simple polygons, A and B, are represented by independently and dynamically recomputed monotone MIN/MAX formulas. The final shape is A − B = A ∩ Bᶜ. Complementing B is obtained by multiplying its implicit function by −1 before the final intersection. Add or drag vertices in either polygon and the formulas and implicit result update immediately.

Polygon A is red; Polygon B is green. Choose which polygon to edit. Click empty space to add a vertex; drag any vertex to move it.
Dynamic Monotone Formulas. A and B each have their own read-once MIN/MAX tree. Editing either polygon recomputes only that polygon’s monotone formula.
Set Difference. The final representation is A − B = A ∩ Bᶜ. The function for B is multiplied by −1 and combined with A using the selected intersection operation.
Display. Implicit Function visualizes sign and magnitude using bands. Implicit Shape shows the inside/outside region defined by the zero set.
Monotone Polygon Representation. 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. 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, presenting the Rvachev formulation used here.
Akleman–Chen Operations. E. Akleman and J. Chen (1999), “Constant Time Updateable Operations for Implicit Shape Modeling” (PDF).