Hatching algorithm (in progress)

hatch.py

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)