C++ Class Design: 2D Point with Coordinates and Hashing

Worked Solution

How to Think About It

There are two distinct challenges here. The first -- coordinate conversion between Cartesian $(x,y)$ and polar $(r,\theta)$ -- is just trigonometry. The second -- making Point2D usable as a key in STL containers -- tests whether you know what each container actually requires under the hood:

- std::set is a balanced BST. It needs a strict weak ordering, supplied via operator< (or a comparator). Equivalence is defined *implicitly* by !(a<b) && !(b<a). - std::unordered_set is a hash table. It needs an equality relation (operator==) that is a genuine *equivalence relation* (reflexive, symmetric, transitive) AND a hash functor satisfying the contract $$a == b \;\Longrightarrow\; \text{hash}(a) = \text{hash}(b).$$

The trap is floating point. A tempting design uses *epsilon* equality, |x_a - x_b| < \varepsilon. This is not an equivalence relation -- it fails transitivity ($a\approx b$ and $b\approx c$ does not give $a\approx c$) -- so it is illegal for unordered_set. Worse, even if you tolerated that, a separate "round to a grid" hash is *inconsistent* with epsilon equality: two points within $\varepsilon$ can straddle a grid boundary and hash differently, breaking the contract. The cure is to make equality and the hash share one canonical representation.

Quick Estimate

Before writing code, sanity-check the requirements list: conversion = $O(1)$ trig; set needs 1 operator (<); unordered_set needs 2 things (== + hash). The only real design decision is *how to canonicalize* coordinates so that equality and hashing agree exactly. Expect the answer to hinge on quantizing each coordinate to an integer bin and defining both == and hash on those integer bins.

Approach

1. Storage. Store Cartesian $(x,y)$ internally. It avoids the branch-cut/wraparound issues of $\theta$ and is numerically stable. Provide getters/setters for *both* forms, converting on demand. 2. Conversion. Polar -> Cartesian: $x = r\cos\theta,\; y = r\sin\theta$. Cartesian -> polar: $r=\sqrt{x^2+y^2},\; \theta=\operatorname{atan2}(y,x)$ (use atan2, not atan(y/x), for correct quadrant and $x=0$ handling). 3. std::set. Provide operator< as lexicographic comparison on the raw doubles $(x,y)$. Exact < on doubles *is* a valid strict weak ordering (assuming no NaNs), so this is correct as-is -- two bit-distinct points are simply distinct elements. 4. std::unordered_set -- the fix. Do not use epsilon ==. Instead pick a quantization step $q$ (the tolerance you want) and map each coordinate to a canonical integer bin $b(v)=\lfloor v/q \rceil$ (rounded to nearest long long). Then: - operator== returns true iff the two points have identical integer bins $(b_x,b_y)$. - the hash is computed from those same bins $(b_x,b_y)$. Because equality now means "same bins," the contract $a==b\Rightarrow\text{hash}(a)=\text{hash}(b)$ holds by construction, and == is a true equivalence relation (it is equality of a derived discrete key, hence transitive). The residual caveat -- two points just $q/2$ apart on opposite sides of a bin edge are treated as distinct -- is *inherent* to any consistent discrete scheme and is acceptable; what matters is that equality and hashing never disagree.

Formal Solution

```cpp #include <cmath> #include <cstdint> #include <functional> #include <set> #include <unordered_set> #include <utility>

class Point2D { public: // --- canonical quantization step shared by == and hash --- static constexpr double QUANT = 1e-9; // tolerance / grid size

Point2D(double x = 0.0, double y = 0.0) : x_(x), y_(y) {}

// Factory from polar coordinates static Point2D fromPolar(double r, double theta) { return Point2D(r * std::cos(theta), r * std::sin(theta)); }

// ---- Cartesian getters / setters ---- double x() const { return x_; } double y() const { return y_; } void setX(double x) { x_ = x; } void setY(double y) { y_ = y; } void setCartesian(double x, double y) { x_ = x; y_ = y; }

// ---- Polar getters / setters ---- double r() const { return std::sqrt(x_ * x_ + y_ * y_); } double theta() const { return std::atan2(y_, x_); } // (-pi, pi] std::pair<double, double> toPolar() const { return {r(), theta()}; } void setPolar(double r, double theta) { x_ = r * std::cos(theta); y_ = r * std::sin(theta); }

// ---- canonical integer bin for one coordinate ---- static long long bin(double v) { return static_cast<long long>(std::llround(v / QUANT)); }

// operator< for std::set: lexicographic on raw doubles -> valid // strict weak ordering (no NaNs). Two bit-distinct points are distinct. bool operator<(const Point2D& o) const { if (x_ != o.x_) return x_ < o.x_; return y_ < o.y_; }

// operator== for std::unordered_set: equality of CANONICAL BINS. // This is a genuine equivalence relation (transitive) and is // exactly consistent with the hash below. bool operator==(const Point2D& o) const { return bin(x_) == bin(o.x_) && bin(y_) == bin(o.y_); }

private: double x_, y_; };

// Hash functor: hashes the SAME bins that operator== compares, // so a == b => hash(a) == hash(b) holds by construction. struct Point2DHash { std::size_t operator()(const Point2D& p) const { std::size_t h1 = std::hash<long long>{}(Point2D::bin(p.x())); std::size_t h2 = std::hash<long long>{}(Point2D::bin(p.y())); // boost-style combine h1 ^= h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2); return h1; } };

// Usage: // std::set<Point2D> ordered; // uses operator< // std::unordered_set<Point2D, Point2DHash> hashed; // uses operator== + hash ```

Why the fix is correct. With bins defined by llround(v / QUANT), operator== reduces to equality of the pair of long long keys $(b_x,b_y)$, which is reflexive, symmetric, and transitive -- a legitimate equivalence relation. The hash is a pure function of that *same* pair, so equal keys necessarily produce equal hashes. The original design's two bugs are both eliminated: there is no non-transitive epsilon test, and equality/hash can never straddle a boundary inconsistently because they read the identical bin.

Subtleties. - *Two notions of equality.* set distinguishes points by exact <, while unordered_set distinguishes them by quantized bins -- these are deliberately different. If you need them to agree, give set a comparator that orders on the same bins ($\langle b_x,b_y\rangle$ lexicographically) instead of raw doubles. - *Bin-edge effect.* Points $q/2$ apart on opposite sides of a bin boundary are treated as distinct. This is unavoidable for *any* consistent discrete equality and is the right trade-off; do not paper over it with epsilon comparisons. - *NaN / signed zero.* operator< assumes no NaN coordinates (NaN breaks strict weak ordering). -0.0 and +0.0 map to the same bin $0$, which is usually desired.

Complexity. All conversions and the hash are $O(1)$. std::set insert/lookup is $O(\log n)$; std::unordered_set insert/lookup is amortized $O(1)$.

Answer

Store coordinates in Cartesian form with getters/setters for both Cartesian and polar (convert via $r\cos\theta,\,r\sin\theta$ and $\sqrt{x^2+y^2},\,\operatorname{atan2}(y,x)$). For std::set, provide operator< giving a strict weak ordering (lexicographic on the doubles). For std::unordered_set, provide both an equality relation and a hash that are *exactly* consistent: quantize each coordinate to a canonical integer bin $\lfloor v/q\rceil$, define operator== as equality of those bins, and compute the hash from the same bins. Do not use $\varepsilon$-based equality -- it is not transitive (so not a valid equivalence relation) and is inconsistent with a rounded hash, since two points within $\varepsilon$ can fall in different bins and hash differently, violating the $a==b\Rightarrow\text{hash}(a)=\text{hash}(b)$ contract.