c++ - 优化/简化许多点靠在一起的路径？

Question

我有一条代表多边形轮廓的点路径。路径由像素构成。

这意味着所有点都非常非常接近，但我确保它们都是唯一的。

现在我正在检查 3 个点是否共线，如果是，我删除中间的一个。

我使用点积检查它们是否共线。然而，我观察到我的许多点积都是 0.0f。有什么问题吗？

void ImagePolygon::computeOptimized()
{
    m_optimized = m_hull;

    m_optimized.erase(
        std::unique(m_optimized.begin(),
        m_optimized.end()),
        m_optimized.end());

    int first = 0;
    int second = 1;

    std::vector<int> removeList;

     for(int i = 2; i < m_optimized.size(); ++i)
        {
            second = i - 1;
            first = i - 2;

            if(isColinear(m_optimized[i - 2],m_optimized[i - 1],m_optimized[i]))
            {
                m_optimized.erase(m_optimized.begin() + i - 1);
            removeList.push_back(i - 1);
            }
        }

     std::sort(removeList.rbegin(),removeList.rend());
     for(int i = 0; i < removeList.size(); ++i)
     {
        m_optimized.erase(m_optimized.begin() + removeList[i]);
     }

}

bool ImagePolygon::isColinear( const b2Vec2& a, const b2Vec2& b, const b2Vec2& c ) const
{
    b2Vec2 vec1 = b2Vec2(b.x - a.x, b.y - a.y);
    vec1.Normalize();
    b2Vec2 vec2 = b2Vec2(c.x - b.x, c.y - b.y);
    vec2.Normalize();

    float dotProduct = vec1.x * vec2.x + vec1.y * vec2.y;

    //test value
    return abs(dotProduct) > 0.00001f;
}

主要问题是我在不应该得到很多 0 点积时得到了很多，因此无论我在哪里设置阈值，路径都没有得到应有的优化。

谢谢

float32 Normalize()
{
    float32 length = Length();
    if (length < b2_epsilon)
    {
        return 0.0f;
    }
    float32 invLength = 1.0f / length;
    x *= invLength;
    y *= invLength;

    return length;
}

Answer 1

您需要 2x2 行列式 vec1.x * vec2.y - vec1.y * vec2.x 而不是点积。当且仅当这些点共线时，行列式为零，而当且仅当这些点形成直角时，点积为零。