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.