通过zip-cod搜索覆盖整个区域的最佳方法

Question

我想按邮政编码进行搜索，它由多边形定义，如下图所示：

事实上，我不能在邮政编码本身上搜索，而是在该邮政编码的中心的一个区域，例如zipcode4，这个区域也会碰到1、2和5。你知道吗

以同样的方式，搜索1的结果也来自2、3、4和6。你知道吗

因此，为了避免重复，我想用zipcodes查找，我可以用较少的搜索次数得到所有结果，比如说take 4和take 6

而不是2，5和6

我如何处理这个问题？你知道吗

Answer 1

我不确定我是否完全理解你的目的。 如果你提供一个或两个例子来说明你所提供的输入，以及你想要得到的相应的输出，那将有助于其他人帮助你。你知道吗

我想你的问题是：
将2D区域（国家、地区等）划分为有限大小的多边形，编号为i=1…N。 这里的分区意味着所有N多边形的并集覆盖了您的域，并且任意两个多边形之间的交集的维数最多为1。也就是说，它们可以共享边界，最多不重叠。 你的意思是给出一个目标空间坐标X=（X，y），并得到它所属多边形的编号j。
到目前为止，您可以计算每个多边形的质心Qi，以及以Qi为中心的最小圆Ci，该圆完全包含多边形Pi，并找到包含目标X的所有圆{Cj>。但是多个Ci之间存在重叠（即，{Ci}不是您区域的分区），因此给定的目标可能属于多个Ci。你知道吗

---

如果我答对了，这是一个Point in polygon问题，它对于凸多边形或非凸多边形都有众所周知的解决方案（因为您没有指定）。你知道吗

下面提供了一些链接。 注意事项：

• 我不认为您需要这个，但是您可以通过首先应用您的算法来获得一个较小的候选多边形集，然后在这个缩减集上应用多边形中的点算法来加快代码的速度。

• 如果子面域不是多边形，则问题会变得更困难。这取决于边界的形状。

• 从数学上讲，你仍然需要决定点在边界上到底会发生什么。

---

特定于python的链接：

What's the fastest way of checking if a point is inside a polygon in python

Python: checking if point is inside a polygon

https://automating-gis-processes.github.io/CSC18/lessons/L4/point-in-polygon.html

https://gis.stackexchange.com/questions/170264/python-point-in-polygon-boundary-and-vertex-check-ray-casting

其他通用链接：

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/

http://alienryderflex.com/polygon/

Answer 2

这是set covering problem的完美例子。存在许多好的算法，但是如果您对编写整数编程模型感到满意，那么使用您选择的建模语言进行编码并使用现成的MIP解算器进行求解可能是最简单的方法。你知道吗