PolyDecomp2D

Inherits: Reference < Object

Polygon partitioning.

Description

A singleton which provides various methods for polygon decomposition, partitioning etc.

A new local instance must be created manually with new_instance method if you need to override the default parameters, else the methods in this class are available globally:

var polygons = []
# Globally.
polygons = PolyDecomp2D.decompose_polygons([boundary, hole])
# Locally.
var pd = PolyDecomp2D.new_instance()
pd.parameters.fill_rule = PolyDecompParameters2D.FILL_RULE_EVEN_ODD
polygons = pd.decompose_polygons([boundary, hole])

Methods

Array decompose_polygons ( Array polygons, Decomposition type ) const
Array decompose_polygons_into_convex ( Array polygons ) const
Reference new_instance ( ) const
Array triangulate_polygons ( Array polygons ) const

Enumerations

enum Decomposition:

  • DECOMP_TRIANGLES_EC = 0 — Triangulate a polygon using the ear clipping algorithm. Time/Space complexity: O(n^2)/O(n).
  • DECOMP_TRIANGLES_OPT = 1 — Optimal triangulation in terms of edge length using dynamic programming algorithm. Time/Space complexity: O(n^3)/O(n^2).
  • DECOMP_TRIANGLES_MONO = 2 — Partition the polygon into monotone polygons, then triangulate. Time/Space complexity: O(n*log(n))/O(n).
  • DECOMP_CONVEX_HM = 3 — Convex polygon partitioning using Hertel-Mehlhorn algorithm. Time/Space complexity: O(n^2)/O(n).
  • DECOMP_CONVEX_OPT = 4 — Optimal convex partition using dynamic programming algorithm by Keil and Snoeyink. Time/Space complexity: O(n^3)/O(n^3).

Property Descriptions

Setter set_parameters(value)
Getter get_parameters()

Parameters to configure the default behavior of operations. Cannot be configured via the global instance, use new_instance first if you need to override the defaults.

Method Descriptions

Partitions polygons into several other convex polygons. The exact algorithm used depends on the type from Decomposition.

Both outer and inner polygons can be passed to cut holes during decomposition and are distinguished automatically, with potential performance cost.

Note: DECOMP_TRIANGLES_OPT and DECOMP_TRIANGLES_OPT do not support partitioning of a polygon with holes.

  • Array decompose_polygons_into_convex ( Array polygons ) const

Similar to decompose_polygons, but partitions polygons with the DECOMP_CONVEX_HM.

Instantiates a new local PolyDecomp2D instance, and parameters can be configured.

  • Array triangulate_polygons ( Array polygons ) const

Similar to decompose_polygons, but triangulates multiple polygons with the DECOMP_TRIANGLES_MONO.