Patent ID: 7388584

Claim:
A method for determining insides and outsides of boundaries, comprising: an external data input step (A) of inputting external data constituted by boundary data of objects; a cell division step (B) of dividing the external data into rectangular parallelepiped cells having boundary planes orthogonal to each other; a cell classification step (C) of classifying the cells into a boundary cell that includes the boundary data and a non-boundary cell that does not include the boundary data; a space classification step (D) of classifying the non-boundary cells into a plurality of spaces that are partitioned by the boundary cells, wherein the space classification step (D) comprises: an initial setting step (D 1 ) of initializing a space number k; a labeling step (D 2 ) of successively scanning all of the cells to label the rectangular parallelepiped cells with the space number k; and a label modifying step (D 3 ) of modifying the space numbers k of the labeled cells; and outputting to an output device output data of either the cell classification step (C), the space classification step (D), or both, wherein the labeling step (D 2 ) comprises: a step (E 1 ) of labeling the currently scanned cell with the same space number as that of the immediately preceding cell when the immediately preceding cell and the currently scanned cell are the non-boundary cells; a step (E 2 ) of labeling the currently scanned cell with the space number for the boundary cell when the currently scanned cell is the boundary cell; and a step (E 3 ) of updating the space number k to be the space number k+1, and labeling the currently scanned cell with the updated space number k+1 when the immediately preceding cell is the boundary cell, and the currently scanned cell is the non-boundary cell, and the label modifying step (D 3 ) comprises: a step (F 1 ) of comparing the space numbers of the neighboring cells that neighbor one another; and a step (F 2 ) of re-labeling the neighboring cells with the smallest of the compared space numbers, and wherein in order to scan all the rectangular parallelepiped cells one after another, the labeling step (D 2 ) is performed for three directions of X, Y and Z in turn, or is performed in a recursive manner.