由内点生成相邻多边形

Question

我有一组点（英国完整的邮政编码中心）。邮政编码与邮政编码扇区和邮政编码区之间存在等级关系。原来的扇区和区是毗连的。我希望推导出扇区和地区的近似边界，这样国家的任何部分都正好属于一个扇区和一个地区，所有得到的多边形理想地应该是连续的，而且（显然？）所有原点都应该在适当的多边形中。有没有合适的算法？更好的是，是否有一些适当的实现？

我想我一定解释得很差，因为我不认为这回答了我的问题。

让我们只谈部门，因为答案也适用于地区。

有1.8米坐标。考虑每一个都有一个邮政编码标签，如“SG13 7AT”，邮政编码标签本身可以反映邮政编码-扇区-地区结构-在这种情况下扇区是“SG13 7”。除了这些点及其邮政编码标签之外，没有其他数据。

我知道存在一个界定扇区的边界。然而，这种边界数据并不是免费获得的。每个邮政编码点都在其真正的扇区边界内。

我想要的是重新创建扇区边界的近似值，这样点落在新创建的多边形内，这样我创建的多边形是连续的。这些边界不能准确地反映原稿，但它们对我的目的来说已经足够好了。

Answer 1

为了得到平面的扇区划分，根据采样的邮政编码，使用在全集点上计算的Voronoi图，然后将每个图单元分配到包含单元站点的扇区。

我用一个关于两个扇区的例子来说明这一点，红扇区和蓝扇区。假设你的初始数据是这样的：

然后在计算Voronoi图之后，对单元格的划分如下所示。我勾勒了红蓝两个扇区之间的界限。请注意，它们都是无界的，但这只是因为数据不包括其他部门。

在你澄清之前我的回答...

您需要的是“点位置查询”的数据结构：给定空间细分（在您的例子中是平面）和查询点，找到包含查询点的对象。对于线、段和多边形，有有效的算法（log(n)查询时间），它们已经在计算几何库CGAL中实现。

注意，我使用了CGAL 2D三角化演示来说明解决方案

查看此链接以获得点位置查询的文档。