Split Polygon into Small Polygons by contain 1 point each

Question

I am not sure if this algorithm exists, much appreciated if someone can provide me the just the Algorithm's name, then I can Google it up.

Basically let's say I have N Points within a polygon (both convex and concave), and I would like to have a way/algorithm to split this polygon into N polygons, that each of these N polygon contains 1 point only.

Thanks.

Answer 1

I'm reluctant to post this as an answer, but it won't fit in the comments. In the GIS world, this is sometimes referred to as voronoi algorithm. Most GIS tools, like ESRI ArcMap can generate veronoi polgons from a set of points. For your use case I think you can create a veronoi polygon set from your points using the package in the link below (it it's compatible), then take that output, and do some fancy spatial joining to replace your polygon with multiple polygons.

Here is a link to the wikipedia page describing the concept

http://en.wikipedia.org/wiki/Voronoi_diagram

also delaunoy triangulation is another approach you might want to look at

http://www.spatialdbadvisor.com/oracle_spatial_tips_tricks/283/application-of-delaunay-triangulation-and-inverse-distance-weighting-idw-in-oracle

here's another link that has the st_veronoi function mentioned with a link to the above. http://www.spatialdbadvisor.com/source_code/223/geoprocessing-package-documentation

the basis of this package appears to be java JTS, which is apparently being compiled within java stored procs in oracle. JTS is the "standard" for geometry operations in Java. I think I'm going to give it a try myself.

Bear in mind, I have only done this using a tool like ArcGIS, not using anything i mentioned above.... so HTH and I'm not leading you down a rat hole.

Answer 2

I can't give you a name but can describe three different algorithms

I'm going to call the set of points you are given "targets" to simplify my solution beacuse I want to call arbitrary locations on the plain "points":

You're going to be doing quite a lot of arithmetic on 2-vectors

my algorithm to partition the polygon is simple: find the nearest target.

the set of points nearest to any target will have straight edges. the vertices will be equidistant to three (or more) of the targets (or be where the edge intersects the boundary polygon),

your algorithm might go like this:

cross the original set of targets with itself twice to produce a set of triples rejecting those that don't copntain three distinct targets.

for each set of three find the point equidistant from all three targets if that point is closer to any other target reject it.

eventually you'll have (at most) n-2 vertices, then you just need to work out how the edges join up. which you can do this by looking at which targets spawned each vertex.

now you need to add the edges which end at infinity take a cross of targets and itself and find the halfway points between each pair of targets, any points that don't have eactly two nearest targets can be rejected, each of these ponts represents a line (perpendicular bisector) and it will end at one a vertex or at infinity

finally trim the map using the boundary polygon, you may want to drop one of the edges from any fragment that does not contain a target

---

another way

on the other hand you could use a fractal partitioning scheme to divide the polygon into chunks dividing each chunk smaller until it contains a single polygon, the results will be less aesthetically pleasing but looks weren't a design requirement AFAICT.

eg the fractal mapping used for IP addresses.

then having converted coordinates into numbers into divide this into chunks at convenient points, (IE by dropping unneeded trailing 1's)

---

another way

measure the extent of set of targets if it is wider than it is high draw a line vertically dividing it in half else draw horizontally. if the lit hots one of the targets adjust it so that it misses.

repeat for each half until the extet is zero (which means a single point)

Answer 3

You didn't mention any restriction on the shapes of the containing polygons, so I'll assume you don't care. I'll also assume we're in two dimensions, though this can easily be extended. The idea is simple: create new polygons by slicing up your initial polygon with vertical strips halfway between points adjacent on the x-axis. In cases where points share an x-coordinate, split the strip containing them with vertical slices between the points on the y-axis.

Use markg's suggestions if long, thin slices don't work for you.