kuan butts

Slicing polygons with linestrings

Jul 7, 2020
6 minute read

Update

Note that the method/solution shown below works with Turf version 5.1.6 and prior. Turf v6 has introduced breaking changes that do not allow the below solution to work. I will update later if I am able to determine a work-around.

Introduction

I recently wanted to explore if it was possible to divide a polygon into two parts by slicing it with a line. My initial exploration involved triangulating the polygon based on all intersecting points on the polygon exterior with the line string and then re-assembling from there.

Above: My tweet in which I first put out the concept.

In response to this proposal, a Twitter user pointed out that Shapely in fact already has a method called split() and that it supports splitting a polygon with a line string.

Above: A Twitter user pointing out the split() functionality that is available in Shapely now.

Learning about this method lead me to want to do two things:

  1. Learn how the method worked in Shapely (what was the underlying algorithm).
  2. There did not appear to be a method that was the same in TurfJS - so could I learn from the algorithm in Shapely and re-implement the slice method in TurfJS?

Having it run in TurfJS would be advantageous because I could leverage interactive drawing tools in MapboxGL and allow a user to draw the line string that they wanted to use to cut the polygon. I ended up making a crude site to demonstrate this functionality (as is shown above).

How Shapely cuts polygons

Shapely achieves the slicing by employing a method called polygonize. You can see the source code here. This method takes a multiline string and creates polygons from each of the shapes. This is similar to my triangle method, but less prone to error since the triangles I was generating needed to be trimmed and fit back against the original polygon.

For shapely, the steps for split in this case were as follows:

  • Take the polygon and get the exterior boundary of it as a line
  • Take the slice line and the polygon exterior and union the two together (this will catch all those intersecting points)
  • Use the polgyonize method to create polygons from the negative space in the union-ed lines
  • Iterate through all the resulting polygons and keep only the ones that have a point inside the original polygon

We can see those steps employed in the _split_polygon_with_line method here.

Or, we can re-write it ourselves using the underlying polygonize method like so:

from shapely.geometry import LineString, MultiPolygon, Polygon, Point
from shapely.ops import polygonize

# make a complex geometry
input_p = Polygon([[8.80228042602539,60.34198591102353], ... [8.80228042602539,60.34198591102353]])

# and a complex intersecting line
input_l = LineString([[8.784770965576172,60.33535977571523], ...[8.82150650024414,60.3352748165263]])

# union the exterior lines of the polygon with the dividing linestring
unioned = input_p.boundary.union(input_l)

# use polygonize geos operator and filter out poygons ouside of origina input polygon
keep_polys = [poly for poly in polygonize(unioned) if poly.representative_point().within(input_p)]

# remaining polygons are the split polys of original shape
MultiPolygon(keep_polys)

Visualizing the result should look something like the following image:

shapely_version

Bringing this functionality over to TurfJS

So I thought it would be great to have this in TurfJS especially because TurfJS can be used in conjunction with MapboxGL Draw to allow for interactive “slicing” of a polygon.

I created a very coarse example of how this would be accomplished and integrated with Draw into an interactive experience and posted it as a Gist here.

[Here] is a video of the simple example page being used, as I posted on Twitter:

The logic followed parallels that used in Shapely. Although TurfJS does not have a split() method available in the same way that Shapely does, it does have the ability to execute each step:

  • convert a polygon to a line with turf.polygonToLine
  • union the dividing line and the polygon exterior with union
  • run polygonize on the unioned lines (just like in Shapely, although the TurfJS docs do not make that immediately clear)
  • filter polygons that do not have a point within the polygon with turf.pointOnFeature and turf.booleanPointInPolygon

We can see this logic applied in the code as well as extracted and highlighted below:

const polyAsLine = turf.polygonToLine(poly);
const unionedLines = turf.union(polyAsLine, line);
const polygonized = turf.polygonize(unionedLines);
const keepFromPolygonized = polygonized["features"].filter(ea => turf.booleanPointInPolygon(turf.pointOnFeature(ea), poly));

The result achieves the same ability to take a polygon and slice it with a line string provided. The upside is that now it can be done all on the client side, with TurfJS, and leverage the power of tools like MapboxGL Draw which allows the user to interactively “slice” a polygon.