search

Turfjs / turf-line-to-polygon

Transforms a LineString geometry to a (closed) Polygon geometry.
8 stars 2 forks source link

line intersect algorithm for robust line and multiline support #4

Open morganherlocker opened 9 years ago

morganherlocker commented 9 years ago

rough algorithm:

  1. get all line segments
  2. get all intersections between all line segments
  3. foreach intersection:
    1. add each vertex clockwise from the intersection
    2. at each intersection, take a "right turn" jump onto the intersecting segment
    3. add vertices to a new polygon ring

This could probably be done more quickly with some graph datastructures or possibly a sweepline. It will probably be O(n^2) at the fastest though. Also note that this approach throws out stray lines that do not intersect another segment. These could be wrapped as well using the method currently employed in a 2nd sweep.

Q: is this closer to the expected behavior of this tool? How does QGIS' Vector > Geometry Tools > Lines to polygons work?

morganherlocker commented 9 years ago

looks like this is how the qgis polygonizer plugin works:

http://confound.me.uk/maps/ppv4.pdf