JP3314744B2 - Mesh figure processing apparatus and mesh figure processing method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a mesh figure processing apparatus and a mesh figure processing method for extracting an outline of a mesh figure from a mesh figure and drawing the outline.

[0002]

2. Description of the Related Art Conventionally, a graphic such as elevation data or a distribution map of geographic information is divided into uniform square mesh units, and grid points (vertices) of a mesh to which the graphic belongs are acquired.
A mesh figure processing method or a mesh figure processing apparatus for managing the vertex data is known. For example, when displaying the mesh figure, the vertex data (ie,
A figure may be drawn by drawing a line segment so as to sequentially connect mesh points (mesh points).

[0003]

By the way, in the prior art, it is assumed that the contour extracted from the mesh figure has a small number of vertices and that the drawing speed does not significantly affect the processing speed. Therefore, in a figure having a large number of constituent vertices, such as a contour line obtained by extracting the contour of mesh data of a geographic information system or the like, there is a problem that the processing speed is reduced if the drawing is performed as it is because the number of vertices is large. Also, when managing contour lines as data,
Unless data thinning, compression, and the like are considered, there is a problem that the data storage capacity increases.

The present invention has been made in view of the above-mentioned circumstances, and reduces the number of vertices of a contour line, thereby reducing the amount of data and increasing the processing speed. It is an object to provide an apparatus and a mesh figure processing method.

[0005]

According to a first aspect of the present invention, there is provided a mesh figure processing apparatus for extracting an outline from a mesh figure.
Approximating means for taking the midpoint of adjacent intersection points between the contour and the mesh grid points, approximating the contour with a line connecting the midpoints, and contouring approximated by the approximating means. Management means for managing , the approximation means,
If the midpoint is located on a straight line, the midpoint and end point of the starting point
Is characterized in that one side of the outline is represented only by the middle point .

Further, according to the invention described in claim 2, according to claim 1,
In the mesh figure processing device described in the above, a rectangular area obtaining means for obtaining a rectangular area including the contour line approximated by the approximating means, a rectangular area obtained by the rectangular area obtaining means and a designated drawing area And a drawing means for drawing a contour line to be drawn in the drawing area, and a drawing means for drawing the contour line specified by the drawing contour line specifying means.

[0007]

[0008]

[0009]

[0010] In order to solve the above-mentioned problems,
According to the third aspect of the present invention, the outline of the mesh figure
In the mesh figure processing method for extracting
Extracting the contour from the shape; and
Obtaining an intersection with a mesh grid point;
The contour is approximated by a straight line connecting the midpoints of the intersections
The method comprising the steps of acquiring encompassing rectangular area of the approximated contour line, comprising the steps of: specifying a drawing area, on the basis of the rectangular area with the specified drawing region, a contour line to be drawn It possesses a step of drawing and identifying, the specified contour, the midpoint
When placed on a straight line, only the midpoint of the start point and the midpoint of the end point
Is used to represent one side of the contour line .

[0011] In the present invention, for a figure such as elevation data or distribution map of geographic information divided into uniform rectangular mesh units, the approximation means makes the contour line and the mesh grid point adjacent to each other. Taking the midpoint of the intersection, approximating the outline with a line connecting the midpoints,
The approximated contour is managed. In this way, by approximating the contour line, when there are many steps in the shape of a step, the number of vertices can be reduced, and the amount of data to be managed is reduced. Can be displayed at high speed because the number of vertices is small.

Further, a rectangular area including the outline approximated by the approximating means is obtained by the rectangular area obtaining means, and the obtained rectangular area and the designated drawing area are converted by the drawing outline specifying means. Based on this, the outline to be drawn is specified, and the specified outline is drawn by the drawing means. As described above, since the rectangular area including the approximated outline is acquired and the outline to be drawn is specified based on the rectangular area, the outline which is completely unrelated to the display area on the display is obtained. It is not necessary to display, and it is possible to eliminate display waste.

[0013]

Embodiments of the present invention will be described below with reference to the drawings. A. First, the principle of the present invention will be described. FIG. 1 is a conceptual diagram showing a certain target area divided into meshes. In the drawing, a portion surrounded by a broken line in the mesh is a contour extraction target portion, and it is considered that a contour of a figure composed of the whole mesh of the broken line is extracted. FIG. 2 is a conceptual diagram in which a part of a region S1 shown in FIG. 1 is enlarged. In the figure,
T1 to T6 are contour extraction lines L along the sides of the mesh figure.
This is the intersection between 1 and the grid point of each mesh. C1 is the midpoint between T1 and T2, C2 is T2 and T3, and C3 is T
3 and T4, C4 is the middle point between T4 and T5, and C5 is the middle point between T5 and T6. Considering a line passing through each of the middle points C1 to C5 instead of T1 to T6 forming the contour line L1, the line becomes the line L2. A line segment C1 connecting C1 and C5
Considering 1-C5, the relationship between line segment C1-C5 and points C1-C5 is examined.

FIG. 3 is a conceptual diagram for explaining the principle of approximating a contour line. FIG. 3 shows a single-stage width W,
A step-shaped continuous line having a uniform height and a height H is shown, and the vertices P (0) to P (n + 1) are respectively located at the midpoints of the steps. The coordinates of P (n) can be represented by the following equation. P (n) = (W / 2 + nW, nH)

The inclination tan θ when the angle between P (0) and P (n) is θ is tan θ = | W / 2 + nW-W / 2 | / | nH | = |
W / H |, which indicates that P (0) to P (n) exist on the same straight line.

Therefore, it is understood that C1 to C6 shown in FIG. 2 are also on the same line, and this line segment C1-C6
It can be seen that only C1 and C5 are necessary coordinate points to represent 5. As described above, coordinates passing through the grid points and the outline of each mesh are extracted, the midpoints of the coordinate points adjacent to the coordinate points are obtained, and the outline is approximated by the line passing through the midpoints. As shown in FIG. 7, when the shape is a step like P (0) to P (n), the number of vertices that need to be managed in order to represent the outline of the figure can be greatly reduced.

In FIG. 1, M1 to M18 are vertices necessary to represent the approximated contour. Here, as a display range for displaying the entire contour, a minimum rectangle surrounding the contour may be assumed, and the vertices N1 and N2 of the diagonal of the rectangle may be obtained. At this time, the vertex M
Vertices M1 are (XM1, YM1) to Vertex M18 are (XM18, YM18).
Then, the coordinates (XN1, YN1) of the vertex N1 are expressed as follows: XN1 = min {XM1 ... XM18} YN1 = max {YM1 ... YM18}

The coordinates (XN2, YN2) of the vertex N2 can be obtained as follows: XN2 = max {XM1... XM18} YN2 = min {YM1.

According to the present invention, when managing the vertices of the outline of a figure, the diagonal vertices N1 and N2 necessary to represent the smallest rectangle surrounding the outline are linked to the vertex data of the outline point. By doing so, when drawing a contour line, if it is determined whether or not the display area to be displayed overlaps the quadrangle represented by the diagonal vertices N1 and N2, that is, whether or not the display area overlaps the display range, the display to be displayed is performed. An outline not included in the region can be prevented from being drawn, and the time required for display can be reduced.

B. Configuration of Embodiment An embodiment of the present invention will be described with reference to the drawings. FIG. 4 is a block diagram showing a configuration example of the mesh figure processing apparatus according to the embodiment of the present invention. Referring to FIG. 1, the mesh figure processing apparatus includes a keyboard 1, a processing unit 2, a database 3, and a display 4. The keyboard 1 inputs commands for instructing the processing unit 2 of the mesh extraction graphic processing device to perform operations, various data, coordinate data relating to a display area to be displayed, and the like. The processing unit 2 extracts a contour line from a mesh figure, approximates the contour line, calculates the minimum vertex data required to display the approximated contour line, and displays the entire contour line. Calculation of display range data representing the minimum area for the display, specification of the outline to be displayed, display of the outline, and the like. The processing unit 2 includes an extraction unit 21, an intersection data creation unit 22, an approximated data creation unit 23, a contour display range data creation unit 24, and a contour data display unit 25. Each of the above means is a processing program constituted by software.

The extracting means 21 specifies an outline of the entire mesh figure to be extracted. The intersection data creating means 22 includes a contour extracting means 21 for the entire mesh.
The intersection between the extracted contour line and the mesh grid is obtained. The approximated data creating means 23 finds a midpoint between adjacent intersections according to the intersection data obtained by the intersection data creating means 22, and approximates the outline by connecting the midpoints. The minimum vertex data required to display is obtained and stored in the contour vertex data storage table 31.

Next, contour line display range data creating means 24
Is calculated for the contour line obtained by the approximated data creating means 23.
A display range for displaying the entire contour line, in other words, a minimum rectangle surrounding the contour line is obtained, and vertices (display range data) located on a diagonal line of the rectangle are stored in the display range data storage table 32. The contour data display means 25 specifies which part of the entire mesh figure is a display area to be displayed on the display 4, refers to the display range data in the display range data storage table 32, and displays the contour to be displayed. And reads the vertex data of the corresponding contour from the contour vertex data storage table 31,
Lines (contours) connecting the vertex data are displayed on the display 4.

The database 3 includes a contour line vertex storage table 31 and a display range data storage table 32. The contour vertex storage table 31 stores the vertex data of the contour extracted and approximated from the entire mesh figure to be extracted. The display range data storage table 32 stores vertices (display range data) located on the diagonal line of the smallest rectangle surrounding the extracted and approximated outline.

C. Next, the operation of the embodiment of the present invention will be described with reference to the drawings. FIG. 5 is a flowchart for explaining the operation of the embodiment of the present invention. First, the extraction means 21 specifies a target mesh whose contour is to be extracted from the mesh figure, and then specifies a side to be extracted as a contour (step S1). An intersection with the lattice is obtained in advance (step S2). For example, when there is a target mesh (hatched mesh) for which contour extraction is to be performed as shown in FIG. 8, the intersection between the contour lines of the illustrated areas A and B and the lattice point is set. ~ Ap22, for region B, the intersection bp1 ~
Find bp10.

Next, the approximated data creating means 23
In FIG. 5, a midpoint between adjacent intersection data is obtained for all the intersection data created in step S2 (step S3). In the example shown in FIG.
In p22, the midpoint of each adjacent intersection a1 = (ap1
+ Ap22) / 2, a2 = (ap1 + ap2) / 2, and midpoints a1 to a22 are obtained for all combinations.
Also at the intersection points bp1 to bp10, midpoints b1 to b10 of adjacent intersection points are obtained. Next, a straight line passing through the midpoint data created in step S3 in FIG. 5 is considered by the approximated data creating means 23, and vertex data necessary for displaying this straight line is stored in the contour line vertex data of the database 3. It is stored in the table 31 (step S4).

FIG. 6 is a flowchart for obtaining the vertices. First, in the contour area of interest, one piece of the obtained midpoint data is read (step S11), and the data is registered in the contour vertex data storage table 31 of the database 4 (step S12). Next, it is determined whether or not the read middle point data includes two or more next middle point data (step S13). If there is more than one, it is determined whether or not a total of three consecutive midpoint data of the read midpoint data and the next two midpoint data are on the same straight line (step S14). If they are on the same straight line, the second midpoint data (middle midpoint data among the three) is deleted from the three midpoint data (step S15). Subsequently, the next two midpoint data are taken out and it is similarly determined whether or not they are on the same straight line. If they are on the same straight line, the second midpoint data (middle of the three The process of deleting point data) is repeated (steps S13 to S15).

On the other hand, when two or more pieces of the next midpoint data do not exist, or when three pieces of the midpoint data do not exist on the same straight line, one vertex of the edge of the contour to be approximated by the midpoint data is used. Since the data has been obtained, it is determined whether or not all of the midpoint data has been read in the contour area of interest (step S16). If the processing has not been completed yet, the process returns to step S11, and the processing of obtaining (the vertex data of) the next side of the contour to be approximated by the next middle point is repeated (steps S11 to S16). on the other hand,
When all the midpoint data has been read, the process is terminated (or the process moves to the next contour area).

In the example shown in FIG. 8, the midpoints a1 to a22 of the area A
First, a1 is read and registered in the contour vertex data storage table 31 of the database 3. next,
For the midpoint a1, there are the following two midpoints a2 and a3,
It is determined whether the three midpoints of the midpoint a1 and the midpoints a2 and a3 are on the same straight line. In this example, since the midpoint a1 and the midpoints a2 and a3 exist on the same straight line, the midpoint a2 is deleted. Next, it is determined whether or not the three midpoints of the midpoint a1 and the next two midpoints a3 and a4 (the midpoint a2 has already been deleted) are on the same straight line. In this way, the determination whether or not the midpoint a1 is on the same straight line as the next two midpoints is repeated until the next two midpoints no longer exist.

The above processing proceeds, and the middle point a1 and the middle point shown in FIG.
When the determination is made for the three middle points a8 and a9, the middle point a1 and the middle points a8 and a9 are not on the same straight line. It is registered in the line vertex data storage table 31, and the determination on the same straight line is performed in the same manner. By this processing, the midpoints a1, a8, a11, a14, a17, a19, and a22 are registered as vertex data necessary for displaying the contour line in the area A in the contour line vertex data storage table 31 of the database 3. Will be. In the area B, by performing the same processing, the vertices are stored in the contour vertex data storage table 31 of the database 3 as the midpoints b1, b2, b5, b6, b7, b1.
0 will be registered as vertex data necessary for displaying the outline.

Next, contour line display range data creating means 24
In FIG. 5, according to the vertex data of the contour created in step S4, a diagonal vertex located at the diagonal of the smallest rectangle surrounding the contour is obtained as a display range when the entire contour is displayed. It is registered in the display range data storage table 32 of the database 3 as display range data (step S5).

In the example shown in FIG. 8, the vertices of the outline of the area A are a1, a8, a11, a14, a17, a19, and a22. When considering the coordinates in the X and Y directions, respectively. (Xa1,
Ya1), (Xa8, Ya8), (Xa11, Ya11), (Xa1
4, Ya14), (Xa17, Ya17), (Xa19, Ya19),
Assuming (Xa22, Ya22), the coordinates (Xas1, Yas1), (Xas1, Yas1) of the diagonal vertices as1, as2 of the smallest rectangle surrounding the contour line
2, Yas2): Xas1 = min1Xa1, Xa8, Xa11, Xa14, Xa17,
Xa19, Xa22｝ Yas1 = max ｛Ya1, Ya8, Ya11, Ya14, Ya17,
Ya19, Ya22｝ Xas2 = max ｛Xa1, Xa8, Xa11, Xa14, Xa17,
Xa19, Xa22｝ Yas2 = min ｛Ya1, Ya8, Ya11, Ya14, Ya17,
Ya19, Ya22}. Coordinates (Xbs1, Ybs) of diagonal vertices bs1, bs2 of the smallest rectangle surrounding the outline of the area B
1) and (Xbs2, Ybs2) are similarly obtained.

When the coordinates obtained in steps S4 and S5 are stored in the database 3, a structure as shown in FIG. 9 is obtained. FIG. 9 is a conceptual diagram showing the data configuration of the contour vertex data storage table 31 and the display range data storage table 32 of the database 3. In the contour vertex data storage table 31, the vertex data is stacked and managed so that the order can be understood in the order of connecting the vertices of the contour. For example, regarding the contour line AL of the area A, a1 → a8 → a11 → a14
→ a17 → a19 → a22 or a22 → a19 → a17 → a14 → a11
→ a8 → a1 are stacked so that the ordering can be understood, and the outline BL of the area B is b1 → b2 → b5 → b6 → b7 → b1
It is stacked so that the ordering can be understood as 0 or b10 → b7 → b6 → b5 → b2 → b1. The display range data storage table 32 stores, for each of the outlines AL and BL, diagonal vertices of the smallest rectangle surrounding the outline as display range data.
as1, as2 and diagonal vertices bs1, bs2 are stored and managed.

Next, referring to FIG. 5, steps S1 to S5
Is displayed on the display 4 using the outline data created in the process (step S6). Here, FIG. 7 is a flowchart for displaying the outline data on the display 4. First, it specifies which of the mesh regions is to be displayed on the display 4 (step S21). Next, the display range data of each contour line is read from the display range data storage table 32 of the database 3 (step S22), and according to the display range data, whether or not the contour line is within the display area to be displayed on the display 4 is determined. That is, it is determined which contour line exists in the display area (step S23).

Next, based on the determination in step S23,
The vertex data of the contour that needs to be displayed is read from the contour vertex data storage table 31 of the database 3 and displayed on the display 4 (step S24).
Then, it is determined whether or not all the data in the display range data storage table 32 has been read (step S25). If not, the process returns to step S22, and the above processing is repeated to register the data in the database 3. Process is performed on all existing contour lines.

Here, a specific description will be given with reference to FIG. FIG. 10 shows a display 4 corresponding to the example shown in FIG.
It is a conceptual diagram which shows the display area displayed above. In FIG. 10, an area V surrounded by oblique lines is a display area to be displayed. Which contour is to be displayed depends on the area diagonal vertices vs1 and vs2 of the display area V displayed on the display 4 and the contour A
Based on the display range data as1 and as2 of L and the display range data bs1 and bs2 of the contour line BL, it is determined whether or not the display area V intersects with which display range (whether or not they overlap).
Is determined. In the illustrated example, since the display range of the outline AL and the display area V intersect, it is necessary to display the outline AL. Therefore, the vertex data a1, a8,
a11, a14, a17, a19, and a22 are extracted from the contour vertex data storage table 31 of the database 3, and the respective vertex data a1, a8, a11, a14, a17, a19, and a22 are sequentially connected, and the display 4 is connected. Display above. In this example, since the display range of the outline BL and the display area V do not intersect,
The contour line BL is not displayed.

D. Another Embodiment Next, another embodiment of the present invention will be described. Here, FIG. 11 is a block diagram showing a configuration of a mesh extraction graphic processing apparatus according to another embodiment of the present invention. In addition,
Components corresponding to those in FIG. 4 are denoted by the same reference numerals, and description thereof will be omitted. In the figure, a memory 40 is a storage medium that can be accessed at a higher speed than the database 3 and is created by the contour line display range data creating means 24 and once stored in the display range data storage table 32 of the database 3.
The diagonal vertices (display range data) of the smallest rectangle surrounding the contour line stored in the display area 4 are transferred to the display range data storage table 41 prior to the process of displaying on the display 4 and stored therein.

In the present embodiment, the diagonal vertices (display range data) of the smallest rectangle surrounding the contour described above have a relatively small data amount as compared with the vertex data of the contour. As described above, prior to the display, the coordinate data of the diagonal vertex (display range data) of the contour is read from the display range data storage table 32 of the database 3,
It is developed in the display range data storage table 41 of the memory 40 which can be accessed at higher speed.

In the actual display, first, which area of the mesh area is to be displayed on the display 4 is specified by the contour line data display means 25,
According to the display range data of each contour stored in the display range data storage table 41 of 0, it is determined which contour should be displayed, and the vertex data of the contour to be displayed is determined. What is necessary is just to read out from the contour vertex data storage table 31 of the database 3 and display it on the display 4. As described above, in the other embodiments, the diagonal vertices (display range data) indicating the display range of the outline, which must be referred to in the display determination, are in the memory 40, so that the determination process can be sped up. Can be displayed at high speed as a whole.

[0039]

As described above, according to the present invention,
Divided into uniform quadrilateral mesh units, for figures such as elevation data or distribution maps of geographic information, by approximation means, taking the midpoint of the adjacent intersection of the contour and the mesh grid point, The contour line is approximated by a line connecting the midpoints, and the management unit manages the approximated contour line, so by approximating the contour line,
When there are many steps, the number of vertices can be reduced, and the amount of data to be managed can be reduced. The advantage is that it can be Further, according to the present invention, since diagonal coordinates indicating the entire display range of the outline are also managed, the outline which has no relation to the display area on the display is not displayed, so that waste of display can be eliminated. The advantage that it can be obtained is obtained.

[Brief description of the drawings]

FIG. 1 is a conceptual diagram showing a certain target area divided into meshes.

FIG. 2 is a conceptual diagram in which a part of a target area is enlarged.

FIG. 3 is a conceptual diagram for explaining a principle of approximating a contour line.

FIG. 4 is a block diagram showing a configuration of a mesh figure processing apparatus according to an embodiment of the present invention.

FIG. 5 is a flowchart for explaining the operation of the present embodiment.

FIG. 6 is a flowchart illustrating an operation of storing approximate data of a contour line.

FIG. 7 is a flowchart illustrating an operation of displaying on a display using stored data.

FIG. 8 is a conceptual diagram for explaining approximation of a contour line for extracting a contour of a mesh figure and a display area.

FIG. 9 is a conceptual diagram showing an example of data management for a database.

FIG. 10 is a conceptual diagram showing a relationship between a display area displayed on a display 4 and a display range of a contour line.

FIG. 11 is a block diagram showing a configuration of a mesh figure processing apparatus according to another embodiment.

[Explanation of symbols]

Reference Signs List 1 keyboard 2 processing unit 3 database 4 display 21 extraction means 22 intersection data creation means 23 approximated data creation means (approximation means) 24 contour line display range data creation means (rectangular area acquisition means) 25 contour data display means (drawing) Contour line specifying means, drawing means) 31 contour line vertex data storage table (management means) 32 display range data storage table 40 memory 41 display range data storage table

Claims (3)

(57) [Claims] 1. A mesh figure processing apparatus for extracting an outline from a mesh figure, wherein a midpoint of an adjacent intersection between the outline and a mesh grid point is taken, and the outline is drawn by a line connecting the midpoints. Approximating means for approximating, and managing means for managing a contour line approximated by the approximating means, wherein the approximating means is configured such that when the midpoint is arranged on a straight line, A mesh figure processing apparatus characterized in that one side of a contour line is represented only by a middle point between a point and an end point. 2. A rectangular area obtaining means for obtaining a rectangular area including an outline approximated by the approximating means, and a rectangular area obtained by the rectangular area obtaining means and a designated drawing area. 2. A drawing contour specifying means for specifying a contour to be drawn in the drawing area, and a drawing means for drawing a contour specified by the drawing contour specifying means. Mesh figure processing equipment. 3. Extracting the outline from a mesh figure.
In the mesh figure processing method, a step of extracting an outline from the mesh figure and a step of obtaining an intersection between the outline and a mesh grid point.
And the straight line connecting the midpoints of adjacent intersections
Approximating, obtaining a rectangular area including the approximated outline, specifying a drawing area, and forming a contour to be drawn based on the rectangular area and the specified drawing area. If possess identifying a line, and a step of drawing the specified contour, wherein the midpoint is located on a straight line, the midpoint of the start and end points
It characterized in that only represent one side of the contour line at the midpoint
Serial placement of mesh graphics processing method.