Module org.dyn4j

Class SweepLine

  • All Implemented Interfaces:
    Decomposer, Triangulator

    public class SweepLine
    extends java.lang.Object
    implements Decomposer, Triangulator
    Implementation of the Sweep convex decomposition algorithm for simple polygons.

    This algorithm first decomposes the polygon into y-monotone polygons, then decomposes the y-monotone polygons into triangles, finally using the Hertel-Mehlhorn algorithm to recombine the triangles into convex pieces.

    This algorithm is O(n log n) complexity in the y-monotone decomposition phase and O(n) in the triangulation phase yielding a total complexity of O(n log n).

    After triangulation, the Hertel-Mehlhorn algorithm is used to reduce the number of convex pieces. This is performed in O(n) time.

    This algorithm total complexity is O(n log n).

    Since:
    2.2.0
    Version:
    3.4.0
    Author:
    William Bittle