在 JGrapht 中计算 DijkstraShortestPath 时出错

Question

我正在写一个 Google 云函数到 return 从多边形内的给定源顶点到多边形中的距离边界。我收到一条错误消息：

java.lang.IllegalArgumentException: Graph必须包含源顶点！在 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() 返回一个不包含在图中的顶点，因为它没有考虑顶点是否受约束。它返回最近的全局顶点，该顶点恰好不受约束（因此尚未插入到图中）。

您有两种选择可以避免该错误。

在调用其余代码之前检查图形是否包含顶点（但是它只会在给定的原点位置在（或非常接近）约束区域内时执行）：

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

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

在 JGrapht 中计算 DijkstraShortestPath 时出错

Error when computing DijkstraShortestPath in JGrapht

java

google-cloud-functions

jgrapht