javascript - 查找距复杂多边形中的点设定距离内的区域

Question

给定一个简单(不相交)的多边形，例如平面图(房间之间的门缺失，以便给出 1 个简单的不间断边界)。如何找到从 (x, y) 点(在多边形边界内或边界上)可到达的多边形内的所有区域？理想情况下，我希望返回一个多边形，然后可以将其叠加以显示所有可到达的区域。

我考虑过 A* 搜索类型方法，其中我将搜索最短路径，迭代位于多边形周界(作为目的地)上的所有点，然后沿最短路径折线在设定距离限制处绘制新点以给出新的多边形外壳。

我也考虑过波传播作为一种方法。

我想知道我是否在库/方法方面遗漏了一些明显的东西，以及是否有人对我如何实现这一目标有任何其他想法。

给定一个像这样的多边形:

我正在创建一个显示内部空间(不包括内门)的多边形，如下所示:

这就是我的问题所指的部分。我想从多边形边界上的给定点找到多边形内所有可到达的点(以红色显示为新多边形)，距该点设定的最大行进距离(在下面用红色方 block 表示)，如下所示:

Answer 1

1. 对多边形进行三 Angular 测量。
   • 如果您选择的原始顶点不是多边形顶点(即，它是多边形内的点)，请将此点作为steiner点包含在三 Angular 剖分中。
2. 根据三 Angular 剖分的顶点和受约束边构建无向加权图(其中图形边权重是三 Angular 剖分边的长度)。
   • 受约束的边是指不位于多边形外部的边。
3. 计算从原始顶点到图中所有其他顶点的最短路径(使用Dijkstra或Bellman-Ford算法)。从原点到顶点的路径距离是该顶点的 Z 值。
4. 使用相同的顶点以及之前计算的 Z 值来更新/创建另一个三 Angular 剖分网格。
5. 通过在三 Angular 形内/之间进行插值(根据每个三 Angular 形顶点的 Z 值进行插值)来计算每个像素的距离值。这可以通过使用 barycentric coordinates 轻松完成。 。坐标的插值输出给出从原点位置到该坐标的距离。

对于下面的插图，我使用了 NaturalNeighborInterpolator来自 TinFour Java 库。它通过对三 Angular 测量进行操作来简化插值步骤 - 我只需在每个像素坐标处调用插值器，最后用原始多边形掩盖输出(因为它有效地计算多边形的凸包)。

示例代码

图表和 Dijkstra 实现使用 JGraphT 库。

IncrementalTin tin = new IncrementalTin();
tin.add(listOfPolygonVertices); // triangulates upon insertion

Graph<Vertex, IQuadEdge> graph = new DefaultUndirectedWeightedGraph<>(IQuadEdge.class);

tin.edges().forEach(e -> {
    if (e.isConstrainedRegionInterior() || e.isConstrainedRegionBorder()) {
        graph.addVertex(e.getA());
        graph.addVertex(e.getB());
        graph.addEdge(e.getA(), e.getB(), e);
        graph.setEdgeWeight(e.getA(), e.getB(), e.getLength());
    }
});

DijkstraShortestPath<Vertex, IQuadEdge> shortestPaths = new DijkstraShortestPath<>(graph);
Vertex originVertex = tin.getNavigator().getNearestVertex(originX, originY);

var paths = shortestPaths.getPaths(originVertex);

IncrementalTin distanceMesh = new IncrementalTin();
for (Vertex v : graph.vertexSet()) {
    var d = paths.getWeight(v);
    distanceMesh.add(new Vertex(v.x, v.y, d)); // add vertices with Z to new tin
}

IInterpolatorOverTin interpolator = new NaturalNeighborInterpolator(distanceMesh);

for (int x = 0; x < width; x++) {
    for (int y = 0; y < height; y++) {
        double z = interpolator.interpolate(x, y, null);
        if (!Double.isNaN(z)) {
            pixels[y * width + x] = someColour;
        }
    }
}

更新:距离边界顶点

如果您只想要距离边界线，则可以放弃第 5 步。而是计算(如果适用)isoline对于每个三 Angular 形，基于所需的距离。如果等值线穿过三 Angular 形(如下图所示)，它将与三 Angular 形的两条边相交 - 在每个此类三 Angular 形的每对相交点之间绘制一条线段，即可给出距离边界。

为三 Angular 剖分中每个受约束三 Angular 形的每条边调用一个方法(如下所示)。如果距离等值线穿过三 Angular 形，您将得到该三 Angular 形的两个交点；否则没有。

/**
 * Compute isoline vertex (if applicable) for a triangle side given by two vertices
 */
Vertex isoVertex(Vertex a, Vertex b, double d) {
    Vertex min, max;

    if (a.getZ() > b.getZ()) {
        max = a;
        min = b;
    } else {
        max = b;
        min = a;
    }

    if (d > min.getZ() && d < max.getZ()) {
        double diff = max.getZ() - min.getZ();
        double numerator = d - min.getZ();

        double fract = numerator / diff;
        double xDiff = max.getX() - min.getX();
        double yDiff = max.getY() - min.getY();
        
        return new Vertex(min.getX() + fract * xDiff, min.getY() + fract * yDiff);
    }
    return null;
}