Hashing Epeck::Point_3

[unageek]

I want to make a hash map of type unordered_map<K::Point_3, std::size_t, Point_hash>, where K is CGAL::Exact_predicates_exact_constructions_kernel. The points inserted as keys are obtained with CGAL::intersection, etc. Is this the right way to hash the points? I mean, do CGAL::to_double(p.x()), etc. give consistent results?

  struct Point_hash {
    std::size_t operator()(const K::Point_3& p) const noexcept {
      p.exact();  // <---- Refine coordinates before calling CGAL::to_double
      std::size_t seed{};
      boost::hash_combine(seed, std::hash<double>()(CGAL::to_double(p.x())));
      boost::hash_combine(seed, std::hash<double>()(CGAL::to_double(p.y())));
      boost::hash_combine(seed, std::hash<double>()(CGAL::to_double(p.z())));
      return seed;
    }
  };

Does p.exact(); have the same effect as separate calls to p.x().exact(); p.y().exact(); p.z().exact();?

[MaelRL]

Yes, that's a way to ensure consistency. You can have a look at a closely related discussion there: #6000.

Note that these calls to exact() will nullify the "lazy exactness" mechanisms (meaning, delaying exact computations until it is really needed) of EPECK, and it might be slower to use an unordered container within your program in the end.

[unageek]

Thank you so much for answering!

Note that these calls to exact() will nullify the "lazy exactness" mechanisms

Yeah, thank you for pointing this out.

By the way, the overall execution time of my program is much faster with p.exact(); than p.x().exact(); p.y().exact(); p.z().exact();. Do you have any idea?

[unageek]

I have come up with an optimization:

  struct Point_hash {
    std::size_t operator()(const Point& p) const noexcept {
      if (!p.x().approx().is_point() || !p.y().approx().is_point() || !p.z().approx().is_point()) {
        p.exact();
      }
      std::size_t seed{};
      boost::hash_combine(seed, std::hash<double>()(CGAL::to_double(p.x())));
      boost::hash_combine(seed, std::hash<double>()(CGAL::to_double(p.y())));
      boost::hash_combine(seed, std::hash<double>()(CGAL::to_double(p.z())));
      return seed;
    }
  };

(This makes the execution faster because most of the points are directly constructed from doubles.)

Is this safe?

[lrineau]

Yes, it seems safe.

[unageek]

Thank you!

[mglisse]

      if (!p.x().approx().is_point() || !p.y().approx().is_point() || !p.z().approx().is_point()) {

I think p.approx().x().is_point() is cheaper than p.x().approx().is_point().

[unageek]

Wow! You're right! I guess that's because p.approx().x().is_point() does not involve construction of lazy objects?

[unageek]

So here is a more optimized version:

  struct Point_hash {
    std::size_t operator()(const Point& p) const noexcept {
      if (!p.approx().x().is_point() || !p.approx().y().is_point() || !p.approx().z().is_point()) {
        p.exact();
      }
      std::size_t seed{};
      boost::hash_combine(seed, std::hash<double>()(p.approx().x().inf()));
      boost::hash_combine(seed, std::hash<double>()(p.approx().y().inf()));
      boost::hash_combine(seed, std::hash<double>()(p.approx().z().inf()));
      return seed;
    }
  };