# sweepline_intersections 0.0.4 sweepline_intersections: ^0.0.4 copied to clipboard

A small and fast module using a sweepline algorithm to detect intersections between polygons and/or polylines.

Ported from: rowanwins/sweepline-intersections

# sweepline-intersections #

A small and fast module using a sweepline algorithm to detect intersections between polygons and/or polylines.

## Documentation #

### Install #

```
dart pub add sweepline_intersections
```

### Basic Use #

Valid inputs: Geojson `Feature`

or `Geometry`

including `Polygon`

, `LineString`

, `MultiPolygon`

, `MultiLineString`

, as well as `FeatureCollection`

.

Returns a List of intersection Points eg, [Point(coordinates:Position(lng:x1, lat:y1)), Point(coordinates:Position(lng:x2, lat:y2)]

```
var box = Feature(geometry: Polygon(coordinates: [[Position.of([0, 0]), Position.of([1, 0]), Position.of([1, 1]), Position.of([0, 1]), Position.of([0, 0])]]));
var intersections = sweeplineIntersections(box);
// returns a List of self-intersection Points
```

Also accepts an optional boolean argument second which when set to true means the module won't detect self-intersections and will only report intersections between different features. This defaults to false. eg

```
var intersectionsBetweenFeature = sweeplineIntersections(featureCollection, true);
// returns a List of intersection Points between Features
```

### Complex Use #

This library also provide a class-based approach which is helpful if you want to check multiple geometries against a single geometry. This allows you to save the state of the initial event queue with the primary geometry.

```
import 'package:sweepline_intersections/sweepline_intersections.dart';
main(){
// create the base instance
var sl = SweeplineIntersections();
sl.addData(aGeom);
// clone the event queue in the original state so you can reuse it
var origQueue = sl.cloneEventQueue();
List<Position> positions = [
Position.of([21.93869948387146, 49.99897434944081]),
Position.of([21.93869948387100, 49.99897434944032]),
];
var f = FeatureCollection(
features: [
Feature(
geometry: LineString(coordinates: positions),
),
],
); // now you can iterate through some other set of features saving
// the overhead of having to populate the complete queue multiple times
for (var feature in f.features) {
// add another feature to test against your original data
sl.addData(feature, alternateEventQueue: origQueue);
// check if those two features intersect
// add an optional boolean argument to ignore self-intersections
}
var intersectionPoints = sl.getIntersections(true);
}
```

#### API

`SweeplineIntersectionsClass()`

- creates a new instance

`.addData(geojson, existingQueue)`

- adds geojson to the event queue. The second argument for an `existingQueue`

is optional, and takes a queue generated from `.cloneEventQueue()`

`.cloneEventQueue()`

- clones the state of the existing event queue that's been populated with geojson. Returns a queue that you can pass to the `addData`

method

`.getIntersections(ignoreSelfIntersections)`

- Checks for segment intersections. Accepts an optional boolean argument to ignore self intersections are only report intersections between features.

## Contributing #

## Algorithm notes #

The basic concept of this algorithm is based on a sweepline. Where this algorithm differs from the bentley-ottmann algorithm is that there is no use of a tree data structure to store the segments. The reason for the modification is because if you are dealing with polygons or polylines (rather than a random group of line segments) there is a reasonable assumption that there are going to be very few segments that lie on the same x plane.

Removing the tree structure greatly simplifies the code. The tree structure is replaced with a priority queue of segments which is sorted by the x vertex of the right endpoint of the segments. A priority queue is already used to sort the vertices which means only 1 data structure is required.

### Algorithm Steps #

- Vertices are entered into a priority queue sorted from left to right
- An empty priority queue is created to store segments encountered
- An item is removed from the priority queue
- If the vertex is the left endpoint of a segment, we test it against every other segment in the segment queue for intersections with any intersection recorded. We then add the vertex (and it's associated right endpoint) to the segment queue.
- When we encounter a right endpoint we remove the first item from the segment queue.

Each pair of segments are only tested once. And only segments that overlap on the x plane are tested against each other.