在JGrapht中计算DijkstraShortestPath时出错

Question

我正在编写一个谷歌云函数，以返回多边形中距离多边形内给定源顶点的边界。我收到一条错误消息，上面写着：

java.lang.IollegalArgumentException：图必须包含源顶点！网址：org.jgrapht.alg.shortestpath.DijkstraShortestPath.getPaths(DijkstraShortestPath.java:154(.

上述错误发生在以下代码中的以下行：

var paths = shortestPaths.getPaths(originVertex);

我的代码从定义多边形、距离和原点顶点的HTTP请求中接收JSON。

测试HTTP请求JSON为：

{"polygon": [[30.0, 100.0], [50.0, 200.0], [220.0, 240.0], [440.0, 240.0], [430.0, 40.0], [230.0, 30.0], [85.0, 40.0]], "holes": [], "distance": 30, "origin": [50.0, 200.0]}

代码为：

package com.example;
import com.google.cloud.functions.HttpFunction;
import com.google.cloud.functions.HttpRequest;
import com.google.cloud.functions.HttpResponse;
import com.google.gson.Gson;
import com.google.gson.JsonElement;
import com.google.gson.JsonObject;
import com.google.gson.JsonArray;
import com.google.gson.JsonParseException;
import java.io.BufferedWriter;
import java.io.PrintWriter;
import java.util.logging.Logger;
import java.util.ArrayList;
import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.traverse.*;
import org.jgrapht.alg.shortestpath.*;
import org.tinfour.common.IIncrementalTin;
import org.tinfour.common.IQuadEdge;
import org.tinfour.common.Vertex;
import org.tinfour.standard.IncrementalTin;
import org.tinfour.interpolation.NaturalNeighborInterpolator;
import org.tinfour.interpolation.IInterpolatorOverTin;

public class Example implements HttpFunction {
Gson gson = new Gson();
Logger logger = Logger.getLogger(Example.class.getName());
@Override
public void service(HttpRequest request, HttpResponse response) throws Exception {
ArrayList<Vertex> polygon = new ArrayList<>();
ArrayList<Vertex> holes = new ArrayList<>();
double distance = 0;
double greatestX = 0;
double greatestY = 0;
// ArrayList<double> origin = new ArrayList<>();
double[] origin = {0, 0};
// Parse JSON request and check for "name" field
try {
JsonElement requestParsed = gson.fromJson(request.getReader(), JsonElement.class);
JsonObject requestJson = null;
if (requestParsed != null && requestParsed.isJsonObject()) {
requestJson = requestParsed.getAsJsonObject();
}
if (requestJson != null && requestJson.has("polygon")) {
JsonArray polygonJA = requestJson.get("polygon").getAsJsonArray();
for (JsonElement element : polygonJA) {
JsonArray point = element.getAsJsonArray();
double x = point.get(0).getAsDouble();
double y = point.get(1).getAsDouble();
double z = Double.NaN;
if (x > greatestX) {
greatestX = x;
}
if (y > greatestY) {
greatestY = y;
}
polygon.add(new Vertex(x, y, z));
}
}
if (requestJson != null && requestJson.has("holes")) {
JsonArray holesJA = requestJson.get("holes").getAsJsonArray();
for (JsonElement element : holesJA) {
JsonArray point = element.getAsJsonArray();
double x = point.get(0).getAsDouble();
double y = point.get(1).getAsDouble();
double z = Double.NaN;
holes.add(new Vertex(x, y, z));
}
}
if (requestJson != null && requestJson.has("distance")) {
distance = requestJson.get("distance").getAsDouble();
}
if (requestJson != null && requestJson.has("origin")) {
JsonArray distanceJA = requestJson.get("origin").getAsJsonArray();
double x = distanceJA.get(0).getAsDouble();
double y = distanceJA.get(1).getAsDouble();
origin[0] = x;
origin[1] = y;
logger.severe("x is: " + origin[0]);
logger.severe("y is: " + origin[1]);
}
} catch (JsonParseException e) {
logger.severe("Error parsing JSON: " + e.getMessage());
}
IncrementalTin tin = new IncrementalTin();
tin.add(polygon, null); // 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(origin[0], origin[1]);
logger.severe(graph.toString());
logger.severe(originVertex.toString());
logger.severe(polygon.toString());
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);
JsonObject json = new JsonObject();
JsonArray array = new JsonArray();

for (double x = 0; x < greatestX; x++) {
for (double y = 0; y < greatestY; y++) {
double z = interpolator.interpolate(x, y, null);
if (!Double.isNaN(z)) {
JsonObject item = new JsonObject();
item.addProperty("x", x);
item.addProperty("y", y);
array.add(item);
// pixels[y * greatestX + x] = someColour;
}
}
}
json.add("pixels", array);
var writer = new PrintWriter(response.getWriter());
writer.printf(json.toString());
// BufferedWriter writer = response.getWriter();
// writer.write("Hello world!");
}
}

pom.xml是：

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>cloudfunctions</groupId>
<artifactId>http-function</artifactId>
<version>1.0-SNAPSHOT</version>

<properties>
<maven.compiler.target>11</maven.compiler.target>
<maven.compiler.source>11</maven.compiler.source>
</properties>
<dependencyManagement>
<dependencies>
<dependency>
<groupId>org.tinfour</groupId>
<artifactId>Tinfour</artifactId>
<version>2.1.5</version>
<scope>import</scope>
<type>pom</type>
</dependency>   
</dependencies>
</dependencyManagement>
<dependencies>
<dependency>
<groupId>com.google.cloud.functions</groupId>
<artifactId>functions-framework-api</artifactId>
<version>1.0.1</version>
</dependency>
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-core</artifactId>
<version>1.5.1</version>
</dependency>
<dependency>
<groupId>org.tinfour</groupId>
<artifactId>TinfourCore</artifactId>
<version>2.1.5</version>
<scope>provided</scope>
</dependency>  
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-ext</artifactId>
<version>1.5.1</version>
</dependency>
<dependency>
<groupId>com.google.code.gson</groupId>
<artifactId>gson</artifactId>
<version>2.8.6</version>
</dependency>
</dependencies>
<!-- Required for Java 11 functions in the inline editor -->
<build>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-compiler-plugin</artifactId>
<version>3.8.1</version>
<configuration>
<excludes>
<exclude>.google/</exclude>
</excludes>
</configuration>
</plugin>
</plugins>
</build>
</project>

Answer 1

由于originVertex未包含在graph中，因此发生错误。

tin.getNavigator().getNearestVertex()返回一个未包含在图中的顶点，因为它没有考虑顶点是否受到约束。它返回最近的全局顶点，该顶点恰好是不受约束的(因此尚未插入到图中(。

您有两个选项可以避免该错误。

1. 在调用代码的其余部分之前，请检查图形是否包含顶点(但是，只有当给定的原点位置在受约束区域内(或非常接近(时才会执行(：

if (graph.containsVertex(originVertex)) {
var paths = shortestPaths.getPaths(originVertex);
....
}

2. 始终查找最近的受约束顶点；在这种情况下，您不能使用tin.getNavigator().getNearestVertex()。相反，对图的顶点进行迭代，以找到最接近给定原点位置的顶点，或者将受约束的顶点插入到类似k-d树的东西中，并查询它以进行快速高效的最近邻计算