Хорошая идея тут сделать диаграмму Вороного и в процессе ее построения взять какую-то сетку на карте (скажем, из квадратиков) и для каждой ячейки сетки запомнить список вершин водоемов, области которых пересекаются с этой ячейкой.
And if you listen very hard the alg will come to you at last.
