JP2006323780A - Image processing apparatus and image processing method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a technique for easily generating boundary shape data even when a complicated shape such as a thin shape is used as a boundary.
Out of rectangular areas obtained by dividing a two-dimensional virtual plane in which a plurality of areas are set, a boundary rectangular area including a boundary portion between the set areas is divided into a predetermined number of areas (S508). The position relationship between the vertices constituting the divided area and the boundary portion in the divided area is obtained, the intersection position between the vertex or ridge line constituting the divided area and the boundary portion in the divided area is obtained, and the positional relationship and the intersection position are determined. By identifying the part that belongs to the area set in the divided area and the part that does not belong, it is possible to determine which pattern among the multiple types of patterns created in advance. Determine (S505).
[Selection] Figure 5

Description

  The present invention relates to a technique for generating boundary shape data such as an interface.

  In recent years, in the numerical analysis methods dealing with boundaries, such as fluid analysis, with the rapid progress of computers, the orthogonal lattice method that has been known for a long time has been refocused as a method suitable for large-scale computation. The cut cell method is known as one of the powerful methods for generating the boundary shape data. In particular, Non-Patent Document 1 discloses a cut cell method for handling a boundary shape in a two-dimensional space.

  In the cut cell method disclosed in Non-Patent Document 1, first, a boundary cell (boundary is a boundary cell) is selected from a set of cells (regions made up of rectangles partitioned by a lattice) generated by orthogonal lattices having a uniform interval. A cell passing through (a state where the boundary passes through the cell means a state where the boundary intersects with a ridge line or a vertex forming the outline of the cell). This detection reveals boundary cells and non-boundary cells (cells through which no boundary passes) in the cell set. Next, the boundary cell detected by the above detection is collated with a basic pattern prepared in advance. FIG. 2 is a diagram illustrating an example of a basic pattern.

  A basic pattern is a pattern of boundary cells counted up in advance based on a certain assumption. Conventionally, it is implicitly assumed that a boundary cut out by an appropriately sized cell is expressed by a single line segment, A basic pattern is created by counting up all the boundary cell patterns that can be considered under the assumption. This basic pattern consists of information on the connection of multiple intersections existing inside the boundary cell and information on whether the cell fragment divided by the boundary belongs to the inside or outside of the boundary (hereinafter, the above two pieces of information are combined). Called boundary cell information).

  As a result of the collation, when the boundary cell and the basic pattern are matched, the basic cell reveals the boundary cell information regarding the boundary cell. If no match is found between the border cell and the basic pattern, the border cell is divided and re-matched. The above division is repeated until a match is found within a predetermined upper limit of the number of divisions.

  Using the above cut cell method, for each boundary cell, find the intersection between the edge of the boundary cell and the boundary.If boundary cell information is used, the boundary is defined using the line segment that has the intersection as a component. Approximate expression.

  When the input boundary shape data has a shape such as 301 and 302 shown in FIGS. 3A and 3B, a plurality of boundaries exist in one cell, and thus cannot be processed by the above method. However, it is known that approximate processing can be obtained as indicated by 311 and 312 by performing a process called blunting (cutting off the tip) disclosed in Non-Patent Document 2, respectively.

As is clear from FIG. 3, in the case of FIG. 3A, the above processing is performed only on the cell of interest, and in the case of FIG. 3B, blunting is executed using information on neighboring cells.
JJ Quirk, “An alternative to unstructured grids for computing gas dynamic flows around arbitrarily complex two-dimensional bodies”, Computers Fluids, Vo. 23, No. 1, pp. 125-142, 1994. JJ Quirk, “A CARTESIAN GRID APPROACH WITH HIERARCHICAL REFINEMENT FOR COMPRESSIBLE FLOWS”, NASA CR-94938 ICASE Report, No. 94-51, pp. 23, June 1994.

  However, the conventional two-dimensional cut cell method has the following three problems.

  1. When the shape of the boundary is complicated, the boundary cell is divided many times and the enormous number of cells generated as a result is used, so that the calculation load in the numerical analysis increases.

  2. When there is a boundary cell (thin shape, sharp shape, etc.) that does not match the basic pattern as shown in FIG. Alternatively, parameters for generating a lattice (upper limit of the number of divisions, etc.) must be corrected.

  3. When the upper limit of the predetermined number of divisions is reached, if there is a shape having a sharp portion, complicated blunting processing must be performed.

  The present invention has been made in view of the above problems, and is a technique for improving the above problems 1, 2, and 3. In particular, a shape having a sharp portion that has been difficult in the prior art, and a shape having a small thickness. An object of the present invention is to provide a technique for easily generating boundary shape data even when a complicated shape is used as a boundary.

  In order to achieve the object of the present invention, for example, an image processing apparatus of the present invention comprises the following arrangement.

That is, setting means for setting a plurality of regions in a two-dimensional virtual plane;
Dividing means for dividing the two-dimensional virtual plane into a plurality of rectangular regions;
A selection means for selecting a boundary rectangular area including a boundary portion between the areas set by the setting means from the rectangular area group obtained by the dividing means;
First calculation means for obtaining a positional relationship with each of the vertices constituting the boundary rectangular area selected by the selection means with the boundary portion in the boundary rectangular area;
Second calculation means for obtaining an intersection position between a vertex or a ridge line constituting the boundary rectangular area and the boundary portion in the boundary rectangular area;
The positional relationship between each vertex constituting the boundary rectangular area and the boundary part in the boundary rectangular area, and the intersection position of the vertex or ridge line constituting the boundary rectangular area and the boundary part in the boundary rectangular area And identifying a portion belonging to the region set by the setting means in the boundary rectangular region and a portion not belonging to the boundary rectangular region, so that the pattern of the boundary rectangular region is a plurality of types of patterns created in advance. And determining means for determining which pattern corresponds to the pattern.

  In order to achieve the object of the present invention, for example, an image processing method of the present invention comprises the following arrangement.

That is, a setting step for setting a plurality of regions in a two-dimensional virtual plane;
A dividing step of dividing the two-dimensional virtual plane into a plurality of rectangular regions;
A selection step of selecting a boundary rectangular region including a boundary portion between the regions set in the setting step among the rectangular region group obtained in the dividing step;
A first calculation step for obtaining a positional relationship with each of the vertices constituting the boundary rectangular region selected in the selection step with the boundary portion in the boundary rectangular region;
A second calculation step for obtaining an intersection position between a vertex or a ridge line constituting the boundary rectangular area and the boundary portion in the boundary rectangular area;
The positional relationship between each vertex constituting the boundary rectangular area and the boundary part in the boundary rectangular area, and the intersection position of the vertex or ridge line constituting the boundary rectangular area and the boundary part in the boundary rectangular area By using the boundary rectangular area to identify the part that belongs to the area set in the setting step and the part that does not belong to the boundary rectangular area, the pattern of the boundary rectangular area is a plurality of patterns created in advance. And a determining step for determining which pattern corresponds to the pattern.

  The above problems 1, 2, and 3 can be improved by the configuration of the present invention. In particular, it is possible to easily generate boundary shape data even when a complicated shape such as a shape having a sharp portion or a thin shape, which has been difficult in the past, is used as a boundary.

  Hereinafter, the present invention will be described in detail according to preferred embodiments with reference to the accompanying drawings.

  FIG. 4 is a block diagram illustrating a hardware configuration of a computer that functions as an image processing apparatus that executes each process described below.

  Reference numeral 401 denotes a CPU that controls the entire computer using programs and data loaded in the RAM 404 and executes each process described below performed by the computer.

  A display device 402 includes a CRT, a liquid crystal screen, and the like, and displays a processing result by the CPU 401 using an image or a character.

  Reference numeral 403 denotes an input device, which includes a keyboard, a mouse, and the like. Various instructions can be input to the CPU 401 by an operator of the computer.

  Reference numeral 404 denotes a RAM, an area for temporarily storing programs and data loaded from the external storage device 405, an area for temporarily storing programs and data received from the outside by the communication device 406, and a CPU 401. Various areas such as a work area used when executing various processes can be provided as appropriate.

  Reference numeral 405 denotes an external storage device, which is a large-capacity information storage device typified by a hard disk drive device. These are stored, loaded into the RAM 404 under the control of the CPU 401, and are processed by the CPU 401.

  A communication device 406 performs data communication with an external device via a network such as a LAN or the Internet. Some or all of programs and data stored in the external storage device 405 are: The communication device 406 may appropriately receive from an external device and transfer it to the RAM 404.

  A bus 407 connects the above-described units.

  Next, a case where calculation processing such as fluid dynamics calculation is performed on a virtual two-dimensional plane will be described. As described above, when such a calculation process is performed on a virtual two-dimensional plane, first, a plurality of areas such as a fluid internal area and an external area are set on the two-dimensional virtual plane. There is a need. Setting a plurality of regions in this way is equivalent to setting a boundary (interface) between the regions at the same time.

  Next, the two-dimensional virtual plane in which a plurality of areas are set is divided into a plurality of rectangular areas. In that case, some rectangular regions include a boundary. In the following description, if there is a plurality of divided rectangular areas including a boundary portion, processing for approximating the boundary portion in the rectangle linearly is performed.

  FIG. 5 is a flowchart of such processing. Note that programs and data for causing the CPU 401 to execute the processing according to the flowchart of FIG. 10 are stored in the external storage device 405, which is appropriately loaded into the RAM 404 under the control of the CPU 401, and the CPU 401 uses the processing. By executing this, the computer executes each process described below.

  First, data (boundary shape data) defining each region set on the two-dimensional virtual plane is loaded from the external storage device 405 to the RAM 404 (step S500). For example, when performing a fluid analysis calculation process that handles an interface between a solid and a fluid on a two-dimensional virtual plane, information on the inside and outside of the boundary is required, such as solid inside and fluid outside. Therefore, the boundary shape data indicates the shape of the boundary, and indicates which side is the inner side and which side is the outer side with respect to the boundary. In the present embodiment, the boundary shape data is defined by a combination of implicit functions.

For example, in the circle shown in FIG. 6, the inner Din of the circular region is defined as Din = {(x, y) | x ² + y ² −1 <0}, and the outer Dout of the circular region is Dout = {(x, y ) | X ² + y ² −1> 0}.

In addition, in the triangular area shown in FIG. 7, the internal area Din is an inequality logical operation expression (y−2x−1 <0) ０ (y + 2x−1 <0) ∩ (y>) in consideration of a programming language such as C language. 0)
It is therefore defined.

  In this way, the region internal Din has three sets Ain = {(x, y) | y-2x-1 <0}, Bin = {(x, y) | y + 2x-1 <0}, Cin = {(x , Y) | y> 0} is defined by the logical product Ai∩Bin∩Cin.

  On the other hand, the external Dout of the triangular area shown in FIG. 7 is Aout = {(x, y) | y−2x−1> 0}, Bout = {(x, y) | y + 2x−1> 0}, Cout = It is defined by the logical sum Aout∪Bout∪Cout of {(x, y) | y <0}.

Further, a triangular area D shown in FIG. 7 is defined by ^c (Din∪Dout). Here, ^c (A) represents a complement of the set A.

  The expression of the boundary shape by the logical operation of such an inequality can be easily realized by using a conditional expression and a true / false value prepared in a programming language such as C language.

  In this way, the boundary shape data indicating the shape of the boundary of each region set on the two-dimensional virtual plane and whether each position on the two-dimensional virtual plane is located inside / outside the region is stored in the RAM 404. Load it.

  Next, the two-dimensional virtual plane is divided into a plurality of rectangular areas (step S501). That is, by arranging lattice points in a lattice shape on the two-dimensional virtual plane, the two-dimensional virtual plane is divided for each region (rectangular region) surrounded by the lattice points. The vertical and horizontal sizes of the rectangular area are not particularly limited.

  FIG. 8 is a diagram illustrating an example of a part of a two-dimensional virtual plane divided into a plurality of rectangular regions. In the figure, reference numeral 800 denotes a part of the two-dimensional virtual plane, and the two-dimensional virtual plane is divided into a plurality of rectangular areas as shown in the figure. In the figure, reference numeral 803 denotes a boundary, which is defined by the boundary shape data.

  In the figure, reference numeral 802 denotes a rectangular region through which the boundary 803 passes (rectangular region including the boundary portion 803), and reference numeral 801 denotes a rectangular region through which the boundary 803 does not pass (rectangular region not including the boundary portion 803). It is. Here, the rectangular area including the boundary portion is a rectangular area where there are intersections between ridgelines and vertices forming the outline of the rectangular area and the boundary portion. Hereinafter, the rectangular area including the boundary portion is referred to as a boundary rectangular area.

  Returning to FIG. 5, next, the respective rectangular areas are sequentially referred to (step S502), and it is determined whether or not the referenced rectangular area is a boundary rectangular area (step S503). Here, a process for determining whether or not the rectangular area is a boundary rectangular area will be described.

  For example, there is a method of using the number of intersections between all the ridgelines constituting the boundary rectangular area and the boundary. When the boundary passes over the vertex of the boundary rectangular area, or when the tip of the boundary touches the edge of the boundary rectangular area from the outside of the boundary rectangular area, it is the case with the minimum number of intersections. Is 1. Of course, the number of intersections of the non-boundary rectangular areas is zero.

  On the other hand, the maximum value of the number of intersections in the rectangular area is infinite because it depends on the complexity of the boundary shape and the size of the rectangular area.

  Therefore, when the number of intersections between the ridge line and the boundary of the rectangular area of interest is N, if N> 0, the rectangular area of interest is a boundary rectangular area; otherwise, it is a non-boundary rectangular area. Determine. Note that the processing for determining whether or not the rectangular area is a boundary rectangular area is not limited to this.

  Therefore, if it is determined in step S503 that the rectangular area referred to in step S502 is a non-boundary rectangular area, the process proceeds to step S507. If there is a rectangular area that has not yet been referenced, the process proceeds to step S502. Then, the subsequent processing is performed for the next rectangular area. On the other hand, if it is determined in step S503 that the rectangular area referred to in step S502 is a boundary rectangular area, the process proceeds to step S504, and thereafter, the rectangular area referred to in step S502 is divided. In S504, it is determined whether or not the number of divisions has reached a predetermined number.

  Here, the division of the boundary rectangular area is to recursively divide one boundary rectangular area as shown in FIG. In the figure, the division is performed in the quadtree division step. Therefore, in step S504, in the case of FIG. 18, it is determined whether or not the current division has reached the depth of the hierarchy in the quadtree.

  If the number of divisions of the boundary rectangular area has not reached the predetermined number in step S504, the process proceeds to step S508, the boundary rectangular area is divided, and the processes in and after step S502 are performed for each divided boundary rectangular area. Do.

  On the other hand, if the boundary rectangular area has been divided a predetermined number of times in step S504, the process proceeds to step S505, and among the plurality of basic patterns stored in the external storage device 405, the divided boundary rectangular area. To which basic pattern corresponds (closest). Although the determination in step S505 is performed after the necessary number of divisions in step S508 here, the determination in step S505 may be performed before or every time the image is divided.

  Here, in the present embodiment, it is assumed that the shape of the boundary portion included in the boundary rectangular area (divided boundary rectangular area) is expressed by two or less line segments. Therefore, the basic pattern indicates a boundary rectangular area including boundary portions of various shapes that satisfy such an assumption. Such a basic pattern is created in advance and stored in the external storage device 405 as data.

  FIG. 9 is a flowchart of processing for creating such a basic pattern. The process according to the flowchart of FIG. 5 is performed in advance before the execution of the process according to the flowchart shown in FIG. 5 as described above.

  Step 1: Count all cases where one line segment exists in the rectangular area. This includes patterns that match when rotated clockwise by 0 °, 90 °, 180 °, and 270 °.

  Step 2: Patterns that coincide when rotated clockwise by 0 °, 90 °, 180 °, and 270 ° with respect to the pattern group counted in Step 1 are collected as one pattern.

  Step 3: A pattern through which two line segments pass is created from all combinations selected one by one from the two types of pattern groups obtained in Step 1 and Step 2.

Step 4: As for the patterns in which the line segments may intersect among the pattern group created in Step 3, as shown in FIG.
(Situation 1) Case where two line segments intersect (Situation 2) Case where two line segments do not intersect (Situation 3) The case where two line segments intersect on the ridgeline is divided.

  Step 5: Considering that the boundary is given in the area of the inequality logical operation expression, (Situation 1) is divided into four patterns as in the example shown in FIG.

  The basic pattern group as shown in FIG. 12 is obtained by collecting the pattern groups of the boundary rectangular areas counted in the above order. FIG. 12 is a diagram illustrating an example of a basic pattern group used in the present embodiment. In the example shown in the same figure, the rotation objectivity in each basic pattern is summarized.

  Next, a process for determining which basic pattern the divided boundary rectangular area matches will be described in detail.

  First, in the divided boundary rectangular area, a process of specifying a part belonging to the inner side and a part belonging to the outer side of the area indicated by the boundary shape data is performed.

  For this purpose, first, it is checked whether each of the four vertices constituting the divided boundary rectangular area belongs to the inside, the outside, or the boundary of the area defined by the boundary shape data.

  For example, as shown on the left side of FIG. 13A, when the positional relationship between the divided boundary rectangular area 1301 and the area 1302 is in the state shown in the figure, the four constituting the divided boundary rectangular area are shown on the right side of the figure. Among the vertices, three vertices (vertices indicated by white circles) other than the vertices at the upper left corner (vertices indicated by black circles) are included inside the region 1302, and only the vertices at the upper left corner are located outside the boundary 1302.

  There are various methods for checking whether each vertex belongs to the inside, outside, or on the boundary of the region defined by the boundary shape data, but in this embodiment, the boundary shape data is Since the inequality logical operation expression for defining the region is used, an arbitrary coordinate position is assigned to the left side of the inequality, and this arbitrary coordinate is determined depending on whether the result is positive or negative or 0. It can be checked whether the position belongs to the inside, the outside, or the boundary of the region defined by the boundary shape data. Then, a value indicating whether the vertex belongs to the inside, the outside, or the boundary of the area defined by the boundary shape data is set for this vertex.

  In the present embodiment, when the vertex is located inside the area defined by the boundary shape data, “0” is set for this vertex, and when the vertex is located outside, “1” is set for this vertex. "Is set, and if it is located on the boundary," 2 "is set for this vertex. As a result, a value (hereinafter referred to as an inside / outside determination value) is set for each vertex constituting one division boundary rectangular area.

  With the above processing, it is possible to check whether each vertex constituting the divided boundary rectangular area belongs to the inside, the outside, or the boundary of the area defined by the boundary shape data.

  Further, as shown on the left side of FIG. 14A, when the positional relationship between the divided boundary rectangular area 1301 and the area 1302 is in the state shown in the figure (that is, the state shown on the left side of FIG. 13A), the divided boundary rectangular area As shown on the right side of the figure, two intersection points between the edge lines (including vertices) constituting the area and the boundary of the area 1302 are obtained.

  Therefore, when the positional relationship between the divided boundary rectangular area 1301 and the inner side of the area 1302 is as shown on the left side of FIG. 13A, one side is an area in the divided boundary rectangular area with a line segment connecting the intersections as a boundary. The inner side and the other side of 1302 can be defined as the outer side of the region 1302. One vertex located on one side with this line segment as the boundary has an inside / outside judgment value of “1”, and the three vertices located on the other side are Since the inside / outside determination value is “0”, it can be assumed that the upper left side is outside the region 1302 and the rest is inside the line segment as a boundary.

  Further, the positional relationship between the divided boundary rectangular area 1301 and the area 1302 may be as shown on the left side of FIG. 13B. In such a state, the divided boundary rectangular area 1301 is configured as shown on the right side of the figure. Among the four vertices, three vertices other than the vertex at the upper left corner are included inside the region 1302, and only the vertex at the upper left corner is located on the boundary of the region 1302.

  Further, the positional relationship between the divided boundary rectangular area 1301 and the inner side of the area 1302 may be considered as shown on the left side of FIG. 14B. In such a state, the edge lines (vertices) constituting the divided boundary rectangular area 1301 are considered. 3) are obtained as shown on the right side of FIG.

  In this way, it is possible to specify a part belonging to the inner side and a part belonging to the outer side of the area indicated by the boundary shape data in the divided boundary rectangular area.

  As indicated by reference numeral 1501 in FIG. 15, the positional relationship between the area 1508 indicated by the boundary shape data and the divided boundary rectangular area 1507 includes four vertices 1521 to 1524 constituting the divided boundary rectangular area 1507 as indicated by 1530. Among them, the vertices 1521 and 1524 are located outside the area 1508, the vertices 1522 and 1523 are located inside the area 1508, and the intersection points of the area 1508 and the divided boundary rectangular area 1507 are 1541 to 1544.

  On the other hand, as indicated by 1502, in the positional relationship between the areas 1510 and 1511 indicated by the boundary shape data and the divided boundary rectangular area 1507, as indicated by 1530, among the four vertices 1521 to 1524 constituting the divided boundary rectangular area 1507 , Vertices 1521 and 1524 are located outside the areas 1510 and 1511, and vertices 1522 and 1523 are located inside the areas 1511 and 1510, respectively, and intersections of the area 1510 and the divided boundary rectangular area 1507 are 1542 and 1543, The intersection points with the divided boundary rectangular area 1507 are 1541 and 1544.

  That is, even if the positional relationship between the area indicated by the boundary shape data and the divided boundary rectangular area is different as indicated by 1501 and 1502, the arrangement relation of the inside / outside determination values set at each vertex is the same. The intersection position is also the same. This makes it impossible to uniquely identify a portion belonging to the inside of the region indicated by the boundary shape data and a portion belonging to the outside in the divided boundary rectangular region.

  Therefore, as indicated by 1540, an additional point 1560 is newly provided at substantially the center of the divided boundary rectangular area, and the inside / outside determination processing performed for each vertex is performed on this additional point 1560. As a result, in the state indicated by 1501, it is determined that the additional point 1560 is “inside the area 1508”. On the other hand, in the state indicated by 1502, as indicated by 1550, this additional point 1560 is determined to be “outside of the areas 1510 and 1511”. As a result, even in different states such as 1501 and 1502, it is possible to uniquely identify the part belonging to the inside and the part belonging to the outside of the area indicated by the boundary shape data in the divided boundary rectangular area.

  FIG. 16 is a diagram showing processing for uniquely specifying the portion belonging to the inside and the portion belonging to the outside of the region indicated by the boundary shape data in the divided boundary rectangular region described above.

  In FIG. 16A, reference numeral 1601 denotes a divided boundary rectangular area, and reference numeral 1602 denotes an area indicated by the boundary shape data. First, it is determined whether each vertex constituting the divided boundary rectangular area 1601 is located inside the area 1602, located outside, or located on the boundary of the area 1602. As a result, only the top left corner vertex is located outside the area 1602, and the remaining three vertices are located inside the area 1602, so the inside / outside determination value “2” is set for the top left corner vertex, An inside / outside determination value “1” is set for each of the remaining three vertices.

  Next, the intersection point between the edge (including the vertex) of the divided boundary rectangular area 1601 and the area 1602 is obtained. As a result, two intersection points are obtained. Accordingly, the pattern indicating the part belonging to the inside of the area 1602 and the part not belonging to the inside of the area 1602 in the divided boundary rectangular area 1601 according to the arrangement relation of the inside / outside determination value and the intersection position is the pattern indicated by 1610, that is, as shown in FIG. Of the basic patterns, it matches the pattern (k). Thereby, it is possible to determine which basic pattern the divided boundary rectangular area 1601 matches.

  On the other hand, in FIG. 16B, reference numeral 1601 denotes a divided boundary rectangular area, and reference numeral 1603 denotes an area indicated by the boundary shape data. First, it is determined whether each vertex constituting the divided boundary rectangular area 1601 is located inside the area 1603, located outside, or located on the boundary of the area 1603. As a result, only the vertices at the upper left corner and the lower right corner are located outside the area 1603 and the remaining two vertices are located inside the area 1603. Therefore, the inside / outside determination value “ 2 ”is set, and an inside / outside determination value“ 1 ”is set for each of the remaining two vertices. Next, the intersection of the edge (including the vertex) of the divided boundary rectangular area 1601 and the area 1603 is obtained. As a result, four intersection points are obtained.

  However, in such a case, the part belonging to the inside of the area 1603 and the part not belonging to the inside of the area 1603 in the divided boundary rectangular area 1601 cannot be uniquely specified only by the arrangement relation of the inside / outside determination value and the intersection position. Therefore, in such a case, an additional point is provided at a substantially central portion of the divided boundary rectangular area 1601, and the inside / outside determination process is performed for this additional point. As a result, it can be determined that the additional point is located inside the area 1603, and therefore, the inside / outside determination value “1” is set for the additional point. As a result, the pattern indicating the part belonging to the inside of the area 1603 and the part not belonging to the area 1603 in the divided boundary rectangular area 1601 matches the pattern indicated by 1620, that is, the pattern (o) of the basic patterns shown in FIG. . Thereby, it is possible to determine which basic pattern the divided boundary rectangular area 1601 matches.

  If the division boundary rectangular area does not match any basic pattern, it is determined that the size of the division boundary rectangular area generated by the number of divisions specified in advance is not appropriate for the boundary shape, and Display a warning message to the effect and exit.

  Returning to FIG. 5, when the basic pattern that matches the division boundary rectangular area is determined in step S505, the process proceeds to step S506, and the division boundary rectangular area has the basic pattern that matches this, and is connected to the intersection and inside the boundary. Since the outside is clear, oriented line segment data to be described later is created (step S506).

  That is, data of line segments connecting the intersections is created. It is assumed that this line segment is oriented. That is, it is assumed that the line segment constituted by the points v1 and v2 existing in the two-dimensional space is described as [v1v2]. Accordingly, the line segment constituted by the points v1 and v2 existing in the two-dimensional space is described as [v1v2], thereby defining the right as the outside and the left as the inside when going from the point v1 to the point v2.

  In FIG. 17, if 1700 is a point v1, and 1701 is a point v2, the upper side is the inside and the lower side is the outside. The data defining the line segment generated in this way (for example, composed of ordered line segment components such as v1v2) is hereinafter referred to as line segment data.

  Then, the process proceeds to step S507, and if there is a rectangular area (or divided boundary rectangular area) that has not been referred to yet, the process returns to step S502, and the subsequent processes are performed for the next rectangular area (or divided boundary rectangular area). However, if all rectangular areas (or divided boundary rectangular areas) are referred to, this processing is terminated.

  By the processing described above, a boundary portion in one divided boundary rectangular area can be represented by a line segment, so that one line segment data can be created for one divided boundary rectangular area.

  Next, the shape of the region obtained by the above-described processing when the region indicated by the boundary shape data is a region represented by the following expression will be described.

(Y−1.2x + 0.1> 0) ∩ (y−0.8x−0.1 <0) ∩
(Y−0.8x + 0.1> 0) ∩ (y−1.2x−0.1 <0) ∩
(Y + 1.2x + 0.1> 0) ∩ (y + 0.8x−0.1 <0) ∩
(Y + 0.8x + 0.1> 0) ∩ (y + 1.2x−0.1 <0)
FIG. 20 is a diagram illustrating a region represented by such an expression. In the figure, the dotted line portion is a straight line when each inequality is an equation, and the region surrounded by the solid line portion is the region indicated by the above equation. When such a region is set on a two-dimensional virtual plane, and then the two-dimensional virtual plane is divided into rectangular regions, a corresponding basic pattern is determined for the boundary rectangular region, and the boundary rectangular region is expressed by the basic pattern. As a result, an area having the shape shown in FIG. 1 is obtained.

  That is, it is difficult to generate boundary shape data by a conventional method for a complicated shape such as a shape represented by a polygon having a sharp point, but according to this embodiment, it is easily realized. The

  Further, by performing the process shown in FIG. 19 on the line segment data obtained by the above process, line segment data restricted when one straight line passes through the rectangular area as in the conventional method can be created. it can. In step S1900 in the figure, a pattern in which one line segment shown in FIG. 2 passes is used as a basic pattern.

  Also, an object of the present invention is to supply a recording medium (or storage medium) in which a program code of software that realizes the functions of the above-described embodiments is recorded to a system or apparatus, and the computer (or CPU or Needless to say, this can also be achieved when the MPU) reads and executes the program code stored in the recording medium. In this case, the program code itself read from the recording medium realizes the functions of the above-described embodiment, and the recording medium on which the program code is recorded constitutes the present invention.

  Further, by executing the program code read by the computer, not only the functions of the above-described embodiments are realized, but also an operating system (OS) running on the computer based on the instruction of the program code. It goes without saying that a case where the function of the above-described embodiment is realized by performing part or all of the actual processing and the processing is included.

  Furthermore, after the program code read from the recording medium is written into a memory provided in a function expansion card inserted into the computer or a function expansion unit connected to the computer, the function is based on the instruction of the program code. It goes without saying that the CPU or the like provided in the expansion card or the function expansion unit performs part or all of the actual processing and the functions of the above-described embodiments are realized by the processing.

  When the present invention is applied to the recording medium, program code corresponding to the flowchart described above is stored in the recording medium.

20 is a diagram showing a region having a shape when the region shown in FIG. 20 is set on a two-dimensional virtual plane, and then the two-dimensional virtual plane is divided into rectangular regions, and then the boundary rectangular region is expressed with a corresponding basic pattern. It is. It is a figure which shows the example of a basic pattern. It is a figure which shows the example of the shape which boundary shape data shows. It is a block diagram which shows the hardware constitutions of the computer which functions as an image processing apparatus. FIG. 10 is a flowchart of a process for linearly approximating a boundary part in a rectangle when there is a part including a boundary part among a plurality of divided rectangular areas. It is a figure which shows the example which the shape which boundary shape data shows, and its inside and outside. It is a figure which shows the example which the shape which boundary shape data shows, and its inside and outside. It is a figure which shows the example of a part of two-dimensional virtual plane divided | segmented into the several rectangular area. It is a flowchart of the process for creating a basic pattern. It is a figure which shows the example of the pattern which a line segment may cross | intersect. It is a figure which shows four patterns divided | segmented by step 5. FIG. It is a figure which shows the example of the basic pattern group used by embodiment of this invention. FIG. 10 is a diagram for explaining the positional relationship between each vertex of a divided boundary rectangular area 1301 and an area 1302. FIG. 10 is a diagram for explaining the positional relationship between each vertex of a divided boundary rectangular area 1301 and an area 1302. It is a figure which shows the intersection of the ridgeline of the division | segmentation boundary rectangular area | region 1301, and the area | region 1302. FIG. It is a figure which shows the intersection of the ridgeline of the division | segmentation boundary rectangular area | region 1301, and the area | region 1302. FIG. It is a figure which shows the arrangement | positioning relationship of the inside / outside determination value set to each vertex, and an intersection position when the positional relationship between the area | region which boundary shape data shows, and a division | segmentation boundary rectangular area is respectively different. It is a figure which shows the process for specifying uniquely the part which belongs to the inner side of the area | region which boundary shape data shows, and the part which belongs to the outer side in a division | segmentation boundary rectangular area. It is a figure explaining line segment data. It is a figure explaining division | segmentation of a boundary rectangular area | region. It is a flowchart of the process for producing the line segment data restrict | limited when one straight line passes in a rectangular area. It is a figure which shows the example of the shape of an area | region.

Claims (7)

Setting means for setting a plurality of regions in a two-dimensional virtual plane;
Dividing means for dividing the two-dimensional virtual plane into a plurality of rectangular regions;
A selection means for selecting a boundary rectangular area including a boundary portion between the areas set by the setting means from the rectangular area group obtained by the dividing means;
First calculation means for obtaining a positional relationship with each of the vertices constituting the boundary rectangular area selected by the selection means with the boundary portion in the boundary rectangular area;
Second calculation means for obtaining an intersection position between a vertex or a ridge line constituting the boundary rectangular area and the boundary portion in the boundary rectangular area;
The positional relationship between each vertex constituting the boundary rectangular area and the boundary part in the boundary rectangular area, and the intersection position of the vertex or ridge line constituting the boundary rectangular area and the boundary part in the boundary rectangular area And identifying a portion belonging to the region set by the setting means in the boundary rectangular region and a portion not belonging to the boundary rectangular region, so that the pattern of the boundary rectangular region is a plurality of types of patterns created in advance. An image processing apparatus comprising: a determining unit that determines which pattern corresponds to the pattern.   After determining the intersection between the vertex or ridge line constituting the rectangular area of the pattern determined by the determining means and the portion corresponding to the boundary portion in the rectangular area, a line segment connecting the intersections is obtained. The image processing apparatus according to claim 1.   The first calculating means is located on the boundary portion in the rectangular area for each vertex constituting the rectangular area selected by the selecting means or inside or outside the area set by the setting means. The image processing apparatus according to claim 1, wherein a value corresponding to whether it is located is obtained.   The determining means includes an arrangement of values obtained by the first calculating means for each vertex constituting the rectangular area selected by the selecting means, and a vertex or ridge line constituting the rectangular area and the boundary in the rectangular area A pattern of the rectangular region is created in advance by specifying a portion belonging to the region set by the setting means and a portion not belonging to the rectangular region using the intersection position with the portion. The image processing apparatus according to claim 3, wherein a pattern corresponding to one of a plurality of types of patterns is determined. A setting step for setting a plurality of regions in a two-dimensional virtual plane;
A dividing step of dividing the two-dimensional virtual plane into a plurality of rectangular regions;
A selection step of selecting a boundary rectangular region including a boundary portion between the regions set in the setting step among the rectangular region group obtained in the dividing step;
A first calculation step for obtaining a positional relationship with each of the vertices constituting the boundary rectangular region selected in the selection step with the boundary portion in the boundary rectangular region;
A second calculation step for obtaining an intersection position between a vertex or a ridge line constituting the boundary rectangular area and the boundary portion in the boundary rectangular area;
The positional relationship between each vertex constituting the boundary rectangular area and the boundary part in the boundary rectangular area, and the intersection position of the vertex or ridge line constituting the boundary rectangular area and the boundary part in the boundary rectangular area By using the boundary rectangular area to identify the part that belongs to the area set in the setting step and the part that does not belong to the boundary rectangular area, the pattern of the boundary rectangular area is a plurality of patterns created in advance. An image processing method comprising: a determining step for determining which pattern corresponds to the pattern.   A program causing a computer to execute the image processing method according to claim 5.   A computer-readable storage medium storing the program according to claim 6.

Images