Algorithm to cut a 2D closed shape into roughly equally sized areas in a single path?

Question

I am looking to create or find an algorithm that can divide a 2D closed shape into sections of roughly equal area in a single path.

Basically something like this picture; imagine I can free hand strait lines too. The thin line is the "cut path", notice each line in the cut path shares an endpoint with the preceding line.

Is there any sort of algorithm that could do this, or any algorithm that is close to this idea that I might be able to modify?

If something doesn't exist, any ideas on how the algorithm might work?

---

Initial idea:

1. Find a Max/Min X/Y point on the outline of the figure.
2. Calculate the area of the figure that has not been cut yet, if it is less than the minimum area stop.
3. If the area is larger, determine which direction from the point you are at that the largest concentration of area is (basically center of gravity of the figure).
4. Draw a line from the current location perpendicular to the direction of the center of gravity until you hit an outline.
5. Repeat steps 2-4 ad infinitum.

*This does have obvious issues. Doesn't take into account the area of the resulting pieces, might be somewhat computational expensive, etc.

Answer 1

An interesting question. Some more details could be relevant, though:

• Do you want to define the number of areas, or their (maximum or minumum) size?
• What does "roughly equal" mean exactly? (Or roughly, at least...)
• Are the input shapes always simple polygons?
• Should the resulting areas be convex and connected? Or may one "cut" pass through a concavity of the input area (like the rightmost cut line in the lightning-shape)?
• May the cuts intersect? (Probably not, but I think this would happen for your initial idea...)
• Are there any further constraints? (E.g. about running time and determinism?)
• (More out of curiosity: ) In which language and which context are you going to implement this?

Of course, the applicability of any suggestion may depend on the above mentioned points.

One idea that came to my mind was: You could place a sequence of points, describing the "cutting line", on the polygon border. Initially, this could be done at arbitrary positions, but in a "zig-zag" fashion: Points with an even index are placed together, and points with an odd index are placed together. Then, these points are "shifted" along the polygon border, in either direction, but preserving their order, so that the "zig-zag" pattern is kept. This shifting is done iteratively, as some kind of relaxation process.

I tried to sketch the idea here...

Of course, this has some issues as well. First of all, one would probably have to prevent the cuts from passing through concave areas (i.e. to prevent them from cutting the area outside of the polygon). Additionally, there would be many degrees of freedom and tuning parameters when actually implementing this. But maybe it's worth to think about this.