PolyPartition Documentation

Before using any partitioning or triangulation methods, ensure your input polygons meet these requirements:

1. No self-intersections: Polygons must not intersect themselves.
2. Correct vertex order: Non-hole polygons must be counter-clockwise (CCW), and holes must be clockwise (CW).
3. Hole marking: Holes must be explicitly marked using TPPLPoly::SetHole(true).

You can automatically correct the vertex orientation by calling the TPPLPoly::SetOrientation method.

Use TPPLPartition::ConvexPartition_HM to partition a polygon into convex pieces. It has a time/space complexity of O(n^2)/O(n). The algorithm produces at most four times the minimum number of convex polygons, though it often performs better in practice.

Hole Support: Supports holes, but you must call TPPLPartition::RemoveHoles first.

TPPLPartition::ConvexPartition_HM(...);

Use TPPLPartition::Triangulate_OPT to achieve an optimal triangulation in terms of minimal edge length. It uses a dynamic programming algorithm with a time/space complexity of O(n^3)/O(n^2).

Hole Support: Does not support holes. While you can call TPPLPartition::RemoveHoles before invoking this method, the resulting solution will no longer be optimal.

TPPLPartition::Triangulate_OPT(...);

Use TPPLPartition::Triangulate_EC for a satisfactory triangulation in most cases. It has a time/space complexity of O(n^2)/O(n).

Hole Support: Supports holes, but you must call TPPLPartition::RemoveHoles first to ensure they are handled correctly.

TPPLPartition::Triangulate_EC(...);

Use TPPLPartition::ConvexPartition_OPT to produce the minimum number of convex polygons using the Keil and Snoeyink dynamic programming algorithm. It has a time/space complexity of O(n^3)/O(n^3).

Hole Support: Does not support holes. Calling TPPLPartition::RemoveHoles beforehand will prevent the algorithm from producing an optimal solution.

TPPLPartition::ConvexPartition_OPT(...);

Use TPPLPartition::Triangulate_MONO for a fast triangulation with a time/space complexity of O(n*log(n))/O(n).

Hole Support: Supports holes by design.

Note: The quality of the solution is generally poor, as it often produces many thin triangles.

TPPLPartition::Triangulate_MONO(...);

You can customize the precision and math functions used by the library by defining macros before including polypartition.h:

• tppl_float: Defines the floating-point type (defaults to double).
• tppl_sqrt: Defines the square root function (defaults to sqrt).

If TPPL_ALLOCATOR is defined, TPPLPolyList and DiagonalList will use the provided allocator instead of std::list defaults.

#define tppl_float float
#define tppl_sqrt sqrtf
#include "polypartition.h"

The RemoveHoles method uses a heuristic to convert a list of polygons containing holes into a list of simple polygons without holes. It works by creating diagonals from the right-most hole vertex to a visible vertex.

Requirements:

• Non-hole polygons must have vertices in counter-clockwise order.
• Hole polygons must have vertices in clockwise order.

Complexity:

• Time: $O(h imes n^2)$ where $h$ is the number of holes and $n$ is the number of vertices.
• Space: $O(n)$

Returns: 1 on success, 0 on failure.

Use TPPLPartition to decompose polygons into convex sub-polygons.

Available Algorithms:

• ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts): Hertel-Mehlhorn algorithm. Complexity: $O(n^2)$. Provides a partition that is at most 4x the optimal number of parts.
• ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts): Hertel-Mehlhorn for a list of polygons (handles holes).
• ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts): Optimal convex partitioning using the Keil-Snoeyink algorithm. Complexity: $O(n^3)$.

All methods return 1 on success and 0 on failure.

TPPLPartition partitioner;
TPPLPoly poly;
// ... initialize poly ...
TPPLPolyList convexParts;
int success = partitioner.ConvexPartition_HM(&poly, &convexParts);

The TPPLPoly class represents a polygon as an array of TPPLPoint objects. A polygon can be designated as a 'hole' using SetHole(bool).

Key operations:

• Init(long numpoints): Initializes the polygon with a specific number of vertices.
• Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3): Quickly creates a triangle.
• GetOrientation() / SetOrientation(TPPLOrientation orientation): Manages vertex order. Valid orientations are TPPL_ORIENTATION_CCW (counter-clockwise) and TPPL_ORIENTATION_CW (clockwise).
• Invert(): Reverses the order of vertices.
• Valid(): Returns true if the polygon has at least 3 points.

TPPLPoly poly;
poly.Init(3);
poly.GetPoint(0) = {0.0, 0.0, 0};
poly.GetPoint(1) = {1.0, 0.0, 1};
poly.GetPoint(2) = {0.0, 1.0, 2};
poly.SetOrientation(TPPL_ORIENTATION_CCW);

The TPPLPoint struct represents a 2D coordinate with x and y components of type tppl_float (defaults to double). It includes an id field for user-specified vertex identifiers, which is preserved during library operations but not used for internal logic.

TPPLPoint supports standard arithmetic operators: +, -, * (scalar), and / (scalar), as well as equality == and inequality != checks.

TPPLPoint p1 = {10.0, 20.0, 1};
TPPLPoint p2 = {5.0, 5.0, 2};
TPPLPoint p3 = p1 + p2;