Skip to content

Instantly share code, notes, and snippets.

@NelsonMinar
Created September 28, 2021 15:08
Show Gist options
  • Save NelsonMinar/16b876fb74ecbdac0431288e8f5ae7b9 to your computer and use it in GitHub Desktop.
Save NelsonMinar/16b876fb74ecbdac0431288e8f5ae7b9 to your computer and use it in GitHub Desktop.
Hatching algorithm (in progress)
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment