Module org.dyn4j
Package org.dyn4j.geometry.decompose

## Class SweepLine

• java.lang.Object
• org.dyn4j.geometry.decompose.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.2.0
Author:
William Bittle
• ### Constructor Summary

Constructors
Constructor Description
`SweepLine​()`
• ### Method Summary

All Methods
Modifier and Type Method Description
`java.util.List<Convex>` `decompose​(Vector2... points)`
Performs the decomposition on the given polygon returning a list of `Convex` shapes.
`java.util.List<Triangle>` `triangulate​(Vector2... points)`
Performs the triangulation on the given polygon returning a list of `Triangle`s.
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### SweepLine

`public SweepLine​()`
• ### Method Detail

• #### decompose

`public java.util.List<Convex> decompose​(Vector2... points)`
Description copied from interface: `Decomposer`
Performs the decomposition on the given polygon returning a list of `Convex` shapes.
Specified by:
`decompose` in interface `Decomposer`
Parameters:
`points` - the polygon vertices
Returns:
List<`Convex`>
• #### triangulate

`public java.util.List<Triangle> triangulate​(Vector2... points)`
Description copied from interface: `Triangulator`
Performs the triangulation on the given polygon returning a list of `Triangle`s.
Specified by:
`triangulate` in interface `Triangulator`
Parameters:
`points` - the polygon vertices
Returns:
List<`Triangle`>