Skip to main content
Tweeted twitter.com/StackGIS/status/1438427450904616968
edited title
Link
mhdadk
  • 221
  • 1
  • 8

How is polygon intersection implemented in JTS/Shapely?

edited tags
Link
gene
  • 55.4k
  • 3
  • 113
  • 191
Source Link
mhdadk
  • 221
  • 1
  • 8

How is polygon intersection implemented in JTS?

I am using Shapely, which from the questions

uses the JTS as a backend. However, none of the answers to these questions specify which algorithm is used in JTS to compute the intersection of two polygons. I've checked the question Are there any references which describe the algorithms used in JTS? on the JTS website, but with no luck.

More specifically, if I write

from shapely.geometry import Polygon
import math

sqrt2 = math.sqrt(2)

# this is a square
A = Polygon([(1,1),(1,-1),(-1,-1),(-1,1)])

# this is the square A rotated by 45 degrees counter-clockwise
B = Polygon([(0,sqrt2),(sqrt2,0),(0,-sqrt2),(-sqrt2,0)])

# intersection of A and B, which is an octagon
C = A.intersection(B)

which algorithm is used by JTS to compute the polygon C? Is it the Sutherland-Hodgman algorithm?