Method and system for fast approximate region bisection
View Patent ↗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; and
dividing the region along the minor axis into a first sub-region and a second sub-region;
receiving a threshold;
determining if the first sub-region and second sub-region are less than or equal to the threshold;
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; and
if the first sub-region and second sub-regions are greater than to the threshold:
determining a first centroid of the first sub-region;
determining a first minor axis of the first sub-region that crosses through the first centroid;
dividing the first sub-region along the first minor axis into a third sub-region and a fourth sub-region;
determining a second centroid of the second sub-region;
determining a second minor axis of the second sub-region that crosses through the second centroid; and
dividing the second sub-region along the minor axis into a fifth sub-region and a six sub-region.
2. A method in a data processing system for subdividing a region, 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; and
dividing the region along the minor axis into a first sub-region and a second sub-region
receiving a threshold; and
repeatedly performing on each sub-region:
determining if each sub-region is less than or equal to the threshold;
if the sub-regions are less than or equal to the threshold:
outputting each sub-region that is less than or equal to the threshold;
if the sub-regions are greater than the threshold:
determining a centroid of each sub-region;
determining a minor axis of each sub-region that crosses through the sub-region's centroid; and
dividing each sub-region along the minor axis into a two new sub-regions; and
repeating the steps on each of the new sub-regions starting from determining if each sub-region is less than or equal to the threshold.
3. The method of claim 1 , wherein the threshold is an area size.
4. The method of claim 3 , 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.
5. The method of claim 4 , further comprising determining a major axis of the region that that crosses through the centroid and is perpendicular to the minor axis.
6. 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; and
divide the region along the minor axis into a first sub-region and a second sub-region;
receive a threshold; and
determine if the first sub-region and second sub-region are less than or equal to the threshold;
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; and
if the first sub-region and second sub-regions are greater than to the threshold:
determine a first centroid of the first sub-region;
determine a first minor axis of the first sub-region that crosses through the first centroid; and
divide the first sub-region along the first minor axis into a third sub-region and a fourth sub-region; and
determine a second centroid of the second sub-region;
determine a second minor axis of the second sub-region that crosses through the second centroid; and
divide the second sub-region along the minor axis into a fifth sub-region and a six sub-region; and
the processor configured to execute the instructions.
7. A data processing system 6 for subdividing a region, wherein the instructions are further configured to cause to the 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;
receive a threshold; and
repeatedly perform on each sub-region:
determining if each sub-region is less than or equal to the threshold;
if the sub-regions are less than or equal to the threshold:
outputting each sub-region that is less than or equal to the threshold;
if the sub-regions are greater than the threshold:
determining a centroid of each sub-region;
determining a minor axis of each sub-region that crosses through the sub-region's centroid; and
dividing each sub-region along the minor axis into a two new sub-regions; and
repeating the steps on each of the new sub-regions starting from determining if each sub-region is less than or equal to the threshold.
8. The data processing system of claim 6 , wherein the threshold is an area size.
9. The data processing system of claim 8 , 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.
10. The data processing system of claim 9 , 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.