I'm out fishing for ideas here.

I have a hash containing data on about 200 locations on a map. These locations are not evenly distributed, they tend to clutter around a few central locations, like suburbs to a metropolis.

I use a complicated object hierarchy to manipulate the map and import/export a lot of stuff that really has no bearing on this particular problem. So, let's just say the data structure looks like this: 

%sites = (
  1   => { x => 65.1231, y => 23.1512 },
  2   => { x => 64.2327, y => 17.5328 },
  3   => { x => 66.1634, y => 21.2512 },
#  ...
  200 => { x => 65.6231, y => 21.8924 }
);

[download]

The thing is, when plotting these locations on a map, the central areas become a dense mess with a lot of empty space in between. I would like to rearrange the locations into a sort of 'grid' which guarantees a minimum space between each location, and removes any unnecessary empty space.

Guaranteeing the minimum space is relatively easy. Closing the gaps is the problem. Consider the following map with 6 locations: 

XX...
X....
.....
....X
...XX

[download]

Examining %sites I would probably want to compress this to something like this: 

XX.
X.X
.XX

[download]

For a human, this problem is trivial to solve visually but I have no idea how to do it efficiently in code. I can't help thinking that someone else must have had this problem before me, so perhaps there's a module for it?

Update: Plenty of good ideas here, I'll have to take some time to read about the different approaches suggested. Thank you :-)

-- Time flies when you don't know what you're doing

In reply to Distribute locations evenly on a map by FloydATC

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.