Appropriate Clustering Algorithm
I'd rather not rely on clustering (clearly, DBSCAN would be the first method to try).

Instead, I'd look for a projection that removes the correlation (x - y maybe?), then define a grid to separate the data.