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.

What does it mean to split an area into smaller regions and enforce a maximum area? — cheeken, Jun 27 '12 at 00:43
Do you mean split the region into sub-regions such that each sub-region has an area no larger than a given value? — Vaughn Cato, Jun 27 '12 at 00:44
Are the quadrilaterals a collection of 4 points on the same plane? — Sean Johnson, Jun 27 '12 at 00:46
@VaughnCato yes, that is exactly what I meant. Sean, all four points are on the same plane. — Jake, Jun 27 '12 at 00:54
While not exactly what you want to do, take a look at this similar sounding [question](http://stackoverflow.com/q/4373741/355230) and its answers. — martineau, Jun 27 '12 at 01:49

score 1 · Answer 1 · answered Jun 27 '12 at 00:49

1

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

answered Jun 27 '12 at 00:49

Hugh Bothwell

55,315
8
84
99

1

What would you do with a shape like the bottom right in the image on wikipedia? http://en.wikipedia.org/wiki/Quadrilateral – Jake Jun 27 '12 at 00:52
@jake: Break it into two triangles first – Vaughn Cato Jun 27 '12 at 00:55
@Jake: Do you have a requirement that the sub-regions also be quadrilaterals? – Vaughn Cato Jun 27 '12 at 00:58
@VaughnCato also, dividing the shape into two triangles first would add another arbitrary boundary. A subregion would then be unable to belong to both triangles. – Jake Jun 27 '12 at 01:06
@Jake: If you split the quadrilateral into two triangles, and then split each triangle at the same point along the common edge, then you can re-join the four triangles into two quadrilaterals. You can repeat this process until you have quadrilaterals of the desired area. – Vaughn Cato Jun 27 '12 at 04:37

score 1 · Answer 2 · answered Jun 27 '12 at 12:21

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.

Split quadrilateral into sub-regions of a maximum area

2 Answers2