地理形状分组

Question

我正在使用Dundas Maps尝试绘制一张世界地图，其中各个国家被分组成具有特定业务实现的区域。

我拥有每个国家的形状数据（点和线段）。我可以通过将属于一个区域内的国家的所有点和线段添加到一个新的区域形状来将国家组合成区域。

foreach(var region in GetAllRegions()){
    var regionShape = new Shape { Name = region.Name };
    foreach(var country in GetCountriesInRegion(region.Id)){
        var countryShape = GetCountryShape(country.Id);
        regionShape.AddSegments(countryShape.ShapeData.Points, countryShape.ShapeData.Segments);
    }
    map.Shapes.Add(regionShape);
}

问题在于国家边界仍然显示在区域内，我想要删除它们，只保留区域边界。

邓迪斯（Dundas）多边形必须从同一点开始和结束。这适用于所有国家的形状。现在我需要一个算法来：

-确定国家边界在地区边界相交的位置，以便可以连接地区边界段。
-确定哪些国家边界不是地区边界，以便将其丢弃。
-排序生成的区域点，以使它们按顺序描述形状边界。

以下是我到目前为止在地图上完成的工作。您可以看到仍需删除国家边界。例如，蒙古和中国之间的边界应该被丢弃，而蒙古和俄罗斯之间的边界应该被保留。

我需要保留区域边界的原因是区域颜色在传达信息时具有重要意义，但相邻的区域可能具有相同的颜色。区域可能会更改以包含或排除国家，这就是为什么区域塑造必须是动态的原因。

编辑：

我现在知道我要寻找的是多边形的联合。David Lean 通过 SQL Server 2008中的空间函数 解释了如何做到这一点，这可能是一个选项，但是我的努力已经停滞不前，因为所得到的多边形联合非常复杂，以至于SQL将其截断为43,680个字符。现在，我正在尝试找到解决此问题的方法或找到在代码中执行联合的方法。

- grenade

Answer 1

当分组国家时，我希望没有重叠 - 您可以采用相当简单直接的算法来查找共享顶点 - 简单的方法是遍历一个多边形上的点，看它是否在任何其他多边形上，并且共享相同的下一个或前一个点以查看是否有匹配项。然后只需删除共享顶点即可创建您的联合。

- Rowland Shaw

---

的确。现在我只需要一个算法。 - grenade

刚刚读了你的答案几遍，我想我明白你在说什么。现在我要试一下。 - grenade

我已经理解了哪些顶点是共享的。现在正在通过算法按正确顺序将未共享的顶点添加到联合多边形中... - grenade

我会通过迭代点来完成，这在你能够保证点始终按顺时针顺序排列时特别有用（例如），因为你可以一边构建多边形，一边进行操作 - 从多边形“a”开始，检查是否存在共享顶点，如果找到，则沿着相反方向沿着该周长继续，直到到达原始形状的另一个共享顶点（最坏情况是你离开的那个）。 - Rowland Shaw

你想要移除共享的线段，而不是共享的顶点。只有在两个共享该顶点的线段都从多边形中移除后，才能移除该顶点。否则，你将删除连接两个半多边形的顶点。 - phkahler

Answer 2

假设相邻的国家共享公共顶点和边缘（如果不是这样，问题就变得更加困难）。

对于每个地区，遍历与该地区中的国家对应的多边形，并创建一个顶点和边缘列表。每条边缘应具有指向其端点的两个顶点的指针，每个顶点应具有指向其为端点的边缘的指针。

在将顶点添加到列表中时，请确保它们是唯一的顶点。换句话说，如果您要添加具有坐标（x，y）的顶点，如果列表中已经有这样的顶点，则不要添加新顶点。这意味着您可能需要检查每个新顶点是否与列表中已有的顶点相同。您可以通过将地区的边界框分成例如n x n个箱子来加快此过程，在其中可以存储顶点。当出现新顶点时，请查找其箱子并将其与该箱子中的其他顶点进行比较。

当你将边添加到边列表时，做同样的事情-如果正在添加边（v0，v1），请检查是否存在现有的边缘（v0，v1）或（v1，v0）。 除此之外，在这种情况下，从列表中删除现有的边缘，并且不添加新的边缘。这是因为这两个边缘'取消'彼此-它们来自相邻的国家。而且不要忘记消除对应于已删除边缘的顶点列表中的边缘指针。

完成后，您应该拥有一份未被两个国家共享的边缘列表。这些是构成边界的边缘。您还应该有一个顶点列表，其中一些指向两个边缘，另一些则不指向任何边缘。前者的顶点位于区域边缘上。

现在从边缘列表中选择一条边缘，并将其删除（并从其端点中删除相应的边缘指针）。 转到其中一个顶点端点，它将指向另一条边缘。通过这种方式，您将沿着区域边界从边缘走到边缘。在将这些边缘从edgelist中删除时将它们添加到您的regionShape中。最终，您将回到第一条边缘的端点，并且您将获得一个闭合的循环。

如果边列表中仍有任何边缘，请重新开始该过程以提取另一个边界循环，并继续进行，直到提取完所有边界循环并且边列表为空为止。

我已经提到了一种优化方法，即将顶点在空间上组织成箱子，以便您可以更快地测试它们的相等性。另一种优化是避免从列表中物理删除边缘，而只是将它们标记为“已删除”。

- brainjam