Method and apparatus for partitioning an arbitrarily-shaped area

A method for processing points in a bounded area to locate a medial axis, the method comprising:

• determining a nearest boundary point outside the area corresponding to each point inside the area;
• finding adjacent points inside the area which have different corresponding nearest boundary points separated by at least a threshold arc length;
• generating paths between said adjacent points with different corresponding nearest boundary points;
• and
• locating the medial axis from amongst said paths.

A processing method for partitioning a bounded area in an image into sub-areas, the method comprising:

• determining pinch cuts located in narrow regions near rapid changes in area width;
• partitioning the area into sub-areas separated by the pinch cuts;
• determining a medial axis comprising at least one medial line segment approximately midway between two boundary line segments;
• and
• further partitioning the area into sub-areas by placing slice cuts approximately perpendicular to the medial line segment and spaced approximately evenly along the medial line segment.

An apparatus for processing an array of points, wherein the processing includes processing a bounded two-dimensional area in the array of points, the apparatus comprising:

• means for storing boundary coordinates at boundary points adjacent to two-dimensional area;
• means for determining an interior point to be processed using a raster pattern moving in a first direction along a line and going from line to line in a second direction inside the two-dimensional area;
• means for processing the interior point by
• i) considering a first boundary location stored at a first adjacent point (located opposite the first direction in relation to the interior point),
• ii) considering a second boundary location stored at a second adjacent point (located opposite the second direction in relation to the interior point),
• iii) determining a closer boundary location to be the second boundary location if the second boundary location is closer in Euclidean distance to the interior point and to be the first boundary location if the first boundary location is even closer in Euclidean distance to the interior point, and
• iv) storing the closer boundary location at the interior point, unless already stored at the interior point is a previously stored boundary location which is even closer than the closer boundary location;
• and
• means for reversing the first and second directions such that they are opposite of their former directions.