按邮政编码搜索整个区域的最佳方式
Optimal way to cover a complete area making search by zip code
我想按邮政编码进行搜索，邮政编码由多边形定义，如下图所示：
事实上，我无法对邮政编码本身进行搜索，而是在该邮政编码中心的区域中进行搜索，例如对于邮政编码 4，该区域触摸 1,2 和 5 作为出色地。
以同样的方式，对 1 的搜索也会从 2、3、4 和 6 中获取结果。
因此，为了避免重复，我想找出的是邮政编码，通过这些邮政编码，我可以用较少的搜索次数获得所有结果，比如说取 4 和 6
而不是 2,5 和 6
我该如何解决这个问题？
这是set covering problem的完美范例。存在许多好的算法，但如果您习惯于编写整数规划模型，那么使用您选择的建模语言对其进行编码并使用现成的 MIP 求解器求解可能是最简单的方法。
我不确定我是否完全理解您的 objective。
如果您提供一两个您提供的输入的示例，以及您想要获得的相应输出，那将有助于其他人帮助您。
我假设您的问题如下：
您将二维区域（国家、地区等）划分为 N 个有限大小的多边形 Pi，编号为 i=1...N。
这里的分区意味着你所有的 N 多边形的并集覆盖你的域，并且任意两个多边形之间的交集最多为 1 维。即，它们最多可以共享边界，没有重叠。
你的意思是给一个目标空间坐标X=(x,y),然后得到数字j 所属的多边形。
到目前为止，您可以计算每个多边形的质心 Qi 和以 Qi[ 为中心的最小圆 Ci =81=] 完全包含多边形 Pi，并找到包含目标 [=53] 的所有圆 {Cj} =]X。但是几个 Ci 之间存在重叠（即 {Ci} 不是您所在区域的分区） , 因此给定目标可能属于多个 Ci.
如果我没猜错，这是一个 Point in polygon 问题，它对凸多边形或非凸多边形都有众所周知的解决方案（因为您没有指定）。
下面提供了一些链接。
一些注意事项：
我认为您不需要这个，但是您可以通过首先应用您的算法来获得一组较小的候选多边形，然后应用点输入来加快编码速度- 此缩减集上的多边形算法。
如果你的子区域不是多边形，问题就会变得更难。这取决于边界的形状。
从数学上讲，您仍然必须决定恰好在边界上的点会发生什么。
python 的特定链接：
Python: checking if point is inside a polygon
https://automating-gis-processes.github.io/CSC18/lessons/L4/point-in-polygon.html
其他通用链接：
How can I determine whether a 2D Point is within a Polygon?
https://en.wikipedia.org/wiki/Point_in_polygon
https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/
我想按邮政编码进行搜索，邮政编码由多边形定义，如下图所示：
事实上，我无法对邮政编码本身进行搜索，而是在该邮政编码中心的区域中进行搜索，例如对于邮政编码 4，该区域触摸 1,2 和 5 作为出色地。
以同样的方式，对 1 的搜索也会从 2、3、4 和 6 中获取结果。
因此，为了避免重复，我想找出的是邮政编码，通过这些邮政编码，我可以用较少的搜索次数获得所有结果，比如说取 4 和 6
而不是 2,5 和 6
我该如何解决这个问题？
这是set covering problem的完美范例。存在许多好的算法，但如果您习惯于编写整数规划模型，那么使用您选择的建模语言对其进行编码并使用现成的 MIP 求解器求解可能是最简单的方法。
我不确定我是否完全理解您的 objective。 如果您提供一两个您提供的输入的示例，以及您想要获得的相应输出，那将有助于其他人帮助您。
我假设您的问题如下：
您将二维区域（国家、地区等）划分为 N 个有限大小的多边形 Pi，编号为 i=1...N。
这里的分区意味着你所有的 N 多边形的并集覆盖你的域，并且任意两个多边形之间的交集最多为 1 维。即，它们最多可以共享边界，没有重叠。
你的意思是给一个目标空间坐标X=(x,y),然后得到数字j 所属的多边形。
到目前为止，您可以计算每个多边形的质心 Qi 和以 Qi[ 为中心的最小圆 Ci =81=] 完全包含多边形 Pi，并找到包含目标 [=53] 的所有圆 {Cj} =]X。但是几个 Ci 之间存在重叠（即 {Ci} 不是您所在区域的分区） , 因此给定目标可能属于多个 Ci.
如果我没猜错，这是一个 Point in polygon 问题，它对凸多边形或非凸多边形都有众所周知的解决方案（因为您没有指定）。
下面提供了一些链接。 一些注意事项：
我认为您不需要这个，但是您可以通过首先应用您的算法来获得一组较小的候选多边形，然后应用点输入来加快编码速度- 此缩减集上的多边形算法。
如果你的子区域不是多边形，问题就会变得更难。这取决于边界的形状。
从数学上讲，您仍然必须决定恰好在边界上的点会发生什么。
python 的特定链接：
Python: checking if point is inside a polygon
https://automating-gis-processes.github.io/CSC18/lessons/L4/point-in-polygon.html
其他通用链接：
How can I determine whether a 2D Point is within a Polygon?
https://en.wikipedia.org/wiki/Point_in_polygon
https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/