java - 在 2D 区域中查找多边形

Question

我有一个二维区域，其中包含 X 个多边形。我唯一的信息是多边形的边缘。多边形由 Voronoi 图的 Fortunes 算法形成。

我正在尝试在 java 中形成一个多边形列表。我的问题在于找出属于多边形的边。我应该补充一点，我在每个多边形内也有一个点，这就是 Voronoi 图的形成点。

我尝试了多种方法。我试过计算离每条边最近的点，但这会产生错误。我也尝试过对角线扫描，试图以某种方式找出边缘，但它也没有用。

编辑:

每条边都是一条线，它有x1、y1、x2和y2。我有一个边列表和一个可用点列表，我能够绘制 Voronoi 图。我想要的输出是对于每个点，我都有一个边列表，这些边形成该点所在的多边形形状。

http://www.cs.wustl.edu/~pless/546/lectures/f16_voronoi.jpg

这是我目前所拥有的示例。我能制作这张图片只是因为我知道每条线的起点和终点。我对多边形一无所知。我的目标是获得一个形状列表，以便我可以选择要绘制的形状。

编辑 5:

这是我设置的测试点。我正在寻找基于它们的 voronoi 图。我有分隔点的线，这些点构成了 voronoi 的基础。我现在需要根据这些线制作多边形。

vals = new double[2][6];
    vals[0][0] = 150;
    vals[1][0] = 250;
    vals[0][1] = 250;
    vals[1][1] = 275;
    vals[0][2] = 300;
    vals[1][2] = 300;
    vals[0][3] = 425;
    vals[1][3] = 425;
    vals[0][4] = 425;
    vals[1][4] = 125;
    vals[0][5] = 250;
    vals[1][5] = 500;

答案中提供的点和代码产生以下结果:

Answer 1

关于 Voronoi 图的一些观察(使用 good ole Wikipedia 作为引用):

1. 我们将多边形内部的点称为“种子”。
2. 每个多边形都有一个种子，多边形本身表示比任何其他种子更接近其种子的所有点的集合。
3. 图表边界上的边段最接近一个种子。
4. 图表内部的边线段(不是图表边界上的边线段)由与两个种子距离相同的线段组成。
5. 图表边界上的多边形顶点是与两个或更多种子距离相同的点。一个可能的异常(exception)是边界的四个角点之一，尽管这些在理论上可以与多个种子等距。
6. 图表内部的多边形顶点(即那些不在边界上的顶点)是与三个或更多种子距离相同的点。

因此我建议的方法是遍历边段的集合，比较每个边段的端点与种子的距离，并找到最近的一个或多个种子。

以下未优化，但应该符合要求，除非我理解有误。 List<SeedPoint> seeds将具有种子点本身以及围绕它的边缘。

顺便说一句，我是 ignoring precision / decimal rounding issues这可能会影响逻辑。

// Get the list of edges and seeds from wherever you are getting them.
List<GraphEdge> edges = ...
List<SeedPoint> seeds = ...    // Assume SeedPoint is a subclass of Point.

for ( GraphEdge edge : edges )
{
  List<SeedPoint> closestSeeds = new ArrayList<>(2);

  // These can safely be instantiated to the diagram's hypotenuse + 1
  double closestStartDistance = ...
  double closestEndDistance = ...

  // Compare the distance of all seeds to the current edge's endpoints:
  for( SeedPoint seed : seeds )
  {
    double startEdgeToSeed = seed.distanceFrom( edge.getStartPoint() );
    double endEdgeToSeed   = seed.distanceFrom( edge.getEndPoint() );

    /* For a seed to be tracked as closest to the edge, BOTH the edge
       end points must be as close or closer to the seed than the
       current known closest edge.

       CAUTION: Update this to consider decimal precision issues! */

    if ( startEdgeToSeed == closestStartDistance &&
         endEdgeToSeed   == closestEndDistance )
    {
      // Same closeness to the currently known closest seed.
      closestSeeds.add(seed);
    }
    else if ( startEdgeToSeed <= closestStartDistance &&
              endEdgeToSeed   <= closestEndDistance )
    {
      /* Current seed is closer than the currently known closest seed.
         Clear previous seeds and track the current. */
      closestSeeds.clear();
      closestSeeds.add( seed );
      closestStartDistance = startEdgeToSeed;
      closestEndDistance   = endEdgeToSeed;
    }

  }

  /* At the end of the iteration, closestSeeds should have size
     of either 1 or 2.  Associate the edge to the seed or seeds
     to which it is closest. */
  for ( SeedPoint closestSeed : closestSeeds )
  {
    closestSeed.addPolygonEdge( edge );
  }

}

为了方便起见，您可能希望某处有一个方法，该方法将两个点作为参数并计算它们之间的距离。在上面的代码中，这就是somePoint.distanceFrom(someOtherPoint)。是。

可能还有其他更好的方法，并且可能有一些方法可以优化上面的示例...