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

Question

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

我考虑过 A* 搜索类型方法，我会搜索最短路径，遍历位于多边形周长（作为目的地）上的所有点，然后沿着最短路径多段线在设定的距离限制处绘制新点以给出一个新的多边形外壳。

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

我想知道我是否遗漏了一些明显的东西 library/method 明智的，是否有人对我如何实现这一目标有任何其他想法。

给定一个这样的多边形：

我正在创建一个显示内部 space 的多边形（不包括内门），如下所示：

这是我的问题所指的部分。我想从多边形边界上的给定点找到多边形内的所有可到达点（以红色显示为新多边形），从该点（下面用红色方块捐赠）设置的最大行程距离如下：

Answer 1

对多边形进行三角测量。
- 如果您选择的原点不是多边形顶点（即它是多边形内的一个点），请将此点作为steiner 点 在三角剖分中。
从三角剖分的顶点和约束边构建一个无向加权图（其中图边权重是三角剖分边的长度）。
- 约束边是不在多边形之外的边。
计算从你的原始顶点到图中所有其他顶点的最短路径（使用Dijkstra或Bellman- Ford 算法）。从原点到顶点的路径距离是该顶点的 Z 值。
Update/create 另一个三角剖分网格，使用与之前计算的 Z 值相同的顶点。
通过内插 within/between 个三角形（根据每个三角形的顶点的 Z 值进行内插）计算每个像素的距离值。这很容易通过使用 barycentric coordinates 来完成。坐标的插值输出为您提供从原点位置到该坐标的距离。

对于下面的插图，我使用了 TinFour Java 库中的 NaturalNeighborInterpolator。它通过对三角剖分进行操作简化了插值步骤——我只是在每个像素坐标处调用插值器，最后用原始多边形屏蔽输出（因为它有效地计算了多边形的凸包）。

示例代码

图形和 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。如果等值线穿过三角形（如下图所示），它将与三角形的两条边相交——为每个这样的三角形在每对相交点之间绘制一条线段给你一个距离边界。

为三角剖分中的每个 constrained 三角形的每条边调用一个方法（如下所示）。如果距离等值线穿过三角形，您将得到该三角形的两个交点；否则 none.

/**
 * 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;
}

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

Find area within set distance from point in a complicated polygon

javascript

algorithm

math

geometry

polygon

示例代码

更新：距离边界顶点