algorithm - Optimal solution for clustering of rectangles

Question

I am looking for some approach (algorithm to be very specific) here.

Problem:There are N rectangles (r1, r2,.. rn) scattered in X-Y plane. Need to find optimal solution to cluster these rectangles with bigger bounded polygons.

Condition for clustering:

1. Results should have maximum number of rectangles covered in the polygon.
2. Total count of bounded polygon should be minimum possible and maximum K.
3. Each bounded polygon must have at least 70% area filled with given rectangles.
4. All rectangles need not to be bounded.

constraint:

• 1 millions <= n <= billions
• K = 50000

Problem can be thought of as to identify islands (max 50k island) having higher density of rectangles (70% in each island). We can off course exclude certain rectangles. But the idea is to find optimal solution and there is no single best solution.

I was trying to use K-means clustering but it doesn't fit in my case as in my problem solution can lie within 1-K values instead of K values. May be it requires all together different dimension of thinking. Hope I am clear!!

Adding image to be just more clearer:

标签： algorithmdata-structurescluster-computingcluster-analysismarkerclusterer