JP2837243B2 - Graphic data compression method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (a) Industrial application field The present invention compresses graphic data in which a boundary line such as a shoreline is represented by a plurality of points to obtain graphic data having a small number of data. About the method.

(B) Summary of the Invention The graphic data extraction method according to the present invention is applied to, for example, extracting data of a chart displayed on a wake display device of a ship or the like. Generally, such chart data is stored in ROM, MT (magnetic tape), etc.
When displaying on an RT or the like, unnecessary data is thinned out and only unnecessary data is extracted and used.

The underlying chart data is stored in ROM, MT, etc. by digitizing the shorelines and contour lines of the printed chart using a digitizer.The display data storage capacity of the display device, drawing speed, and displayable pixels Abilities such as numbers,
It is necessary to extract and use only necessary data by thinning out data according to the display range.

According to the present invention, when compressing graphic data such as a marine chart, data can be efficiently compressed with a small number of data without losing necessary information as a boundary line.

(C) Conventional technology Conventionally, for example, in a wake display device in a ship,
When extracting data to be displayed from chart data stored in advance, data is extracted at regular intervals.

For example, if the total number of chart data is 40,000 and the number of points that can be displayed is 10,000, the chart data is extracted every four points. FIG. 7 is a diagram showing an example of conventional data extraction. In the figure, each point represents a point of the chart data stored in the ROM or MT in advance, and a double circle represents an extracted point. Extract data every 4 points as shown in the figure,
Display is performed based on this data.

(D) Problems to be Solved by the Invention However, such a conventional graphic data extraction method has the following problems.

First, there is a possibility that an island or the like composed of points equal to or less than the points thinned out from the chart data may disappear. In addition, there is a possibility that parts protruding into the sea, such as the tip of a cape, may disappear. Furthermore, the error between the original chart data and the extracted data cannot be grasped quantitatively.

In view of this, the applicant has filed an application in Japanese Patent Application No. 61-295486 regarding a graphic data extraction method for compressing data in conformity with graphic data. According to the earlier application, as a result, points where the change is rapid are densely extracted, and portions where the change is gradual are sparsely extracted.

By the way, for example, chart data is used in a device related to navigation assistance in a ship or the like. However, depending on the purpose of use, not only high graphic accuracy is simply required. For example, if the approximate straight line obtained by thinning out the points that make up the coastline passes on the land side from the actual coastline, the land that is originally land is represented as the sea, which is dangerous for the navigation of ships. A chart without such a thing is required. In the example shown in FIG. 7, the shoreline represented by the straight line L1 between the points 1-5 and the straight line L2 between the points 5-9 actually passes through the land, so that the hatched portion corresponds to the sea. Will be considered.

An object of the present invention is to compress a graphic data in which a boundary line such as a shoreline is represented by a plurality of points so that an approximate straight line passes through only one of two regions divided by the boundary line. To provide a method of compressing graphic data.

(E) Means for Solving the Problems The present invention is a graphic data compression method for obtaining graphic data having a small number of data points by compressing graphic data representing a boundary line such as a coastline by a plurality of points. Approximate straight line extraction processing in which a point to be left as data among a plurality of points constituting a boundary line is set as an extraction point, and a tangent tangent to one side of the boundary line at the extraction point is obtained as an approximate line. An approximate point data generating process for setting the intersection of the two points as new approximate point data; and changing the extracted point position and the approximate point position to set a distance between a polygonal line formed by the extracted point and the approximate point and a boundary line in advance. And the matching point data extraction and generation processing within the range.

(F) Function In the graphic data compression method according to the present invention, the approximate line extraction processing is performed to select, among the plurality of points constituting the boundary line,
A point to be left as data is extracted, and a tangent at one side of the boundary at the extracted point is obtained as an approximate straight line. Further, the intersection of adjacent approximate straight lines is obtained as new approximate point data by the approximate point data generation processing. Further, the extraction point position and the approximate point position are changed by the matching point data extraction generation processing, and the extraction point and the approximate point are set so that the distance between the bent line and the boundary line formed by the extraction point and the approximate point is within a predetermined distance. An approximate point is determined.

Specific examples of the above processes will be described with reference to FIG. In FIG. 1, reference numerals 1 to 29 denote graphic data representing the original boundary lines, and points 1, 2, 6, 8, 12, 14, 18, 19,
23 and 29 are obtained as extraction points, respectively, and the tangents to the sea side at these extraction points are obtained as approximate straight lines. In the approximate point data generation processing, intersections 4 ', 7', 10 ', 13', 21 ', and 25' between adjacent approximate straight lines are generated as new approximate point data. As described above, there is a deviation in each part between the bent line composed of the extraction point and the approximate point and the original boundary line, but the distance between the bent line and the boundary line is within the predetermined distance Ls by the matching point data extraction generation processing. The extraction point position and the approximate point position are changed so that

(G) Embodiment A specific example of the graphic data compression method according to the embodiment of the present invention is as follows.

In FIG. 1, each approximate straight line (approximate line segment) constituting the broken line indicated by 1-4'-7'-10'-13 '... Is constituted by a starting point, a passing point, and an ending point. In the example of FIG. 1, the starting point of the approximate straight line 1-4 'is 1, the passing point is 2, and the ending point is 4'.
And the starting point of the approximate straight line 4'-7 'is 4' and the passing point 6
Means that the end point is 7 '. Where point 4 'is point 1 and point 2
This is the position where the perpendicular is lowered from the point 4 with respect to the straight line connecting. Similarly, point 7 'is a position where a perpendicular line from point 7 to a straight line connecting point 4' and point 6 is lowered. Below 1
The same applies to 0 ', 13', 21 ', 25'. Hereinafter, these approximation points are indicated by adding '. The point where each approximate line touches the boundary of the chart (the “extraction point” according to the present invention) always passes through one point on the original chart data, and this point is referred to as a “passing point”. However, when the end point is on the original chart data, the passing point coincides with the end point.

Each of the approximate straight lines is obtained by first obtaining a passing point, then obtaining an end point, and using this end point as a starting point of the next approximate straight line, and thereafter repeating the same processing.

[How to find a passing point]

In FIG. 1, 4 'is the end point of the approximate straight line 1-4' obtained last time. The passing point of the approximate straight line starting from this point 4 'is obtained as follows.

A straight line is drawn from the starting point 4 'to, for example, the candidate passage point 7, and points 4 (not including 4 (4')) between the two points are included. And drop it to the vertical. Then find the length of each perpendicular and its sign,
It is determined whether or not all of these perpendiculars satisfy the following conditions. If point 7 is OK, point 8 is advanced. If point 8 is OK, point 9 is sequentially advanced. Pass candidate point when the point number of the original chart data has the maximum value,
In other words, the point before the point that is not OK for the first time is the passing point.

The sign of the length of the perpendicular must be positive (land side) or 0. In other words, the point of the original chart data is on the land side with respect to the approximate straight line.

The length of the perpendicular must be less than Ls. That is, the distance between the approximate straight line and the point of the original chart data is Ls or less.

For example, if 7 is a candidate for a passing point and a straight line is drawn from 4 ′ to 7 and there are 6 points on the sea side from this straight line, point 7 is inappropriate as a passing point. A point 6 which is one point before is set as a passing point.

In the above example, the pass point candidates were described as 7 or 6 from the beginning, but in actuality, starting from the original point of the start point 4 ', that is, the point 4, a straight line between the two points and a straight line between the two points exist. The distance to the other point and the sign thereof are obtained, and candidates for points to be passed are sequentially advanced until the above condition is not satisfied. The point immediately before that is set as a passing point. (When the point 5 does not satisfy the above conditions, the point 4 becomes a passing point.) [Method of calculating the end point] The passing point of the approximate straight line is determined by the above method. That is, it is a problem how to set the end point.

In the example of FIG. 1, a straight line having a starting point of 4 'and a passing point of 6 is an approximate straight line. First, a point 7 next to the passing point is set as an end point candidate point, and a perpendicular is drawn from this point to this straight line. , Are determined to be satisfied. If point 7 is OK, point 8 is advanced, if point 8 is OK, point 9 is advanced in order, and so on. If the point number of the original shoreline data is maximum, the end point candidate point is the end point. is there. In other words, if the point number n of the original shoreline data immediately before the point that is not OK for the first time is n, n 'is the end point. In FIG. 1, 7 'is the end point. The end point is not limited to n '(approximate point) but may be n (point on the chart data) like points 14 and 18.

However, the end point may not be determined only by the above determination. For example, in FIG. 2, when an approximate straight line having the passing point at point 18 exists, the end point is 24 'under the above conditions alone.
Becomes At this time, when the passing point is determined from the point 24 with the 24 'as the starting point and the next approximate straight line is obtained, the points 22 and 23 exist on the sea side of the approximate straight line. This does not achieve the original purpose of not providing an approximate straight line on the land side. Therefore, the following conditions are required.

When the distance l between each passing point and the end point between the passing point and the end point is larger than the distance between the passing point and the end point, a point at which the distance l becomes the maximum is obtained. Let k 'be the end point. Where l is the distance from the passing point to each point, the starting point
The direction from 12 'to the passing point 18 is defined as positive. In the example of FIG. 2, since 23 is the maximum, 23 'is the end point instead of 24'.

[Extraction of the closest line]

An approximate straight line can be obtained by the above method. For example, as shown in FIG. 3, when there is an approximate straight line starting from 68 'and ending at 82, the point C is set as the starting point, The approximate straight line (broken line) ending at 82 is more suitable as the approximate straight line. In other words, there is a possibility that an approximate straight line that is more suitable for an approximate straight line having a point marked with 'as a start point and an end point not marked with' may be present. In the example shown in FIG. 3, a straight line starting from point C, passing point 67, and ending point 82 is an approximate straight line. Here, the point 67 is an approximate straight line 68'-82 among the straight lines connecting each point and the point 82 at each point between the passing point 65 of the approximate straight line immediately before and the point 81 just before the point 82. Is the passing point that becomes the straight line closest to. This pass point 67 and end point 82
Is the intersection point between the straight line connecting and the approximate straight lines 63'-68 'found last time. Hereinafter, obtaining the most suitable approximate line is referred to as extraction of the most approximate line.

Next, an example of a wake display device to which the graphic data compression method of the present invention is applied will be described.

FIG. 4 is a block diagram of the wake display device. In FIG. 4, a CPU 100 is an arithmetic and control unit that performs an approximate straight line extraction process, an approximate point data generation process, a suitable point data extraction and generation process, and the like according to the present invention. The ROM 101 represents a memory for storing a control program of the CPU 100 in advance, and the RAM 102 represents a memory used as a working area when executing the program. 104 is a floppy disk drive, 1
03 represents the controller, and the CPU 100 reads the chart data previously written on the floppy disk. CRT107
Is a display device for displaying a chart based on the extracted data, and is driven by the display control circuit 106. The display control circuit 106 creates a display signal according to the display data written in the display memory 105, and outputs it to the CRT 107. The CPU 100 creates display data based on the extracted data and the current position of the ship, and writes the display data into the display memory 105 to perform display. The keyboard 109 is an input device for setting the number of data to be extracted and the like, and is controlled by the key controller 108. The positioning device 110 is a device that measures the current position of the ship.

The processing procedure of the CPU 100 will be described with reference to the flowchart shown in FIG.

 The meaning of each variable shown in FIG. 5 is as follows.

Ls: Permissible set distance from the original chart data to the approximate line Ns: Number of data to be extracted (points) D: Permissible error of the number of data to be extracted La (n): Latitude data of chart Lo (n): of chart Longitude data X (n): X coordinate data of a chart Y (n): Y coordinate data of a chart x (s): X coordinate data of an extracted point y (s): Y coordinate data of an extracted point s: x ( s), y (s) pointer n: X (n), Y (n) pointer S _M : number of extraction points ΔA: change amount of Ls for each calculation X01: X coordinate data of reference point 1 of chart Y01: chart X02: X coordinate data of the reference point 2 of the chart. Y02: Y coordinate data of the reference point 2 of the chart. La1: Latitude data of the reference point 1 of the chart. Lo1: Longitude data of the reference point 1 of the chart. La2: Latitude data of reference point 2 of the chart Lo2: Longitude data of reference point 2 of the chart ND: Total number of data of the original chart (total points) As shown in Fig. 5, Not Ls, ΔA, Ns, each value of D is set from the keyboard, respectively (n1). Next, from the floppy disk, the total coordinate data X (1 to 1) in the XY coordinate system which represents the total number of data Nd of the chart and the position on the chart in units of length.
Nd), Y (1 to Nd) and position data X01,
Read Y01, X02, Y02, La1, Lo1, La2, Lo2 respectively (n
2).

Subsequently, the first point (the first point) of the chart data is unconditionally extracted as a point to be extracted and stored as a starting point (n3).
Thereafter, the pointers s and n are set to 2 (n
4) When the n-th chart data X (n), Y (n) is once regarded as a passing point and the point is regarded as a passing point,
It is determined whether or not the condition is satisfied (n5 → n6). ,
If the condition is satisfied, n is incremented (n7), and similarly, the condition of the passing point is determined for the n-th chart data. In the example shown in FIG. 1, the condition when n = 3 (the point of the original chart data is on the land side with respect to the approximate straight line) is not satisfied, and the point 2 is finally obtained as the passing point. Are stored in x (2) and y (2) (n8). Next, it is determined whether or not X (n), Y (n) (where n = 3) satisfies the end point condition (n9). If this condition is satisfied, n is incremented (n10), and the determination of the end point condition is similarly repeated. In the example of FIG. 1, when n = 5, the end point condition is not satisfied and the value of n is returned to 4 in step n11. Subsequently, it is determined whether or not the end point condition is satisfied for the n-th chart data (n12). Since the condition of the example of FIG. 1 is satisfied, the pointer s is incremented (n13), and the condition for extracting the closest straight line, that is, '
Then, it is determined whether or not the end point is marked with 'without the mark (n14). In the example shown in FIG. 1, since the condition is not the condition, the n-th chart data is obtained as the s-th extraction point,
This is stored as a starting point (n17). That is, the fourth point of the chart data in FIG. 1 is stored as the third extraction point.
Thereafter, it is determined whether or not n has reached the total number of data Nd of the chart (n18), and if not reached, n is incremented,
Pass points are obtained for the nth and subsequent chart data (n19 → n5...).

If the end point condition is not satisfied in step n12, n is decremented until the condition is satisfied (n12 → n11...) For example, the end point 24 'once obtained in FIG. 2 is changed to 23'.

If the obtained end point satisfies the extraction condition of the most approximate line in relation to the start point, at step n15 the most approximate line and the intersection C of the most approximate line and the previously obtained approximate line
Is extracted, and the coordinates of the point C are stored as the s-th extraction point (n16). In the example shown in FIG. 3, the straight line connecting the point 67 and the end point 82 is obtained as the most approximated straight line,
The point of intersection with -68 'is determined as C.

After performing the above steps n5 to n19 for all points of the chart data, the last data of the chart data is extracted and stored as the end point (n18 → n20 → n21). afterwards,
Extract performs comparison between data speed Ns to be extracted and the total number of data S _M was. If the number S _M of extracted data exceeds the number Ns of data to be extracted, the value of the initially set permissible set distance Ls is increased by ΔA, the stored contents are erased, and the same processing is performed again (n22). → n23 → ・ ・ ・). If extracted when data S _M falls below the value obtained by subtracting the allowable error D from the data speed Ns to be extracted, the allowable set distance Ls performed only reduced so again similar processing ΔA (n24 → n25 →・ ・
・).

Repeating the above process, the number of extracted data S
_{If M} falls within the range of the allowable error D from the number Ns of data to be extracted initially specified, the position data X01, Y01, X02, Y02, La1, Lo1, La2, Lo2 of the two reference points on the chart are used. latitude of each point of 1 to S _M, the longitude data La (1~S _M), obtains the Lo (1~S _M), stores it in the RAM 102 (n26). The latitude and longitude data of each point in the chart data can be obtained from the latitude and longitude data of the two reference points on the chart and the difference between the two reference points on the X and Y coordinates of each point in the chart data. If the scale is clear, it can be converted to latitude and longitude data using one reference point and scale data.

As described above, the data can be compressed using an approximate straight line that has a small difference from the original chart and does not pass through the land side in the original chart.

In the embodiment described above, when the pass point or the end point is obtained, if the above condition is not satisfied, the point returns to the immediately preceding point and this is immediately stored as the pass point or the end point. Even if the condition is not satisfied, the candidate point of the passing point or the end point is advanced, and as a result, each of the points from the starting point to the passing point or the points from the passing point to the end point satisfies the above condition. As a matter of course, a process of extracting a passing point or an end point may be performed. For example, in the example shown in FIG. 6, if a pass point is to be obtained starting from 68 ', according to the previous embodiment, the point 72 will be extracted as a pass point. When 68
To 81 to satisfy the above conditions and
Candidate point 82 can be extracted as a passing point and an end point. After the point 82 is extracted, a straight line (broken line) connecting 72-82 can be obtained as the most approximate line by the process of extracting the most approximate line.

In this embodiment, a wake display device having two functions of compression and display of graphic data is described as an example, but the respective functions may be separated. The graphic data extracted in advance may be stored in the floppy disk, the RAM 102, or the ROM 101 in accordance with the display data storage capacity of the display device, the drawing speed, the number of displayable pixels, and other capabilities and the display range.

In the embodiment, the shoreline printed as a chart is read by a digitizer, and the chart data is recorded in advance on a floppy disk as X and Y coordinate data. However, the chart data is stored as latitude and longitude data. May be.

(H) Effects of the Invention According to the present invention, when data of a boundary line composed of a plurality of points is compressed, an approximate straight line becomes a tangent line which is in contact with one side of the original boundary line. At the time of compression, it is possible to prohibit the shoreline existing in the original chart data from retreating to the land side, and it is possible to easily generate graphic data suitable for ship navigation assistance.

[Brief description of the drawings]

FIG. 1 is a diagram for explaining the operation of the present invention and a specific example of a graphic data compression method according to an embodiment of the present invention. 2 and 3 are diagrams showing a specific example of the graphic data compression method according to the embodiment. FIG. 4 is a block diagram of a wake display device to which the graphic data compression method of the present invention is applied, and FIG. 5 is a flowchart showing a graphic data compression procedure of the wake display device. FIG. 6 is a diagram for explaining a graphic data compression method according to another embodiment, and FIG. 7 is a diagram for explaining a conventional graphic data compression method.

Claims (1)

(57) [Claims] A graphic data compression method for compressing graphic data representing a boundary line such as a shoreline by a plurality of points to obtain graphic data having a small number of data points, comprising: An approximate straight line extraction process is performed in which a point to be left as data is set as an extraction point, and a tangent line which is in contact with one side of the boundary line at this extraction point is set as an approximate straight line. Approximation point data generation processing, and adaptation point data extraction generation processing for changing the distance between the extraction point and the approximation point to the broken line and the boundary line within a predetermined distance by changing the extraction point position and the approximation point position A graphic data compression method consisting of