NelsonMinar · September 28, 2021 15:08 · Sep 28, 2021
diff --git a/hatch.py b/hatch.py
@@ -0,0 +1,65 @@
+def hatch(polygon, spacing: float = 1, rotation: float = 0, tolerance: float = 5, inset: float = 0) -> shapely.geometry.MultiLineString:
+	"""
+        Fill a polygon with hatched lines.
+	Note this code is unit-independent. The default spacing of 1 was chosen with the idea of the units being
+	millimeters and the pen width being 0.5mm, for a 50% fill.
+
+        :param polygon: the shape to generate a hatch for
+        :param spacing: space between hatch lines
+        :param rotation: rotation of hatch lines (in degrees)
+        :param tolerance: limit on length of joining lines to make hatches a single line. Multiples of spacing.
+	:param inset: absolute amount of spacing to give inside the polygon before hatch lines. Can be negative.
+        :return: a collection of lines that represent the hatching
+        """
+	hatch_polygon = polygon
+	if inset != 0:
+		hatch_polygon = polygon.buffer(-inset)
+	# Make a square big enough to cover the whole object, even when rotated 45 degrees.
+	# sqrt(2) should be big enough but it seemed wise to pad this out a bit
+	hatch_box = shapely.affinity.scale(hatch_polygon, 1.6, 1.6)
+	xmin, ymin, xmax, ymax = hatch_box.bounds  # type:ignore
+
+	# Draw horizontal lines to fill the box
+	lines = tuple(((xmin, y), (xmax, y)) for y in more_itertools.numeric_range(ymin, ymax, spacing))
+	mls = shapely.geometry.MultiLineString(lines)
+
+	# Rotate the lines
+	mls = shapely.affinity.rotate(mls, rotation)
+
+	# And intersect them with the polygon
+	cropped = mls.intersection(hatch_polygon)
+
+	# Now try to merge the lines boustrophedonically. This algorithm relies on the lines being sorted nicely by
+	# intersection(). It does not work on messy polygons: concave or those with holes. The intersection operation
+	# seems to mostly preserve ordering of the line collection but if it has to break a line it seems to insert new
+	# lines in-place when putting them at the end would be more helpful to this algorithm. I think complex polyognos
+	# could be supported by making the code actually search for the closest next line to join to, instead of relying
+	# on intersection() returning lines in a useful order. for the small number of lines a simple scan would
+	# probably work. Optimizations would be to counter-rotate the lines back to horizontal and sort by Y, or maybe
+	# build a full spatial index.
+	lines = list(cropped.geoms)  # type: ignore
+	merged = []  # collection of new merged lines
+	to_merge = list(lines[0].coords)  # accumulate the next new merged line here
+	which_end = 1  # whether we're at the left end of the line or the right
+	join_limit = (spacing * tolerance)**2  # squared to avoid sqrt in distance calculation
+	for line in lines[1:]:
+		# Endpoint of the previous line we're building up
+		old_x, old_y = to_merge[-1]
+		# New candidate line and the point we're considering merging in
+		lc = line.coords
+		new_x, new_y = lc[which_end]
+		# Check the distance of the new candidate joining line
+		if ((new_x - old_x)**2 + (new_y - old_y)**2) < join_limit:
+			# Small enough? Attach candidate line to the line we're building
+			to_merge.append((new_x, new_y))
+			to_merge.append(lc[1 - which_end])
+		else:
+			# Too far away; start a new line
+			merged.append(to_merge)
+			to_merge = list(lc)
+		which_end = 1 - which_end  # turn the ox around
+	merged.append(to_merge)  # bring in the final line
+
+	# print(f'{len(merged)} lines in hatch pattern')
+	# And return the hatch lines as a collection
+	return shapely.geometry.MultiLineString(merged)