我有一组点(英国完整邮政编码质心)。邮政编码与邮政编码扇区和邮政编码区之间存在层级关系。原来的扇区和区是连续的。我希望得出扇区和地区的近似边界，以便国家的任何部分都恰好属于一个扇区和一个地区，所有生成的多边形理想情况下应该是连续的，并且(显然？)所有原始点都应该位于适当的多边形中。 有没有合适的算法？更好的是，是否有一些适当的实现？
我认为我的解释一定很糟糕，因为我认为这不能回答我的问题。
我们只讨论部门，因为答案也适用于地区。
有1.8m坐标。考虑其中每一个都标有邮政编码，例如“SG13 7AT”邮政编码标签本身可以反射(reflect)邮政编码-扇区-地区结构 - 本例中的扇区是“SG13 7” 除了这些点及其邮政编码标签之外没有其他数据。
我知道存在定义扇区的边界。然而，该边界数据并不是免费提供的。已知每个邮政编码点都位于其真实的扇区边界内。
我想要的是重新创建扇区边界的近似值，以便这些点落在新创建的多边形内，并且我创建的多边形是连续的。这些边界不会准确反射(reflect)原件，但它们对于我的目的来说已经足够了。
最佳答案
要获得平面的扇区划分，请根据采样的邮政编码，使用在完整点集上计算的 Voronoi 图，然后将每个图单元分配给包含该单元站点的扇区。
我用红色和蓝色两个扇区的示例来说明这一点。假设您的初始数据是这样的:
计算完 Voronoi 图后，细胞的划分将如下所示。我勾勒出红色和蓝色部分之间的边界。请注意，它们都是无界的，但这只是因为数据不包含其他扇区。
在你澄清事情之前，现在先听我的回答......
您需要的是“点位置查询”的数据结构:给定空间分割(在您的情况下为平面)和查询点，找到包含查询点的对象。有一些有效的算法(log(n) 查询时间)可以在线、线段和多边形上执行此操作，并且它们已在计算几何库 CGAL 中实现。
请注意，我使用了 CGAL 2D triangulation demo说明解决方案
看看这个 link用于点位置查询的文档。
关于algorithm - 从内部点生成相邻多边形，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10774109/