I'm having a go at rendering OpenStreetMap sea for one of my side projects: https://twitter.com/willsewell_/status/1172523752699113473/photo/1

I'm struggling to come up with an algorithm for rendering arbitrary coastline! But it's also quite a fun/challenging problem to think about.

I've had a go at writing up a simplified description of the core problem. I wonder whether anyone has any ideas for how to solve it?

Coastline is specified as "paths" (array) of points (x,y coordinates).

Example paths in a map covering coordinates 0,0 to 19,8:

[
  [(14,8),(14,1)(11,1),(11,3),(12,3),(12,5),(9,5),(9,0)],
  [(16,1),(16,3),(18,3),(18,1)],
  [(7,0),(7,8)],
  [(5,8),(5,3),(4,0)],
  [(2,0),(2,3),(0,3)],
  [(1,5),(3,5),(3,7),(1,7)]
]

These paths are directed (low index to high). Land is always on the "left" of the path. A cell in the map that has a path "on" it will be sea.

If a path ends on the same coordinate it started at, then it forms an island or inland sea.

Otherwise the start and end point will always be on the boundary of the map (and you can assume the sea/land continues beyond the extent of the map).

The paths are guaranteed to not intersect.

Rendering the example coastlines as land (Os) and sea (Xs) will produce this map:

XXXOXXXXOXXXXXXXXXXX
XXXOXXXXOXXXOOXXXOXX
XXXOXXXXOXXXOOXXXOXX
XXXOXXXXOXXXXOXXXXXX
OOOOOXXXOXXXXOXXXXXX
OXXXOXXXOOOOOOXXXXXX
OXXXOXXXOOOOOOXXXXXX
OXXXOXXXOOOOOOXXXXXX
OOOOOXXXOOOOOOXXXXXX

How would you implement this rendering for arbitrary coastlines? Pseudocode is fine.

You can assume you have access to a function fill function:

fill(
  map : array of arrays of X or O,
  path : a closed path
  fill : X or O
)

Please let me know if anything isn't clear.