[Community] Spliting a polygon into two polygons with the same area

[Nick Ves]

Hey list,

I have a question: How you can divide a polygon into two smaller polygons
with the same area?

I know this problem have infinitive answers, because there are infinitive
lines that intersects with the a polygon, thus for a constrain I thought
that the intersecting line should pass from the point which defines the the
middle of the perimeter of the polyline.

Did anyone came across with a solution? I've read about the problem here
[1], but a google search didn't provide anything that can be used with
python.


With Regards,

Nick
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.gispython.org/pipermail/community/attachments/20120725/202b08d4/attachment.htm>

[Sean Gillies]

Hi Nick,

Martin Davis, the author of JTS (from which GEOS is ported), fields
the same question here:

http://sourceforge.net/mailarchive/forum.php?thread_name=CAK2ens1XNR1ZaLa6Zq_EuC7aDG%2B3mt0BeCHm%2BTDEhUaR6g0S9Q%40mail.gmail.com&forum_name=jts-topo-suite-user

He doesn't have a general solution.

The very latest version of the GEOS library implements Delaunay
triangulation and I can imagine it used to break a polygon down into
triangles and then you'd start at a point and begin accumulating
adjacent triangles until you hit your target area... something like
that? Shapely doesn't support this yet, but will later this fall.

Yours,

Post by Nick Ves
Hey list,
I have a question: How you can divide a polygon into two smaller polygons
with the same area?
I know this problem have infinitive answers, because there are infinitive
lines that intersects with the a polygon, thus for a constrain I thought
that the intersecting line should pass from the point which defines the the
middle of the perimeter of the polyline.
Did anyone came across with a solution? I've read about the problem here
[1], but a google search didn't provide anything that can be used with
python.
With Regards,
Nick
_______________________________________________
Community mailing list
Community at lists.gispython.org
http://lists.gispython.org/mailman/listinfo/community

[Harasty, Daniel J]

Nick,

I assume Shapely's "centroid" function is a true, center-of-mass of centroid. (This could be verified

If so, the ANY line though the centroid will bisect the original polygon in to two equal portions by area.

There are two questions:
- How do you pick a "good line"?
- Once you've picked a line, how do you actually use the functions in the API to concoct the two polygons (two halves) from the original one.

The first one is a bit subjective: "good" versus "less good" is defined by your actual need. I could suggest some heuristics if you fill us in. (Is this process only going to be done once? Or N times? One post mentioned the idea of making the pieces "kinda square". Is that your need?)

For now, I'll just suggest you pick the cutline to be a simple vertical segment from (x-centroid, y-max) to (x-centroid, y-min), where:
- x-centroid is the x-value of the centroid
- y-max is the maximum y-value of the original polygon
- y-min is the minimum y-value of the original polygon

Here's a recipe for the second part (using the API to cleave the original poly):

- "poly" is your original Polygon
- "cutline" is the LineString from the above

If the original polygon is simple (no holes or self crossing) and convex, then I think this is the recipe:
- get the exterior LinearRing of the polygon:

exterior = poly.exterior

- use cascaded union to get the cut-up segments of where the lines "cut" each other:

segments = cascaded_union([exterior, cutline])

- use polygonize to convert this back to polygons:

poly_parts = list(polygonize(segments))

Then these should be true:

len(poly_parts) == 2
poly_parts[0].area == poly_parts[1].area
poly_parts[0].area * 2 = poly.area

Make sense?

Now: let me know if your polygon is NOT necessarily simple and convex. (Hint: if any of the above were NOT true, then the preconditions of simple and convex were not met.) We'll need to add another few steps (and your result for "each half" might be MultiPolygons). Shall I elaborate, or will that do for now?

-- Dan Harasty






The second has many steps in the general case. , but can be simplified in certain cases

Post by Nick Ves
Hey list,
I have a question: How you can divide a polygon into two smaller
polygons with the same area?
I know this problem have infinitive answers, because there are
infinitive lines that intersects with the a polygon, thus for a
constrain I thought that the intersecting line should pass from the
point which defines the the middle of the perimeter of the polyline.
Did anyone came across with a solution? I've read about the problem
here [1], but a google search didn't provide anything that can be used
with python.
With Regards,
Nick