Algorithm to split 2D polygon in equal halves
Looking for an algorithm, that would take a custom 2D polygon as an input. The algorithm should split the polygon in half, and produce two (at least approximately) equal halves in terms of area.
My idea so far is:
- Put the polygon on a high resolution grid --> mark cells with 1 if polygon is in it, 0 if not
- find a cell that's on the edge (at least has a neighbour with 0)
- start adding neighbouring cells, while area of cells is < half of the polygons area
I'm curious if there's a better solution than this, in terms of speed or accuracy.
A fast, exact solution for simple polygons:
- Triangulate the polygon.
- Compute the area of each triangle.
- Form the dual tree, where each node has weight equal to the area of the corresponding triangle.
- Find the node that, when removed, leaves connected components that each have total weight of at most half of the area of the polygon.
- The largest connected component that remains is included in one half, and the others are included in the other half. Cut the triangle corresponding to the removed node to even them out (you may need two segments if it has three neighbors).
Step 1 has an O(n log n)-time algorithm. (There are faster algorithms, but I don't know how complicated they are.)
Steps 2 and 3 are obviously O(n).
Step 4 has an O(n)-time algorithm. Root the tree somewhere and compute the total for each sub-tree with depth-first search. Starting from the root, repeatedly descend via the child that has more than half of the overall total until that is no longer possible.
Step 5 is O(1)-time.