CODEWITHSUNDEEP
algorithmgrouping
Laurent Crivello
Laurent Crivello

Reputation: 3931

Spread points equally

This is more an algorithm than a development question.
I have many locations in a country (represented by geographical coordinates) and would like to group them so that each group covers a same area (the amount of different areas is fixed), and that each group roughly contains the same number of locations.

What would be the best method to reach this ?

Upvotes: 0

Views: 290

Answers (1)

imfede
imfede

Reputation: 36

Ok let's define things (in pseudocode):

location: (double x-coord, double y-coord)

that is, every location is just two numbers. Let's say you have M locations.

group: array of (array of locations)

so that group[i] is an array that contains the locations of the i-th group. Now, you know beforehand that you will end up with a fixed amount of groups (if i understood correctly what you are asking), let's call it N. So every group will have roughly M/N locations. Now, your main problem is that you cannot order couples of numbers (ie complex numbers are not ordinable) but here is what i would do:

  1. construct a matrix matrix[i][j] so that every cell contain a location. For my idea to work you have to make that (let's borrow some OO notation):

    • matrix[i][j].x <= matrix[i+1][j].x
    • matrix[i][j].y <= matrix[i][j+1].y.

    In order for this to work some cells may be empty. Just discard them in the next phase.

  2. Then you define a group as a submatrix that contain only adjacent locations (or locations that you can reach travelling only on adjacent locations). So you start a for cycle (java/c notation) for(int i=0; i<N; i++) and inside you add element to group[i] until group[i].length reaches M/N; then you go to the next i. I would iterate the matrix using something like (0,0),(0,1),(1,0),(1,1),(0,2),(2,0),(2,1),(1,2),(2,2)... but you can implement it in some different way (for example taking into account the difference between coordinates so that you group together only "close" locations but that depends on what you need.

Your problem is not easy but if you only need a rough grouping it can be done easily.

Upvotes: 2

Related Questions