Module org.dyn4j

## 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.4.0
Author:
William Bittle
• ### Constructor Summary

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

All Methods
Modifier and Type Method Description
`(package private) DoubleEdgeList` `createTriangulation​(Vector2... points)`
Creates a triangulation of the given simple polygon and places it in the returned doubly-connected edge list (DCEL).
`java.util.List<Convex>` `decompose​(Vector2... points)`
Performs the decomposition on the given polygon returning a list of `Convex` shapes.
`(package private) void` ```end​(SweepLineVertex vertex, SweepLineState sweepstate)```
`(package private) void` ```merge​(SweepLineVertex vertex, SweepLineState sweepstate)```
`(package private) void` ```regular​(SweepLineVertex vertex, SweepLineState sweepstate)```
`(package private) void` ```split​(SweepLineVertex vertex, SweepLineState sweepstate)```
`(package private) void` ```start​(SweepLineVertex vertex, SweepLineState sweepstate)```
`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

`clone, equals, finalize, 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`>
• #### createTriangulation

`final DoubleEdgeList createTriangulation​(Vector2... points)`
Creates a triangulation of the given simple polygon and places it in the returned doubly-connected edge list (DCEL).
Parameters:
`points` - the vertices of the simple polygon to triangulate
Returns:
`DoubleEdgeList`
Since:
3.1.9
• #### start

```final void start​(SweepLineVertex vertex,
SweepLineState sweepstate)```
Parameters:
`vertex` - the vertex
`sweepstate` - the current state of the SweepLine algorithm
• #### end

```final void end​(SweepLineVertex vertex,
SweepLineState sweepstate)```
Parameters:
`vertex` - the vertex
`sweepstate` - the current state of the SweepLine algorithm
• #### split

```final void split​(SweepLineVertex vertex,
SweepLineState sweepstate)```
Parameters:
`vertex` - the vertex
`sweepstate` - the current state of the SweepLine algorithm
• #### merge

```final void merge​(SweepLineVertex vertex,
SweepLineState sweepstate)```
Parameters:
`vertex` - the vertex
`sweepstate` - the current state of the SweepLine algorithm
• #### regular

```final void regular​(SweepLineVertex vertex,
SweepLineState sweepstate)```
Parameters:
`vertex` - the vertex
`sweepstate` - the current state of the SweepLine algorithm