title: Compression of a 2D point set - ideas?
body: <p>I have a set of 2D points stored in an array. <strong>I need to compress it as much as I can.</strong> Preferably fast, but not a deal breaker, compression rate is the goal. The rules are:</p>
  
  <ul>
  <li>a point = a 32-bit structure, stored as (x,y), 2 bytes for each coordinate</li>
  <li>a coordinate = a "float" with 8 bits integer part, 8 bits fractional part</li>
  </ul>
  
  <p>Special properties:</p>
  
  <ul>
  <li><strong>I may change the order of the points as I see fit</strong></li>
  <li>I'm given the points in the order of the integer parts of their x and y, maybe I can exploit that, but the fractional parts are pretty much random from what I saw</li>
  <li>the array I receive is contiguous (from a memory standpoint)</li>
  </ul>
  
  <p>What I've researched so far:</p>
  
  <ul>
  <li>consider them plain integers (32 bit), sort them (the order is mine to choose), then compress it as in <a href="https://stackoverflow.com/questions/283299/best-compression-algorithm-for-a-sequence-of-integers">this question</a>.</li>
  <li>consider my array as a plain char string, then apply <a href="http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform" rel="nofollow noreferrer">a Burrows-Wheeler transform</a> (BWT) with <a href="http://en.wikipedia.org/wiki/Run-length_encoding" rel="nofollow noreferrer">run-length encoding</a>, or <a href="http://en.wikipedia.org/wiki/Huffman_coding" rel="nofollow noreferrer">Huffman</a></li>
  <li>treat my array as plain binary data, then apply an <a href="http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch" rel="nofollow noreferrer">LZW</a></li>
  </ul>
  
  <p>I only managed to implement Huffman and BWT, but neither of them gives me a good compression ratio (or use the main property of my data set). I'm going to try the first option today.</p>
  
  <p><strong>I'm sure there are better ideas. Do you have any?</strong> Did you come across anything similar and implemented something really good?</p>
  
  <p>Dataset example, in hex:</p>
  
  <pre><code>00 0A 00 77 00 55 00 80 00 2B 00 B9 00 7A 00 5B 
  00 F6 00 76 00 B4 00 25 00 47 00 D3 00 F6 00 7D
  ...
  01 05 00 A9 01 B8 00 10 01 4F 00 6A 01 E6 00 DF
  01 1F 00 F0 01 BE 00 C3 01 6C 00 87 01 CE 00 44
  ...
  ...
  15 06 03 F4 15 1E 03 29 15 35 03 10 15 B9 03 22
  15 67 03 73 15 EF 03 5C 15 29 03 B8 15 4C 03 2F
  ...
  </code></pre>
  
  <p>where e.g. the particle <code>15 67 03 73</code> (last row) means particle at x = 15 and 67/256, y = 3 and 73/256. As you see, the data is somewhat ordered but the fractional parts are in a total disarray.</p>