CODEWITHSUNDEEP
algorithmgeometrygiscomputational-geometry
Tim Pigden
Tim Pigden

Reputation: 935

Generate adjacent polygons from interior points

I have a set of points (UK full postcode centroids). There is a hierarchical relationship in the postcodes to postcode sectors and postcode districts. The original sectors and districts are contiguous. I wish to derive approximate boundaries for the sectors and districts such that any part of country falls into exactly one sector and exactly one district, all resulting polygons should ideally be contiguous and (obviously?) all original points should be in the appropriate polygons. Is there some appropriate algorithm? Better yet, is there some appropriate implementation?

I think I must have explained it poorly since I don't think that answers my question.

Let's just talk about sectors since the answer would also apply to districts.

There are 1.8m coordinates. Consider each of these is tagged with a postcode such as "SG13 7AT" The postcode tag can itself reflects the postcode-sector-district structure - the sector in this case is "SG13 7" There is no other data than these points and their postcode tags.

I know that there exists a boundary that defines the sector. However, this boundary data is not freely available. Each postcode point is known to be inside its true sector boundary.

What I want is to recreate approximations of the sector boundaries such that the points fall within the newly created polygons and so that the polygons I create are contiguous. These boundaries will not be an accurate reflection of the originals, but they are good enough for my purposes.

Upvotes: 2

Views: 378

Answers (1)

killogre
killogre

Reputation: 1800

To obtain the partition of the plane into sectors, according to the sampled postal codes, use the Voronoi diagram calculated on the full set of points, then assign each diagram cell to the sector containing the cell's site.

I am illustrating this with an example on two sectors, red and blue. Say your initial data is this:

data from two sectors: red and blue

Then after computing the Voronoi diagram, the division to cells will look as follows. I outlined the boundary between the red and blue sectors. Note that they are both unbounded, but that's just because the data doesn't include other sectors.

Voronoi diagram of the data

Now to my answer before you clarified things...

What you need is a data structure for "Point Location Queries": given a subdivision of space (in your case, the plane) and a query point, find the object that contains the query point. There are efficient algorithms (log(n) query time) for doing that on lines, segments, and polygons, and they have been implemented in the computational geometry library CGAL.

Note that I used the CGAL 2D triangulation demo to illustrate the solution

Check out this link for the documentation of point location queries.

Upvotes: 2

Related Questions