Optimal way to cover a complete area making search by zip code

Question

I want to make a search by zip code, which is defined by polygons like in the picture below:

The thing is that actually, I can not make the search on the zip codes itself but in an area from the centroid of that zip code, for example for the zipcode 4, this area touch 1,2 and 5 as well.

In the same way, the search for 1 with takes the results from 2,3,4 and 6 as well.

Hence to avoid getting duplicates I want to take find out with are the zipcodes with which I can get all the results with the less number of searches, say take 4, and 6

Instead of 2,5 and 6

How can I approach this problem?

sancho.s ReinstateMonicaCellio · Accepted Answer · 2019-08-11T09:23:20.473

I am not sure I fully understood your objective. If you provide one or two examples of the input you give, and the corresponding output you mean to get, that would help others help you.

I assume your problem is the following:
You have a given partition of your 2D region (country, area, etc.) into N finite size polygons Pi, numbered i=1...N. Partition here means that the union of all your N polygons covers your domain, and the intersection between any two polygons is of dimension 1, at most. I.e., they can share boundaries, at most, no overlaps. You mean to give a target spatial coordinate X=(x,y), and get the number j of the polygon to which it belongs.
So far, you can compute the centroid Qi of each polygon and the minimal circle Ci centered at Qi that fully includes the polygon Pi, and find all circles {Cj} that contain your target X. But there is an overlap among several Ci (i.e., {Ci} is not a partition of you region), so a given target may belong to more than one Ci.

If I got this right, this is a Point in polygon problem, which has well known solutions for either convex or non-convex polygons (since you did not specify that).

Some links are provided below. A few notes:

I don't think you would need this, but you may speed up a little you code by first applying your algorithm to get a smaller set of candidate polygons, and then apply the point-in-polygon algorithm on this reduced set.
If your subregions are not polygons, the problem becomes harder. It depends on the shapes of the boundaries.
Mathematically speaking, you still have to decide what happens with poins exactly on boundaries.

Links specific for 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

Optimal way to cover a complete area making search by zip code

2 Answers2