A simple solution is paint the sea with triangles of which one side is perfectly horizontal. And always work bottom to top.

You will have to pre scan the ways for instance where they change from ascending to descending. Here the sea will spilt into a left and right section. Make a list of these and sort them from top to bottom.

While generating triangles, check that list to where you should split.