<p>Using C++ (and Qt), I need to process a big amount of 3D coordinates.</p>

<p>Specifically, when I receive a 3D coordinate (made of 3 doubles), I need to check in a list if this coordinate has already been processed.
If not, then I process it and add it to the list (or container).</p>

<p>The amount of coordinates can become very big, so I need to store the processed coordinates in a container which will ensure that checking if a 3D coordinate is already contained in the container is fast.</p>

<p>I was thinking of using a map of a map of a map, storing the x coordinate, then the y coordinate then the z coordinate, but this makes it quite tedious to use, so I'm actually hoping there is a much better way to do it that I cannot think of.</p>

[{'answer_id': 72178, 'author': 'slicedlime', 'author_id': 11230, 'author_profile': 'https://Stackoverflow.com/users/11230', 'pm_score': 1, 'selected': False, 'text': '<p>Well, it depends on what\'s most important... if a tripple map is too tedious to use, then is implementing other data structures not worth the effort?</p>\n\n<p>If you want to get around the uglyness of the tripple map solution, just wrap it up in another container class with an access function with three parameter, and hide all the messing around with maps internally in that.</p>\n\n<p>If you\'re more worried about the runtime performance of this thing, storing the coordinates in an <a href="http://en.wikipedia.org/wiki/Octree" rel="nofollow noreferrer">Octree</a> might be a good idea.</p>\n\n<p>Also worth mentioning is that doing these sorts of things with floats or doubles you should be very careful about precision -- if (0, 0, 0.01) the same coordinate as (0, 0, 0.01000001)? If it is, you\'ll need to look at the comparison functions you use, regardless of the data structure. That also depends on the source of your coordinates I guess.</p>\n'}, {'answer_id': 72195, 'author': 'Leigh Caldwell', 'author_id': 3267, 'author_profile': 'https://Stackoverflow.com/users/3267', 'pm_score': 1, 'selected': False, 'text': '<p>Are you expecting/requiring exact matches? These might be hard to enforce with doubles. For example, if you have processed (1.0, 1.0, 1.0) and you then receive (0.9999999999999, 1.0, 1.0) would you consider it the same? If so, you will need to either apply some kind of approximation or else define error bounds.</p>\n\n<p>However, to answer the question itself: the first method that comes to mind is to create a single index (either a string or a bitstring, depending how readable you want things to be). For example, create the string "(1.0,1.0,1.0)" and use that as the key to your map. This will make it easy to look up the map, keeps the code readable (and also lets you easily dump the contents of the map for debugging purposes) and gives you reasonable performance. If you need much faster performance you could use a hashing algorithm to combine the three coordinates numerically without going via a string.</p>\n'}, {'answer_id': 72200, 'author': 'Head Geek', 'author_id': 12193, 'author_profile': 'https://Stackoverflow.com/users/12193', 'pm_score': 1, 'selected': False, 'text': '<p>How about using a boost::tuple for the coordinates, and storing the tuple as the index for the map?</p>\n\n<p>(You may also need to do the divide-by-epsilon idea from this answer.)</p>\n'}, {'answer_id': 72206, 'author': 'moonshadow', 'author_id': 11834, 'author_profile': 'https://Stackoverflow.com/users/11834', 'pm_score': 0, 'selected': False, 'text': '<p>Pick a constant to scale the coordinates by so that 1 unit describes an acceptably small box and yet the integer part of the largest component by magnitude will fit into a 32-bit integer; convert the X, Y and Z components of the result to integers and hash them together. Use that as a hash function for a map or hashtable (NOT as an array index, you need to deal with collisions).</p>\n\n<p>You may also want to consider using a fudge factor when comparing the coordinates, since you may get floating point values which are only slightly different, and it is usually preferable to weld those together to avoid cracks when rendering.</p>\n'}, {'answer_id': 72219, 'author': 'Veynom', 'author_id': 11670, 'author_profile': 'https://Stackoverflow.com/users/11670', 'pm_score': 1, 'selected': False, 'text': "<p>Use any unique transformation of your 3D coordinates and store only the list of the results.</p>\n\n<p>Example:\nmd5('X, Y, Z') is unique and you can store only the resulting string.</p>\n\n<p>The hash is not a performant idea but you get the concept. Find any methematic unique transformation and you have it.</p>\n\n<p>/Vey</p>\n"}, {'answer_id': 72227, 'author': 'zweiterlinde', 'author_id': 6592, 'author_profile': 'https://Stackoverflow.com/users/6592', 'pm_score': 0, 'selected': False, 'text': "<p>If you write a helper class with a simple public interface, that greatly reduces the practical tedium of implementation details like use of a <code>map&lt;map&lt;map&lt;&gt;&gt;&gt;</code>.  The beauty of encapsulation!</p>\n\n<p>That said, you might be able to rig a hashmap to do the trick nicely.  Just hash the three doubles together to get the key for the point as a whole.  If you're concerned about to many collisions between points with symmetric coordinates (e.g., (1, 2, 3) and (3, 2, 1) and so on), just make the hash key asymmetric with respect to the x, y, and z coordinates, using bit shift or some such.</p>\n"}, {'answer_id': 72238, 'author': 'Vytautas Šaltenis', 'author_id': 6763, 'author_profile': 'https://Stackoverflow.com/users/6763', 'pm_score': 4, 'selected': True, 'text': '<p>Probably the simplest way to speed up such processing is to store the already-processed points in <a href="http://en.wikipedia.org/wiki/Octree" rel="noreferrer">Octree</a>. Checking for duplication will become close to logarithmic.</p>\n\n<p>Also, make sure you tolerate round-off errors by checking the distance between the points, not the equality of the coordinates.</p>\n'}, {'answer_id': 72266, 'author': 'Tyler', 'author_id': 3561, 'author_profile': 'https://Stackoverflow.com/users/3561', 'pm_score': 0, 'selected': False, 'text': '<p>You could use a <a href="http://www.sgi.com/tech/stl/hash_set.html" rel="nofollow noreferrer">hash_set</a> of any hashable type - for example, turn each tuple into a string "(x, y, z)".  hash_set does fast lookups but handles collisions well.</p>\n'}, {'answer_id': 72269, 'author': 'tzot', 'author_id': 6899, 'author_profile': 'https://Stackoverflow.com/users/6899', 'pm_score': 0, 'selected': False, 'text': '<p>Whatever your storage method, I would suggest you decide on an epsilon (minimum floating point distance that differentiates two coordinates), then divide all coordinates by the epsilon, round and store them as integers.</p>\n'}, {'answer_id': 72350, 'author': 'Roel', 'author_id': 11449, 'author_profile': 'https://Stackoverflow.com/users/11449', 'pm_score': 0, 'selected': False, 'text': '<p>Something in this direction maybe:</p>\n\n<pre><code>struct Coor {\n    Coor(double x, double y, double z)\n    : X(x), Y(y), Z(z) {}\n    double X, Y, Z;\n}\n\nstruct coords_thesame\n{\n  bool operator()(const Coor&amp; c1, const Coor&amp; c2) const {\n    return c1.X == c2.X &amp;&amp; c1.Y == c2.Y &amp;&amp; c1.Z == c2.Z;\n  }\n};\n\nstd::hash_map&lt;Coor, bool, hash&lt;Coor&gt;, coords_thesame&gt; m_SeenCoordinates;\n</code></pre>\n\n<p>Untested, use at your own peril :)</p>\n'}, {'answer_id': 72374, 'author': 'finnw', 'author_id': 12048, 'author_profile': 'https://Stackoverflow.com/users/12048', 'pm_score': 2, 'selected': False, 'text': '<p>Assuming you already have a Coordinate class, add a hash function and maintain a hash_set of the coordinates.\nWould look something like:</p>\n\n<pre><code>struct coord_eq\n{\n  bool operator()(const Coordinate &amp;s1, const Coordinate &amp;s2) const\n  {\n    return s1 == s2;\n    // or: return s1.x() == s2.x() &amp;&amp; s1.y() == s2.y() &amp;&amp; s1.z() == s2.z();\n  }\n};\n\nstruct coord_hash\n{\n  size_t operator()(const Coordinate &amp;s) const\n  {\n     union {double d, unsigned long ul} c[3];\n     c[0].d = s.x();\n     c[1].d = s.y();\n     c[2].d = s.z();\n     return static_cast&lt;size_t&gt; ((3 * c[0].ul) ^ (5 * c[1].ul) ^ (7 * c[2].ul));\n  }\n};\n\nstd::hash_map&lt;Coordinate, coord_hash, coord_eq&gt; existing_coords;\n</code></pre>\n'}, {'answer_id': 72375, 'author': 'Ed.', 'author_id': 12257, 'author_profile': 'https://Stackoverflow.com/users/12257', 'pm_score': 2, 'selected': False, 'text': '<p>Divide your space into discrete bins.  Could be infinitely deep squares, or could be cubes. Store your processed coordinates in a simple linked list, sorted if you like in each bin.  When you get a new coordinate, jump to the enclosing bin, and walk the list looking for the new point. </p>\n\n<p>Be wary of floating point comparisons.  You need to either turn values into integers (say multiply by 1000 and truncate), or decide how close 2 values are to be considered equal.</p>\n'}, {'answer_id': 72382, 'author': 'xtofl', 'author_id': 6610, 'author_profile': 'https://Stackoverflow.com/users/6610', 'pm_score': 0, 'selected': False, 'text': '<p>You can easily define a comparator for a one-level <code>std::map</code>, so that lookup becomes way less cumbersome.  There is no reason of being afraid of that.  The comparator defines an ordering of the _Key template argument of the map.  It can then also be used for the multimap and set collections.</p>\n\n<p>An example:</p>\n\n<pre><code>#include &lt;map&gt;\n#include &lt;cassert&gt;\n\n\nstruct Point {\n  double x, y, z;\n};\n\nstruct PointResult {\n};\n\nPointResult point_function( const Point&amp; p ) { return PointResult(); }\n\n// helper: binary function for comparison of two points\nstruct  point_compare {\n  bool operator()( const Point&amp; p1, const Point&amp; p2 ) const {\n    return p1.x &lt; p2.x\n      || ( p1.x == p2.x &amp;&amp; ( p1.y &lt; p2.y \n      || ( p1.y == p2.y &amp;&amp; p1.z &lt; p2.z ) \n      )\n      );\n  }\n};\n\ntypedef std::map&lt;Point, PointResult, point_compare&gt; pointmap;\n\nint _tmain(int argc, _TCHAR* argv[])\n{\n\npointmap pm;\n\nPoint p1 = { 0.0, 0.0, 0.0 };\nPoint p2 = { 0.1, 1.0, 1.0 };\n\npm[ p1 ] = point_function( p1 );\npm[ p2 ] = point_function( p2 );\nassert( pm.find( p2 ) != pm.end() );\n    return 0;\n}\n</code></pre>\n'}, {'answer_id': 72392, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 1, 'selected': False, 'text': '<p>Use an std::set. Define a type for the 3d coordinate (or use a boost::tuple) that has operator&lt; defined. When adding elements, you can add it to the set, and if it was added, do your processing. If it was not added (because it already exists in there), do not do your processing.</p>\n\n<p>However, if you are using doubles, be aware that your algorithm can potentially lead to unpredictable behavior. IE, is (1.0, 1.0, 1.0) the same as (1.0, 1.0, 1.000000001)?</p>\n'}, {'answer_id': 72566, 'author': 'Adi', 'author_id': 9090, 'author_profile': 'https://Stackoverflow.com/users/9090', 'pm_score': 0, 'selected': False, 'text': '<p>There are more than a few ways to do it, but you have to ask yourself first what are your assumptions and conditions.</p>\n\n<p>So, assuming that your space is limited in size and you know what is the maximum accuracy, then you can form a function that given (x,y,z) will convert them to a unique number or string -this can be done only if you know that your accuracy is limited (for example - no two entities can occupy the same cubic centimeter).\nEncoding the coordinate allows you to use a single map/hash with O(1).</p>\n\n<p>If this is not tha case, you can always use 3 embedded maps as you suggested, or go towards space division algorithms (such as OcTree as mentioned) which although given O(logN) on a average search, they also give you additional information you might want (neighbors, population, etc..), but of course it is harder to implement.</p>\n'}, {'answer_id': 72567, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 2, 'selected': False, 'text': '<p>You can easily use a set as follows:</p>\n\n<pre><code>#include &lt;set&gt;\n#include &lt;cassert&gt;\n\nconst double epsilon(1e-8);\n\nclass Coordinate {\npublic:\nCoordinate(double x, double y, double z) :\n  x_(x), y_(y), z_(z) {}\n\nprivate:\ndouble x_;\ndouble y_;\ndouble z_;\n\nfriend bool operator&lt;(const Coordinate&amp; cl, const Coordinate&amp; cr);\n};\n\nbool operator&lt;(const Coordinate&amp; cl, const Coordinate&amp; cr) {\n  if (cl.x_ &lt; cr.x_ - epsilon) return true;\n  if (cl.x_ &gt; cr.x_ + epsilon) return false;\n\n  if (cl.y_ &lt; cr.y_ - epsilon) return true;\n  if (cl.y_ &gt; cr.y_ + epsilon) return false;\n\n  if (cl.z_ &lt; cr.z_ - epsilon) return true;\n\n  return false;\n\n}\n\ntypedef std::set&lt;Coordinate&gt; Coordinates;\n\n// Not thread safe!\n// Return true if real processing is done\nbool Process(const Coordinate&amp; coordinate) {\n  static Coordinates usedCoordinates;\n\n  // Already processed?\n  if (usedCoordinates.find(coordinate) != usedCoordinates.end()) {\n    return false;\n  }\n\n  usedCoordinates.insert(coordinate);\n\n  // Here goes your processing code\n\n\n\n  return true;\n\n}\n\n// Test it\nint main() {\n  assert(Process(Coordinate(1, 2, 3)));\n  assert(Process(Coordinate(1, 3, 3)));\n  assert(!Process(Coordinate(1, 3, 3)));\n  assert(!Process(Coordinate(1+epsilon/2, 2, 3)));\n}\n</code></pre>\n'}, {'answer_id': 72600, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': "<p>You can either use a <code>std::set</code> of 3D coordinates, or a sorted <code>std::vector</code>. Both will give you logarithmic time lookup. In either case, you'll need to implement the less than comparison operator for your 3D coordinate class.</p>\n"}, {'answer_id': 75284, 'author': 'hyperlogic', 'author_id': 1841, 'author_profile': 'https://Stackoverflow.com/users/1841', 'pm_score': 0, 'selected': False, 'text': '<p>Why bother?  What "processing" are you doing?  Unless it\'s very complex, it\'s probably faster to just do the calculation again, rather then waste time looking things up in a huge map or hashtable.</p>\n\n<p>This is one of the more counter-intuitive things about modern cpu\'s.  Computation is fast, memory is slow.</p>\n\n<p>I realize this isn\'t really an answer to your question, it\'s questioning your question.</p>\n'}, {'answer_id': 78219, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>Good question... it\'s one that has many solutions, because this type of problem comes \nup many times in Graphical and Scientific applications.</p>\n\n<p>Depending on the solution you require it may be rather complex under the hood, in this \ncase less code doesn\'t necessarily mean faster.</p>\n\n<p><em>"but this makes it quite tedious to use"</em> --- generally, you can get around this by \ntypedefs or wrapper classes (wrappers in this case would be highly recommended).</p>\n\n<p>If you don\'t need to use the 3D co-ordinates in any kind of spacially significant way ( \nthings like "give me all the points within X distance of point P") then I suggest you \njust find a way to hash each point, and use a single hash map... O(n) creation, O(1) \naccess (checking to see if it\'s been processed), you can\'t do much better than that.</p>\n\n<p>If you do need more spacial information you\'ll need a container that explicitly takes \nit into account. \nThe type of container you choose will be dependant on your data set. If you have good \nknowledge of the range of values that you recieve this will help.</p>\n\n<p>If you are recieving well distributed data over a known range... go with <a href="http://en.wikipedia.org/wiki/Octree" rel="nofollow noreferrer">octree</a>. </p>\n\n<p>If you have a distribution that tends to cluster, then go with <a href="http://en.wikipedia.org/wiki/Kd_tree" rel="nofollow noreferrer">k-d trees</a>. You\'ll need \nto rebuild a k-d tree after inputting new co-ordinates (not necessarily every time, \njust when it becomes overly imbalanced). Put simply, Kd-trees are like Octrees, but with non uniform division.</p>\n'}]
['https://Stackoverflow.com/questions/72128', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/2796/']