在jgrapht中计算dijkstrashortestpath时出错

zpjtge22  于 2021-07-09  发布在  Java
关注(0)|答案(1)|浏览(421)

我正在编写一个googlecloud函数来返回一个多边形中一个给定的源顶点的距离边界。我收到一条错误消息,说:
java.lang.illegalargumentexception:图形必须包含源顶点!在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>
gfttwv5a

gfttwv5a1#

发生错误的原因是 originVertex 不包括在 graph . tin.getNavigator().getNearestVertex() 返回未包含在图中的顶点,因为它不考虑顶点是否受约束。它将返回最近的全局顶点,该顶点恰好是无约束的(因此没有插入到图中)。
你有两个选择来避免这个错误。
在调用其余代码之前,请检查图形是否包含顶点(但它仅在给定原点位置位于(或非常接近)受约束区域时执行):

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

总是找到最近的约束顶点;在这种情况下,你不能使用 tin.getNavigator().getNearestVertex() . 相反,迭代图的顶点,找到一个最接近给定的原点位置,或插入像一个k-d树的约束顶点,并查询快速有效的最近邻计算。

相关问题