通过向量扩展二维多边形

Question

我有凸多边形，我想通过像这样沿着向量投影来扩展它们：

（左侧为原始多边形和矢量，右侧为所需结果。）

我的多边形存储为一系列逆时针缠绕的点。我想要找到的是我需要投影的 "starting" 和 "stopping" 点，如下面带圆圈的顶点所示。

（绿色箭头表示多边形的缠绕，给出每条边的"direction"。）

我最初的计划是通过从每个点投射一条带有矢量方向的射线，并找到射线不与边相交的第一个和最后一个点来确定要使用的点。然而，这似乎很昂贵。

有没有一种方法可以使用边缘方向与矢量方向或类似的技巧来确定从哪些点延伸？

Answer 1

是的，你可以。您想沿 x、y 投影。所以法线是y，-x。现在旋转它（atan2，或者如果你了解旋转矩阵，你可以直接使用它）。要投影的点以及现在的最小值和最大值 x，您还可以通过始终沿轴进行然后旋转回来来加快投影速度。

Answer 2

查看矢量方向落在边方向之间的点。

换句话说，取三个向量：

引出顶点的边
翻译矢量
与通向顶点的边相反

如果它们在逆时针时按此顺序排列，即如果第二个向量介于第一个和第三个向量之间，则这是一个 "inside" 点。

为了确定一个向量是否位于其他两个向量之间，请使用叉积，例如here.

Answer 3

n.m。我提出并想象的问题，但在编程时我很快注意到有一个常见的情况，所有顶点都是 "outside" 个顶点（这在三角形上很容易看到，并且可能发生在其他多边形也是如此）。

文字说明。

我使用的解决方案是查看通往和离开每个顶点的边的法向量。我们要扩展的顶点是至少有一个边缘法线的顶点，与我们扩展的增量向量的最小角度小于 90 度。

逆时针多边形的外向边缘法线可以通过以下方式找到：

normal = (currentVertex.y - nextVertex.y, nextVertex.x - currentVertex.x)

请注意，由于我们不关心确切的角度，因此我们不需要对法线进行归一化（制作单位向量），这样可以节省平方根。

为了将它与 delta 向量进行比较，我们使用点积：

dot = edgeNormal.dot(deltaVector)

如果结果大于零，则最小角为锐角（小于90）。如果结果恰好为零，则向量是垂直的。如果结果小于零，则最小角为钝角。当向量垂直时值得注意，因为它可以让我们避免向扩展多边形添加额外的顶点。

如果你想像我一样可视化角度如何与点积一起工作，只需看一下反余弦图（通常你通过 acos(dot) 获得角度）。

现在我们可以找到边法线和增量向量之间有一个锐角和一个非锐角的最小夹角的顶点。这些顶点 "acute side" 上的所有内容都添加了增量向量，而 "obtuse side" 上的所有内容保持不变。两个边界顶点本身是重复的，一个扩展一个保持不变，除非 "obtuse side" 正好垂直于增量向量（在这种情况下我们只需要扩展顶点，否则我们将在同一条线上有两个顶点）。

这是此解决方案的 C++ 代码。

它可能看起来有点长，但实际上非常简单明了并且有很多评论，因此希望它不难理解。

它是我的多边形 class 的一部分，它有一个 std::vector 逆时针缠绕的顶点。 units::Coordinate 是浮点数，units::Coordinate2D 是矢量 class 我觉得应该是不言自明的。

// Compute the normal of an edge of a polygon with counterclockwise winding, without normalizing it to a unit vector.
inline units::Coordinate2D _get_non_normalized_normal(units::Coordinate2D first, units::Coordinate2D second) {
    return units::Coordinate2D(first.y - second.y, second.x - first.x);
}
enum AngleResult {
    ACUTE,
    PERPENDICULAR,
    OBTUSE
};
// Avoid accumulative floating point errors.
// Choosing a good epsilon is extra important, since we don't normalize our vectors (so it is scale dependent).
const units::Coordinate eps = 0.001;
// Check what kind of angle the minimum angle between two vectors is.
inline AngleResult _check_min_angle(units::Coordinate2D vec1, units::Coordinate2D vec2) {
    const units::Coordinate dot = vec1.dot(vec2);
    if (std::abs(dot) <= eps)
        return PERPENDICULAR;
    if ((dot + eps) > 0)
        return ACUTE;
    return OBTUSE;
}
Polygon Polygon::extend(units::Coordinate2D delta) const {
    if (delta.isZero()) { // Isn't being moved. Just return the current polygon.
        return Polygon(*this);
    }
    const std::size_t numVerts = vertices_.size();
    if (numVerts < 3) {
        std::cerr << "Error: Cannot extend polygon (polygon invalid; must have at least three vertices).\n";
        return Polygon();
    }
    // We are interested in extending from vertices that have at least one edge normal with a minimum angle acute to the delta.
    // With a convex polygon, there will form a single contiguous range of such vertices.
    // The first and last vertex in that range may need to be duplicated, and then the vertices within the range
    // are projected along the delta to form the new polygon.
    // The first and last vertices are defined by the vertices that have only one acute edge normal.

    // Whether the minimum angle of the normal of the edge made from the last and first vertices is acute with delta.
    const AngleResult firstEdge = _check_min_angle(_get_non_normalized_normal(vertices_[numVerts-1], vertices_[0]), delta);
    const bool isFirstEdgeAcute = firstEdge == ACUTE;

    AngleResult prevEdge = firstEdge;
    AngleResult currEdge;
    bool found = false;
    std::size_t vertexInRegion;
    for (std::size_t i = 0; i < numVerts - 1; ++i) {
        currEdge = _check_min_angle(_get_non_normalized_normal(vertices_[i], vertices_[i+1]), delta);
        if (isFirstEdgeAcute != (currEdge == ACUTE)) {
            // Either crossed from inside to outside the region, or vice versa.
            // (One side of the vertex has an edge normal that is acute, the other side obtuse.)
            found = true;
            vertexInRegion = i;
            break;
        }
        prevEdge = currEdge;
    }
    if (!found) {
        // A valid polygon has two points that define where the region starts and ends.
        // If we didn't find one in the loop, the polygon is invalid.
        std::cerr << "Error: Polygon can not be extended (invalid polygon).\n";
        return Polygon();
    }
    found = false;
    std::size_t first, last;
    // If an edge being extended is perpendicular to the delta, there is no need to duplicate that vertex.
    bool shouldDuplicateFirst, shouldDuplicateLast;
    // We found either the first or last vertex for the region.
    if (isFirstEdgeAcute) {
        // It is the last vertex in the region.
        last = vertexInRegion;
        shouldDuplicateLast = currEdge != PERPENDICULAR; // currEdge is either perpendicular or obtuse.
        // Loop backwards from the end to find the first vertex.
        for (std::size_t i = numVerts - 1; i > 0; --i) {
            currEdge = _check_min_angle(_get_non_normalized_normal(vertices_[i-1], vertices_[i]), delta);
            if (currEdge != ACUTE) {
                first = i;
                shouldDuplicateFirst = currEdge != PERPENDICULAR;
                found = true;
                break;
            }
        }
        if (!found) {
            std::cerr << "Error: Polygon can not be extended (invalid polygon).\n";
            return Polygon();
        }
    } else {
        // It is the first vertex in the region.
        first = vertexInRegion;
        shouldDuplicateFirst = prevEdge != PERPENDICULAR; // prevEdge is either perpendicular or obtuse.
        // Loop forwards from the first vertex to find where it ends.
        for (std::size_t i = vertexInRegion + 1; i < numVerts - 1; ++i) {
            currEdge = _check_min_angle(_get_non_normalized_normal(vertices_[i], vertices_[i+1]), delta);
            if (currEdge != ACUTE) {
                last = i;
                shouldDuplicateLast = currEdge != PERPENDICULAR;
                found = true;
                break;
            }
        }
        if (!found) {
            // The edge normal between the last and first vertex is the only non-acute edge normal.
            last = numVerts - 1;
            shouldDuplicateLast = firstEdge != PERPENDICULAR;
        }
    }

    // Create the new polygon.
    std::vector<units::Coordinate2D> newVertices;
    newVertices.reserve(numVerts + (shouldDuplicateFirst ? 1 : 0) + (shouldDuplicateLast ? 1 : 0) );
    for (std::size_t i = 0; i < numVerts; ++i) {
        // Extend vertices in the region first-to-last inclusive. Duplicate first/last vertices if required.
        if (i == first && shouldDuplicateFirst) {
            newVertices.push_back(vertices_[i]);
            newVertices.push_back(vertices_[i] + delta);
        } else if (i == last && shouldDuplicateLast) {
            newVertices.push_back(vertices_[i] + delta);
            newVertices.push_back(vertices_[i]);
        } else {
            newVertices.push_back( isFirstEdgeAcute ? // Determine which range to use.
                ( (i <= last || i >= first) ? vertices_[i] + delta : vertices_[i] ) : // Range overlaps start/end of the array.
                ( (i <= last && i >= first) ? vertices_[i] + delta : vertices_[i] )); // Range is somewhere in the middle of the array.
        }
    }
    return Polygon(newVertices);
}

到目前为止，我用三角形、矩形、近似圆和通过许多不同的增量向量按顺序扩展近似圆而形成的任意凸多边形测试了这段代码。

请注意，此解决方案仍然仅对凸多边形有效。

通过向量扩展二维多边形

Extend 2d polygon by vector

polygon