alexbol99

alexbol99 / PolygonBooleanOp / 1.1.0

README.md

Boolean operations on polygons

BooleanOp algorithm performs fast and reliable boolean operations on polygons. It supports all basic operations on polygons:

  • unify
  • intersect
  • subtract

BooleanOp dependent on flatten-js javascript library. This library provides Polygon class definition together with the methods to treat faces and edges.
Polygon is actually a multi-polygon comprised from a number of faces. Each face is a closed loop of edges - segments or circular arcs. The orientation of faces (clockwise or counterclockwise) is matter, because algorithm implemented in the way that it never changes an original direction of the edge. For the boolean operation to be performed correctly, faces have to fit the following rules:

  1. Each face is a non-degenerated simple closed polygon. In another words, face should not have self-intersections and its orientation may be strictly defined.
  2. If one face is totally inside another face, its orientation should be opposite to the orientation of external face. Then we will call external faces islands and internal faces holes. So the rule is "no island inside island and no hole inside hole".
  3. Faces of the polygon should not overlap each other

BolleanOp algorithm does not check that input polygon fits these rules, this is on the responsibility of the caller.

The result of boolean operation is also a polygon. Note, that the resulted polygon may be empty, for example as the result of the intersection between two disjoint polygons.

Applicable Scenarios and Problems

What scenarios or problems would this algorithm work well in?

Usage

Input

ParameterDescription
Polygon1First Polygon in JSON format
Polygon2Second Polygon in JSON format
OperarionBoolean operation code

JSON format for polygon defined as an array of faces, where each face describes edges.

Face array may be defined in 2 forms:

  1. Simplified form - array of points as an array of numbers, where numbers at odd places describing x-coordinates and numbers ar even places describing y-coordinates
  2. Regular form - array of edges where each edge describes segment or arc in the following format:

Segment:

"
{
	"name": "segment",
	"ps" : {"x": number, "y": number},
	"pe" : {"x": number, "y": number}
}
"

Circular arc:

"
{
	"name": "arc",
	"pc": {"x": number, "y": number"},
	"r": number,
	"startAngle": number,
	"endAngle": number,
	"counterClockwise": boolean
}
"

Operation is one of the constants (defined in flatten-js library):

1 - Unify
2 - Intersect
3 - Subtract

What data pre-processing would be great to perform on the input before calling this algorithm?

Output

Output of the algorithm is also a polygon in the same JSON format

ParameterDescription
polygonResulted polygon

Examples

Provide and explain examples of input and output for your algorithm.