Find area within set distance from point in a complicated polygon

user_2365711 0
Viewed 330

Given a simple (non intersecting) polygon such as a floor plan (with doors between rooms missing so as to give 1 simple uninterrupted boundary). How can I find all areas within the polygon reachable from a (x, y) point (within or on the boundary of the polygon)? I’d ideally like from this to return a polygon which could be then overlaid to show all reachable areas.

I’ve considered A* search type methods where I would search the shortest path iterating over all points located on the polygon perimeter (as destination) then plotting new points at the set distance limit along the shortest path polyline to give a new polygon hull.

I’ve also thought about wave propagation as a method.

I’m wondering if I’m missing something obvious here library/method wise and if anyone has any other ideas of how I might achieve this.

Given a polygon like this:

enter image description here

I am creating a polygon showing internal space (excluding internal doors) like this:

enter image description here

This is the part my question refers to. I would like to find all reachable points within the polygon (shown in red as a new polygon) from a given point on the polygon boundary at a set maximum travel distance from that point (donated below with a red square) like this:

enter image description here

polygon math geometry algorithm javascript
1 Answers
  1. Triangulate the polygon.
    • If your chosen origin vertex is not a polygon vertex (i.e. it's a point within the polygon), include this point as a steiner point in the triangulation.
  2. Build an undirected weighted graph from the triangulation's vertices and constrained edges (where graph edge weights are triangulation edge lengths).
    • Constrained edges are edges that do not lie outside the polygon.
  3. Compute shortest paths from your origin vertex to all other vertices in the graph (using Dijkstra or Bellman-Ford algorithm). The path distance from the origin to a vertex is that vertex's Z value.
  4. Update/create another triangulation mesh, using the same vertices with the Z values calculated from before.
  5. Calculate distance values for every pixel by interpolating within/between triangles (interpolating based on each triangle's vertices' Z values). This is readily done by using barycentric coordinates. The interpolation output for a coordinate gives you the distance from the origin position to that coordinate.

For the illustrations below I used the NaturalNeighborInterpolator from the TinFour Java library. It eases the interpolation step by operating on a triangulation — I simply call the interpolator at each pixel coordinate and finally mask the output with the original polygon (since it effectively computes over the convex hull of the polygon).

enter image description here

enter image description here

Illustrative Code

The graph and Dijkstra implementation use the JGraphT library.

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

Update: Distance Boundary Vertices

If you want merely the distance boundary line, you can forgo step 5. Instead, compute (if applicable) the isoline for each triangle, based on the desired distance. If an isoline crosses a triangle (as in the illustration below), it will intersect with two of the triangle's edges — plotting a line segment between each pair of intersecting points for every such triangle give you a distance boundary.

enter image description here

Call a method (such as below) for each edge for every constrained triangle in the triangulation. If the distance isoline crosses the triangle, you'll get two points of intersection for that triangle; otherwise 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;
}

enter image description here

user_98087920
Related