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:
- Find a Max/Min X/Y point on the outline of the figure.
- Calculate the area of the figure that has not been cut yet, if it is less than the minimum area stop.
- 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).
- Draw a line from the current location perpendicular to the direction of the center of gravity until you hit an outline.
- 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.