JP2008158925A - Linear approximation device and method for deformation - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To use a further simplified line array for expression while maintaining shape features of an original line array by solving the problem in conventional linear approximation for approximating a line array with a smaller number of lines, where features of a road shape cannot be maintained. <P>SOLUTION: It is examined whether line direction is largely changed at each connection point between two or more lines, and at a connecting point where the direction is largely changed, linear approximation is performed so as to keep the point. All lines are grouped by direction, to examine the groups of the lines mutually connected at each point. When the lines belong to the same group, the small directional change is determined. When the lines belong to adjacent groups, also, the small direction change is determined. In other cases, large directional change is determined. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

The present invention relates to a graphic processing for linearizing a line segment sequence, and to a line segment linear approximation device and method used when it is desired to approximate a line while maintaining the features of the graphic as much as possible, such as when a road is represented by a line segment sequence. Involved.

A deformation method based on making the road more straight and quantizing the direction horizontally / vertically or in the direction of 45 degrees is performed. A method (Non-Patent Document 1) and a parallel-type deformation method (Non-Patent Document 2) in which all roads are gradually moved and deformed have been proposed.

Kenji Hamada Kazunori Yamamori Junichi Hasegawa: “Development of an automatic deformation map generation system” Transactions of Information Processing Society of Japan, Vol.37 (No.9): pp.1736-1744 (Sep 1996) Kazunori Yamamori Hiroshi Honda Junichi Hasegawa: “A road network shaping method based on street-based road deformation”, IEICE Transactions, VOL.J84-D-II (No.9): pp.2058-2069 (Sep 2001) )

  However, the deformation method proposed in Non-Patent Document 1 is to sequentially select and deform roads, and in a road map with a complicated shape, it is effective on the last road as the deformation progresses. There was a problem that it could not be deformed. At this time, the roads with higher priority are deformed in order, but due to the presence of roads with lower priorities, problems such as crossing will occur, and the priority will be high enough to a sufficiently deformed position. There was also a problem that the road could not be deformed. Therefore, in order to solve these problems, the inventor changes the road shape step by step for each classified road, and is restricted by the existence of the road for a low-priority road. Invented a road map automatic deformation method characterized in that the road is deformed without any change (Patent Document 1).

JP 2006-259012 A

  By the way, the line segment sequence to be linearly approximated is not limited to road use, and there is a piecewise linear approximation method as a method for linearly approximating a general line segment sequence. In this method, the points at both ends are connected by a straight line, and a connection point that has the longest perpendicular to the straight line is selected for the connection point in the middle. If the length of the perpendicular foot is equal to or greater than the threshold value, the line segment connecting both ends is replaced with a line segment refracted at the connection point. If it is shorter than the threshold value, the line segment itself connecting both ends is a linear approximation result. When it is replaced with a refracted line segment, the positions of both ends are recursively changed to the replaced line segment position, and the process of whether or not to further refract is repeated.

The above-described content will be described with reference to FIG. 1. When a line segment consisting of a thick solid line from point x to point y is given, the foot of a perpendicular line dropped to a line segment xy connecting point x and point y with a straight line Find the point A where is the longest. When the length of the leg of the perpendicular line dropped from the point A (the length of the line segment connecting the point A and the point L) is equal to or greater than the threshold value, the line segment is divided at the point A. Dividing into a line segment consisting of a thick solid line from point X to point A and a line segment string consisting of a thick solid line from point A to point Y, the point where the length of the vertical leg is the longest in the same way. locate. If point B and point C are found, it is checked whether the length of the line segment connecting point B and point M is equal to or greater than the threshold value. Further, it is checked whether the length of the line segment connecting the points C and N is equal to or greater than the threshold value. If it is equal to or greater than the threshold, the line segment is divided at that point. If it is smaller than the threshold, the line segment sequence is approximated by a line segment connecting both ends. FIG. 1 shows a case where the line segment BM is equal to or greater than the threshold value and the point B is divided, and the line segment CN is smaller than the threshold value and the point C is not divided. If it is divided, it is repeated until it is not divided recursively. In FIG. 1, a line displayed as a double line is the final straight line approximation result.

However, the piecewise straight-line method focuses only on whether or not the connection point falls within the threshold distance from the replaced line segment, even if there is a connection point where the direction of the line segment changes rapidly. If the distance between the legs of the perpendicular line is within the threshold value, the connection point is not left. In addition, in the case of a line segment representing a road, the connection points at which the direction of the line segment changes suddenly represent the characteristic shape of the road shape. There are times when you want to leave a point of a characteristic shape. However, the piecewise linear approximation method has a problem that a characteristic shape cannot be left.

Further, when simplifying a line segment sequence representing a road, it may be desired to simplify a horizontal line segment sequence more horizontally and to simplify a vertical line segment sequence more vertically. People often draw deformed maps with an emphasis on the use of horizontal and vertical line segments, and even when approximating a line segment representing a road in a straight line, it may be desirable to approximate the horizontal and vertical lines. However, the piecewise linear approximation method has a problem that the direction has no specificity and cannot be approximated only with respect to the horizontal and vertical directions.

Therefore, the present invention aims to provide a method for performing a straight line approximation while leaving a connection point where the direction of the line segment changes rapidly, and to provide a straight line approximation with more importance on the horizontal and vertical directions. Reached.

That is, the present invention is an apparatus and method having means for reading out an electronically stored line segment sequence, linear approximation processing means, and means for outputting the line segment sequence of the linear approximation result, wherein the linear approximation processing means After line segments are grouped according to direction, connection points that connect line segments that do not belong to the same group or adjacent groups are left as refraction points when they are approximated by a straight line without being deleted. Is a linear approximation device and method.

Further, according to the present invention, when the line approximation is divided into groups according to the direction in the straight line approximation processing means, the grouping boundary line does not come in the horizontal and vertical directions, but clockwise or counterclockwise from the horizontal direction and the vertical direction. A straight line approximation apparatus and method characterized in that the same group is formed up to a direction shifted by a threshold angle around.

According to the present invention, at a connection point where the direction of the line segment is greatly changed, linear approximation can be performed so as to leave that point. For example, for a connection point where the direction of a line segment representing a characteristic change point of the road shape changes abruptly, such as a line segment representing a road, it is possible to approximate the line by leaving the point as a refraction point. it can. In addition, a line segment sequence close to horizontal can be simplified more horizontally, and a line segment sequence close to vertical can be simplified more vertically.

  Although embodiments of the present invention will be described below, the technical scope of the present invention is not limited by the following embodiments, and various modifications can be made without changing the gist of the present invention. Further, the technical scope of the present invention extends to an equivalent range.

In the straight line approximation processing means of the present invention, when dividing a line segment into groups according to the direction, the grouping boundary line is shifted in the clockwise and counterclockwise directions from the horizontal direction by the threshold angle without causing the boundary line of the grouping to be in the horizontal and vertical directions. The direction is divided into the same group, and the direction shifted from the vertical direction by the threshold angle clockwise and counterclockwise is divided into the same group.
For example, when 360 degrees is divided into 16 groups, one group has a direction in the range of 22.5 degrees as one group, and the threshold is 11.25 degrees. That is, a range between horizontal and plus or minus 11.25 degrees is one group. The second group is in the range of 11.25 to 33.75 degrees, the third group is in the range of 33.75 degrees to 56.25 degrees, and the third group is in the range of 56.25 degrees. The range of 78.75 degrees from the range, and the fourth group is in the range of 78.75 degrees to 101.25 degrees. In the same manner, 16 groups are allocated at an interval of 22.5 degrees per round.
For example, when 360 degrees is divided into eight groups, one group has one direction in the range of 45 degrees, and the threshold is 22.5 degrees. That is, a range between horizontal and plus or minus 22.5 degrees is one group. The second group is in the range of 22.5 to 67.5 degrees, and the third group is in the range of 67.5 to 112.5 degrees. In the same manner, 8 groups are assigned at 45 degree intervals per round.

Specific embodiments of the present invention will be described with reference to the drawings. An example in which 360 degrees is divided into 16 groups is shown in FIG. In FIG. 2, group 1 is a group responsible for a range between horizontal and plus or minus 11.25 degrees. Group 2 is a group responsible for a range from 11.25 degrees to 33.75 degrees. When the direction of the line segment belongs to the range, it is determined that the line segment belongs to the group.

Next, when 360 degrees is divided into 16 groups, the first group is responsible for the range between horizontal and plus or minus 11.25 degrees, and the 16th group is 326.25 degrees. To 348.75 degrees, the first group and the 16th group are regarded as adjacent groups.
When 360 degrees is divided into eight groups, the first group is responsible for a range between horizontal and plus or minus 22.5 degrees, and the eighth group is 292.5 degrees to 337.degree. Waiting for a range of 5 degrees, the first group and the eighth group are considered as adjacent groups.

Next, with respect to a connection point that connects line segments that do not belong to the same group or adjacent groups, a given line segment row is divided at the connection point. The segmented line segment sequence is then linearly approximated. The linear approximation method at this time may be a conventional piecewise linear approximation method, and the method is not limited.

Next, a configuration example of the linear approximation device of the present invention will be described more specifically with reference to FIG. As shown in FIG. 3, the straight line approximation apparatus 100 of the present invention outputs means 101 for reading a line segment stored in the present invention, line approximation processing means 102, and a line segment sequence of the line approximation result. Means 103 is included.

The straight line approximation processing means 102 includes a process 110 for dividing each line segment into groups according to directions, a process 111 for extracting connection points connecting line segments that do not belong to the same group or adjacent groups, There is a process 112 for dividing the line segment sequence at the extracted connection points, and a process 113 for approximating the line segment sequence after the segmentation to a straight line. In the processing 113 for linearly approximating the divided line segment sequence, for example, a conventional linear approximation method such as a piecewise linear approximation method may be used.

It is a figure for demonstrating the processing method by the piecewise linear approximation method by a conventional method. It is a figure for demonstrating the group in the case of dividing the line segment by a direction into 16 groups by a direction. It is a figure for demonstrating one structural example of the linear approximation apparatus which concerns on embodiment of this invention.

Explanation of symbols

DESCRIPTION OF SYMBOLS 100 ... Straight line approximation apparatus 101 ... Means 102 which read the line segment sequence memorize | stored 102 ... Linear approximation process means 103 ... Means to output the line segment sequence of a straight line approximation result 110 ... Each line segment Processing 111 to divide into groups according to direction ... Processing to extract connection points connecting line segments that do not belong to the same group or adjacent groups 112 ... Divide line segments at the extracted connection points Process 113 ... Process for approximating a line segment after segmentation to a straight line

Claims (4)

An apparatus comprising: means for reading out a line segment stored electronically; means for processing a line approximation; and means for outputting a line segment as a result of the line approximation, wherein the line approximation processing means groups line segments according to direction. After being divided, the connection point connecting the line segments that do not belong to the same group or adjacent groups is left as a refraction point when it is linearly approximated without being deleted. . In the straight line approximation processing means, when dividing the line segment into groups according to the direction, the boundary line of the grouping does not come in the horizontal and vertical directions, and the threshold angle is divided clockwise or counterclockwise from the horizontal direction and the vertical direction. The straight line approximation apparatus according to claim 1, wherein the same group is formed up to the shifted direction. A method comprising a means for reading out a line segment stored electronically, a line approximation processing means, and a means for outputting a line segment sequence of the line approximation result, wherein the line approximation processing means groups line segments according to direction. A straight line approximation method characterized by leaving a connection point connecting line segments that do not belong to the same group or adjacent groups as a refraction point when the straight line approximation is performed without being deleted. . In the straight line approximation processing method, when dividing a line segment into groups according to the direction, the boundary line of the grouping does not come in the horizontal and vertical directions, and the threshold angle is divided clockwise or counterclockwise from the horizontal direction and the vertical direction. The straight line approximation method according to claim 3, wherein the same group is formed up to the shifted direction.

Images