2
$\begingroup$

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.

enter image description here

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.

$\endgroup$
1
$\begingroup$

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...

ShapeSplitting

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.

$\endgroup$
  • $\begingroup$ First, the input could be any closed figure by that I mean you could make the figure by starting at one point and ending at the point "behind" it without lifting the pen and without going over an already drawn line. // The resulting shapes area's just need to be less than or equal to a minimum area, but the less cuts the better. // The cuts can intersect, but it would be better to not backtrack; I think intersection would imply backtracking. // No further restraints I can think of. // I will be using C++ // I like this idea, thinking of ways to improve upon it. $\endgroup$ – AnotherUser Aug 8 '14 at 17:38
  • $\begingroup$ @AnotherUser I'll have to think about this once more, but for a moment this reminded me of the classical delaunay triangulation (can be done with any library e.g. cs.cmu.edu/~quake/triangle.html ). But the crucial thing then is the requirement to have all "cutting lines" connected. Maybe such a triangulation may somehow serve as the basis for solving this problem nevertheless? But again, this is somewhat "brainstorming" - tackling this task algorithmically seems to be much harder than one might think at the first glance. Hope there will be further ideas... $\endgroup$ – Marco13 Aug 8 '14 at 19:04
  • $\begingroup$ Ooooooo, Didn't even think of that from graphics. Turn it all into triangles and traverse the edges! hmm. $\endgroup$ – AnotherUser Aug 8 '14 at 19:23
  • $\begingroup$ You accepted this - but I wonder which path you actually chose for the solution? (Maybe you could create+accept a real answer to your own question...) $\endgroup$ – Marco13 Aug 13 '14 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.