如何为相同多边形生成可区分翻转/旋转的唯一标识ID？

针对你遇到的归一化多边形哈希碰撞问题（旋转/翻转后得到相同ID），可以用以下几种简单且鲁棒的方案：

1. 基于有序坐标序列的迭代哈希 #

利用归一化后坐标的顺序性，用迭代式哈希算法处理整个坐标序列，能有效区分旋转、翻转后的不同多边形。推荐使用FNV-1a算法，实现简单且碰撞概率极低：

#include <vector>
#include <cstdint>

uint64_t polygon_hash(const std::vector<std::pair<int32_t, int32_t>>& normalized_coords) {
    const uint64_t FNV_OFFSET = 14695981039346656037ULL;
    const uint64_t FNV_PRIME = 1099511628211ULL;
    
    uint64_t hash_val = FNV_OFFSET;
    for (const auto& [x, y] : normalized_coords) {
        // 将32位x、y拼接为64位坐标值
        uint64_t coord_val = (static_cast<uint64_t>(x) << 32) | static_cast<uint32_t>(y);
        // FNV-1a核心操作：异或后乘质数
        hash_val ^= coord_val;
        hash_val *= FNV_PRIME;
    }
    return hash_val;
}

该算法会按顺序处理每个坐标，旋转或翻转后的坐标序列（值或顺序变化）会生成完全不同的哈希值，彻底解决你之前的碰撞问题。

2. 多特征组合哈希 #

如果需要更直观的特征可追溯性，可以提取多边形的多个唯一特征，组合后计算哈希：

• 提取归一化坐标的统计特征：x的最大/最小值、y的最大/最小值、x/y坐标总和
• 提取相邻坐标的差值序列（包括最后一个点到第一个点的闭环差值），对差值序列单独计算哈希
• 将所有特征打包为结构体，再对结构体计算哈希：

#include <vector>
#include <cstdint>
#include <algorithm>

struct PolySignature {
    int32_t min_x, max_x;
    int32_t min_y, max_y;
    int64_t sum_x, sum_y;
    uint64_t delta_hash;
};

uint64_t compute_delta_hash(const std::vector<std::pair<int32_t, int32_t>>& coords) {
    const uint64_t FNV_OFFSET = 14695981039346656037ULL;
    const uint64_t FNV_PRIME = 1099511628211ULL;
    uint64_t hash = FNV_OFFSET;
    size_t n = coords.size();
    for (size_t i = 0; i < n; ++i) {
        auto [x1, y1] = coords[i];
        auto [x2, y2] = coords[(i+1)%n];
        int32_t dx = x2 - x1;
        int32_t dy = y2 - y1;
        uint64_t delta_val = (static_cast<uint64_t>(dx) << 32) | static_cast<uint32_t>(dy);
        hash ^= delta_val;
        hash *= FNV_PRIME;
    }
    return hash;
}

PolySignature generate_signature(const std::vector<std::pair<int32_t, int32_t>>& normalized_coords) {
    PolySignature sig{};
    sig.sum_x = 0;
    sig.sum_y = 0;
    sig.min_x = normalized_coords[0].first;
    sig.max_x = normalized_coords[0].first;
    sig.min_y = normalized_coords[0].second;
    sig.max_y = normalized_coords[0].second;
    
    for (const auto& [x, y] : normalized_coords) {
        sig.sum_x += x;
        sig.sum_y += y;
        sig.min_x = std::min(sig.min_x, x);
        sig.max_x = std::max(sig.max_x, x);
        sig.min_y = std::min(sig.min_y, y);
        sig.max_y = std::max(sig.max_y, y);
    }
    sig.delta_hash = compute_delta_hash(normalized_coords);
    return sig;
}

// 自定义结构体哈希函数，用于unordered_map
namespace std {
    template<> struct hash<PolySignature> {
        size_t operator()(const PolySignature& s) const {
            size_t h1 = hash<int32_t>{}(s.min_x);
            size_t h2 = hash<int32_t>{}(s.max_x);
            size_t h3 = hash<int32_t>{}(s.min_y);
            size_t h4 = hash<int32_t>{}(s.max_y);
            size_t h5 = hash<int64_t>{}(s.sum_x);
            size_t h6 = hash<int64_t>{}(s.sum_y);
            size_t h7 = hash<uint64_t>{}(s.delta_hash);
            // 组合多个哈希值
            return h1 ^ (h2 << 1) ^ (h3 << 2) ^ (h4 << 3) ^ (h5 << 4) ^ (h6 << 5) ^ (h7 << 6);
        }
    };
}

这种方案通过多维度特征组合，进一步降低碰撞概率，同时特征本身可用于后续的多边形属性分析。

注意事项 #

• 如果你需要区分多边形的顶点顺序（顺时针/逆时针），上述方案直接可用；如果不需要，需先统一顶点顺序（比如通过计算多边形面积的符号，将所有多边形调整为顺时针顺序），再计算哈希。
• 所有方案都基于归一化后的坐标（已消除起始点偏移），确保同一形状不同位置的多边形能被归为同一组。

内容的提问来源于stack exchange，提问作者keith969