Split quadrilateral into sub-regions of a maximum area

Question

It is pretty easy to split a rectangle/square into smaller regions and enforce a maximum area of each sub-region. You can just divide the region into regions with sides length sqrt(max_area) and treat the leftovers with some care.

With a quadrilateral however I am stumped. Let's assume I don't know the angle of any of the corners. Let's also assume that all four points are on the same plane. Also, I don't need for the the small regions to be all the same size. The only requirement I have is that the area of each individual region is less than the max area.

Is there a particular data structure I could use to make this easier?
Is there an algorithm I'm just not finding?

Could I use quadtrees to do this? I'm not incredibly versed in trees but I do know how to implement the structure.

I have GIS work in mind when I'm doing this, but I am fairly confident that that will have no impact on the algorithm to split the quad.

Answer 1

If your quadrilateral is convex, then in fact you can split it into two equal-area pieces which at the same time have equal perimeters! This is called a fair partitioning, and is described at The Open Problems Project (it is open for larger number of pieces, but solved for two pieces).

For nonconvex quadrilaterals, it is not difficult to find a line to partition it into two equal pieces.
I believe this will work: Pass a line through the one reflex vertex, and spin it about that vertex until it partitions the area equally. The same method works for convex polygons, if your only goal is to partition the area into two equal halves.

The generic problem (for arbitrary polygons) goes under the name of "ham-sandwich sectioning of polygons." In fact, I wrote a paper with that exact title.

Answer 2

You could recursively split the quad in half on the long sides until the resulting area is small enough.