Method and system for fast approximate region bisection
Methods and systems in accordance with the present invention automatically subdivide an area having an arbitrary shape into multiple sub-regions that have approximately equal area under a threshold, with compact shapes having minimal perimeter length. These systems input an arbitrarily shaped zone and recursively bisect it until all of the new sub-zones are smaller than a particular threshold. A data processing system subdivides a two-dimensional region, such as a digital image of a landmass. The data processing system loads the region into memory, determines a minor axis of the region, and splits the region along the minor axis into a first sub-region and a second sub-region. The sub-regions are evaluated to determine if they are under the threshold area. The steps of the process are repeated until all resulting sub-regions are under the threshold area. Consistently compact sub-regions with minimal perimeter are achieved by splitting along the minor axis.
1. A method in a data processing system for subdividing a region, the method comprising:
receiving data representing the region by the data processing system;
determining a centroid of the region;
determining a minor axis of the region that crosses through the centroid;
dividing the region along the minor axis into a first sub-region and a second sub-region; and
recursively dividing the first sub-region and the second sub-region into further sub-regions by, for each of the sub-regions:
determining a sub-region centroid of the sub-region;
determining a sub-region minor axis of the sub-region that crosses through the sub-region centroid; and
dividing the sub-region along the minor axis into a further first sub-region and a further second sub-region.
2. The method of claim 1 , further comprising:
receiving a threshold; and
determining if the first sub-region and second sub-region are less than or equal to the threshold.
3. The method of claim 2 , further comprising:
transmitting the first sub-region and the second sub-region if the first sub-region and second sub-region are less than or equal to the threshold.
4. The method of claim 1 , wherein the threshold is an area size.
5. The method of claim 4 , further comprising measuring an area of the first sub-region and an area of the second sub-region to determine each of the areas are less than or equal to the threshold.
6. The method of claim 5 , further comprising determining a major axis of the region that that crosses through the centroid and is perpendicular to the minor axis.
7. A data processing system configured to subdivide a region, the system comprising:
a memory storing instructions configured to cause a processor to:
receive data representing the region into the memory;
determine a centroid of the region;
determine a minor axis of the region that crosses through the centroid;
divide the region along the minor axis into a first sub-region and a second sub-region; and
recursively divide the first sub-region and the second sub-region into further sub-regions by, for each of the sub-regions:
determining a sub-region centroid of the sub-region;
determining a sub-region minor axis of the sub-region that crosses through the sub-region centroid; and
dividing the sub-region along the minor axis into a further first sub-region and a further second sub-region; and
the processor configured to execute the instructions.
8. The data processing system of claim 7 , wherein the instructions are further configured to cause to the processor to:
receive a threshold; and
determine if the first sub-region and second sub-region are less than or equal to the threshold.
9. The data processing system of claim 8 , wherein the instructions are further configured to cause to the processor to:
transmit the first sub-region and the second sub-region if the first sub-region and second sub-region are less than or equal to the threshold.
10. The data processing system of claim 7 , wherein the threshold is an area size.
11. The data processing system of claim 10 , wherein the instructions are further configured to cause to the processor to:
measure an area of the first sub-region and an area of the second sub-region to determine each of the areas are less than or equal to the threshold.
12. The data processing system of claim 11 , wherein the instructions are further configured to cause to the processor to:
determine a major axis of the region that that crosses through the centroid and is perpendicular to the minor axis.
13. A method in a data processing system for subdividing a region, the method comprising:
receiving data representing the region by the data processing system;
determining a centroid of the region;
determining a minor axis of the region that crosses through the centroid;
dividing the region along a line parallel to the minor axis into a first sub-region and a second sub-region; and
recursively dividing the first sub-region and the second sub-region into further sub-regions by, for each of the sub-regions:
determining a sub-region centroid of the sub-region;
determining a sub-region minor axis of the sub-region that crosses through the sub-region centroid; and
dividing the sub-region along the minor axis into a further first sub-region and a further second sub-region.
14. The method of claim 13 , further comprising:
receiving a threshold; and
determining if the first sub-region and second sub-region are less than or equal to the threshold.
15. The method of claim 14 , further comprising:
transmitting the first sub-region and the second sub-region if the first sub-region and second sub-region are less than or equal to the threshold.
16. The method of claim 14 , further comprising:
adjusting a position of a dividing line parallel to the minor axis to change the first sub-region and second sub-region.