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.
Wanted to split a polygon by a linestring and noticed that there's no "out of the box" method w/ shapely/turf/other popular libs. Ended up going down a rabbit hole but got it to work w/ triangulation of the polygon - surprisingly tricky! pic.twitter.com/xGTVcSYWNu— Kuan Butts (@buttsmeister) May 30, 2020
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.
Oh wow that's embarrassing! Thanks for pointing that out. For some reason, I'd always been under the impression it did (multi)linestrings split by points, but not polygons. 😐 pic.twitter.com/nUTIiCkNpi— Kuan Butts (@buttsmeister) May 31, 2020
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:
- Learn how the method worked in Shapely (what was the underlying algorithm).
- 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:
Visualizing the result should look something like the following image:
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
- union the dividing line and the polygon exterior with
polygonizeon 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
We can see this logic applied in the code as well as extracted and highlighted below:
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.