JPS6350722B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a curve interpolation method for two-dimensional discrete point data that can be numbered, and in particular, to apply an interpolation curve of two-dimensional isoparametric representation to the discrete point data,
The present invention relates to a curve interpolation method in which the interpolation positions of the interpolation curve are sequentially divided into two parts, and the interpolation values of the interpolation edge areas are finely calculated, thereby clarifying the characteristics of the interpolation curve.

The interpolation formula of the two-dimensional isoparametric expression for interpolating n point sequence P _j (j = 1, 2, 3, ..., n) of discrete point data (hereinafter referred to as observation points) is X _j = _{n+ 1} 〓 ⁱ⁼¹ a _ij t ^i-1 (1-a) Y _j = _n+1 〓 ⁱ⁼¹ b _ij t ^i-1 (1-b) In the above formula, j is the interpolation section number and m is the interpolation curve a _ij and b _ij are interpolation coefficients for interval j, t is a domain parameter, and is expressed as 0≦t≦1 for each interval.

The conventional interpolation method using equation (1) above is based on a sequence of observation points.
For interpolation from adjacent P _j to P _j+1 at P _j ,
A constant increment of interpolation width Δt is used for the domain parameter t of the interpolation interval (hereinafter referred to as interpolation position), and the t value (0, Δt, 2・Δt, 3・Δt, ..., 1
-Δt, 1) to calculate the interpolated value.

In general, the curvature of the interpolation curve near observation point P _j tends to increase, and in the conventional method in which Δt is a constant value, the curvature of the interpolation curve becomes large compared to the interpolation density at the center of the interpolation section where the curvature is small. The interpolation density at the end positions of the sections is relatively sparse, so a smooth interpolation curve cannot be drawn, and the characteristics of the interpolation curve are difficult to clarify.

In addition, if the interpolation width Δt is set to a sufficiently small value in order to sufficiently clarify the characteristic tendency of the interpolation curve, the interpolation value at the center position of the interpolation interval will be calculated more precisely than necessary, and the calculation time will increase. Ta.

SUMMARY OF THE INVENTION An object of the present invention is to provide a simple curve interpolation method that improves the above drawbacks and reveals the characteristic tendency of an interpolated curve with a small number of interpolations.

The configuration of the present invention to achieve this objective is to use two-dimensional discrete point data Pj: Xj,
Yj is input to the data stack memory area, and based on the input discrete point data Pj, the interpolation coefficients a _j and b _j of the interpolation curve by the isoparametric expression polynomial passing through the discrete point Pj are calculated. Store the discrete points Pj in the stack memory area, and sort the discrete points Pj in numbered order (j=1~
The domain (0
Interpolation position data t determined in ~1) and the interpolation coefficient
A curve interpolation method for calculating interpolated values Xt, Yt of the interpolation curve between the discrete point data Pj by a _j and b _j , the discrete point data Pj being arranged in the order of numbering (j=1 to Determine the number of data points k _j of the interpolated position data t between the discrete point data Pj according to the angle α _j formed by the straight lines on both sides at the discrete point data position Pj when connected in a straight line to The interpolated position data between the discrete point data _Pj (0≦t≦
1) is sequentially divided into two parts, and the interpolation coefficients a _j , b _j and interpolation position data t in the coefficient stack memory area are output.
When calculating the interpolated value with
It is characterized in that the interpolation near Pj is calculated more densely than the interpolation near the center between the discrete point data Pj.

For example, n observation points P _j (j=1, 2, 3,
..., n) are connected in a straight line in the order of numbering. At this time,
Observation point P _j is called a cusp, and the angle between the cusp P _j is ∠P _j-1 P _j
P _j+1 is called cusp angle α _j . In the interpolation section from cusp P _j to cusp P _j+1 , interpolation position data t is changed to the center position (t
= 0.5) as the starting point, proceed separately toward the cusp P _j (t = 0) and the cusp P _{j +1} (t = 1), and interpolate by repeating each t value by dividing it into two. Calculate the value. At this time, the number of repetitions in the direction of cusp P _j (decrease of t by two) and the direction of cusp P _j+1 (increase of t by two), in other words, the number of times of giving an interpolated position is the cusp angle α It depends on _j and α _j+1 , and it is decided to increase the cusp angle at the interpolation end position where the cusp angle is small.

The present invention will be explained below using figures.

Figure 1 shows a sequence of observation points P _j (j=1, 2, 3, ...,
This is a graph in which one observed data sequence of n-1, n) is plotted on the X-Y coordinates. In the figure, the observation point
From P ₁ to Pn 100, 101, 102, 103,
104, 105, 106 from observation point P ₁
A straight line 400 connecting the observation points in the interpolation interval leading to Pn,
401, 402, 403, 404, 405, 40
6,407.

FIG. 2 is a block configuration diagram showing one embodiment of the present invention and explaining the curve interpolation procedure, data stack state, and unit connection relationship.

In the figure, block 1 inputs observation point data P _j (100 to 106 in FIG. 1) and stores it in the data stack memory area 8a in preparation for the following processing. In block 2, the calculation unit 7 calculates interpolation coefficients for each interpolation section of the isoparametric expression interpolation curve using the input observation point data _Pj , and stores them in the coefficient stack memory area 8c. Furthermore, observation point data P _j
Accordingly, in block 5, the angle (referred to as cusp angle; see Figure 5) formed at observation point P _j (referred to as cusp P _j ) is calculated by calculation unit 7, and the angle formed at observation point P j (referred to as cusp P _j ) is calculated by calculation unit 7. The number of occurrences of the interpolated position data up to , is determined based on the size of the cusp angle, and is stored in the stack memory area 8b for the number of occurrences.

Block 6 is a generator for outputting interpolated position data, and outputs interpolated position data for each interpolation interval the number of times of occurrence. Block 3 calculates an interpolated value in a calculation unit 7 using the output from the interpolation position generator 6 and the interpolation coefficient in the stack memory area 8c.
In block 4, it is output to the stack memory area 8d.

FIG. 3 is a diagram illustrating an example of the area arrangement of the stack memory 8 in FIG. 2. In the figure, 8
a is the storage area for observation point data P _j (see Figure 1), 8
b is a storage area for the number of occurrences of interpolation position data for each interpolation interval, 8c is a storage area for interpolation coefficients for each interpolation interval, 8
d is a storage area for interpolated values.

FIG. 4 is a flowchart illustrating a procedure for generating interpolated position data by the interpolated position generator 6 in FIG. 2. In the figure, block 20 prepares initial conditions for starting interpolation calculations, and block 21 prepares initial conditions for each interpolation section. Block 22 determines the end of interpolation for each interpolation section, and block 25
Block 26 determines the end of the number of occurrences of the two-division decreasing series interpolated position data in the interpolation interval, and block 26 determines the end of the number of occurrences of the two-division increasing series interpolated position data. Block 23 generates interpolated position data for a two-part decreasing series, and block 24 generates interpolated position data for a two-part increasing series.

Figures 5 to 7 show the state in which observation points 103P _j to 104P _j+1 of the observation point data in Figure 1 are applied to the present invention in Figure 2, and the interpolated values in this section are output. This is a graph showing the resulting interpolated curve as a broken line. The following description will be made with reference to FIGS. 1 to 4.

Block 5 (Fig. 2) retrieves observation point data P _j-1 ,
Input P _j , P _j+1 , P _j+2 (Fig. 1) and cusp 103
The cusp angle 150 (Fig. 5) of the cusp point 104 is calculated by the calculation unit 7 at the three points P _j-1 , P _j , P _j+1 , and the cusp angle 151 (Fig. 5) of the cusp point 104 is calculated by P After calculating from the three points _j , P _j+1 , P _j+2 in the calculation unit 7, interpolation interval 4
The number of interpolated position data occurrences of 04 (Figure 5) is
It is determined by a step function shown in the figure (described later) and stored in the stack memory area 8b. For example, according to Fig. 8, if the cusp angle is a decreasing series from about 82 degrees to about 150 degrees, the interpolated position data will be three pieces: 1/2, 1/4, and 1/8.
Also, if it is an increasing series from about 150 degrees to 180 degrees, 1/2,
Generates 2 pieces of 3/4.

The plot point on the graph in Figure 6 is block 3.
This is an example of calculating the interpolated value in (Fig. 2). Block 3 (Fig. 2) is a stack memory 8c (Fig. 2,
The interpolation coefficient for the j-th interpolation interval is input from the interpolation position data generator 6 (Fig. 3), and the two-division decreasing series of the interpolation position t is inputted from the interpolation position data generator 6 (Fig. 2, Fig. 3). /2, 1/4, 1/8) and two bipartite increasing series (1/
2, 3/4) and enter X and Y at each t value.
The interpolated value of is calculated by the calculation unit 7 using interpolation formulas (1-a) and (1-b).

Figure 6 A shows the interpolated values 211, 212, 213, 21 of X at the t values (1/8, 1/4, 1/2, 3/4).
4 and the X values of observation points 103 and 104 are plotted as a broken line, and Figure 6B is a graph that similarly plots the interpolated Y values 311, 312, 313, 314 and the Y values of observation points 103 and 104 and is displayed as a broken line. This is the displayed graph.

A broken line 410 in FIG. 7 is a linear approximation interpolation curve that combines A and B in FIG. 6, plots it on the X-Y coordinates, and connects each point with a straight line.

FIG. 8 shows a step function that determines the number of occurrences of interpolated position data in block 5 of FIG.
In the figure, the function form calculates the ratio of 180 and the cusp angle,
1.8 is added to it, the decimal value of the result is rounded down, and the integer value is used as the number of interpolations, and the maximum number of times is limited to 11.

For example, when the cusp angle is 120 degrees, there are 3 t values,
In other words, in the two-part decreasing series, it is up to 1/2, 1/4, and 1/8, and in the two-part increasing series, it is up to 1/2, 3/4, and 7/8.

As described above, according to this embodiment, in FIG.
Since it can be appropriately distributed to each of the vicinity and the vicinity of the cusp 104, it is effective to sufficiently clarify the characteristic tendency of the interpolated curve even with only a few interpolations.

By the way, when comparing the number of interpolations to obtain the same characteristic tendency of the interpolation curve with the conventional method, the number of interpolations of the present invention: the number of interpolations of the conventional method is 1:1, 3:3, 5:
7, 7:15, 9:31, etc., and the effect of the present invention becomes clear.

FIG. 9 shows points from cusp 103 to cusp 104 in FIG.
3 is a graph showing an example of application of the present invention to an interpolation interval leading to . What is different from FIG. 6 in this figure is the two-division interpolation position (1/
8), 3/8 is generated at the same time, and the interpolated value 215 at that position is also calculated. This application example is used when the distance of the interpolation interval is long, and in the interpolation position generator 6 (Fig. 2), in the two-division decreasing series, 1/2, 1/4, (1/8, 3/8), ( 1/16, 3/16), (1/32,
3/32), ..., and in the two-division increasing series, 1/2, 3/4, (7/8, 5/8), (15/16, 13/16), (31/3
2, 29/32), etc., each pair of interpolation position data is generated and interpolated. According to this application example, it is possible to more smoothly interpolate the interpolation curve in the center area of the interpolation section in the simple two-division interpolation position data generation described above.

As described above, according to the present invention, compared to the conventional calculation of interpolation values by dividing the interpolation position equally, the number of times of interpolation is significantly reduced and the time required for calculation is reduced if the characteristic tendency of the interpolation curve is equally expressed. It has the effect of shortening the time.

[Brief explanation of the drawing]

Figure 1 is a graph plotting an example of two-dimensional discrete point data on X-Y coordinates, Figure 2 is an example diagram showing the curve interpolation procedure, data stack state, and unit connection, and Figure 3 is the stack memory of Figure 2. FIG. 4 is a flowchart showing the procedure of the generator that outputs the interpolated position data in FIG. 2. Furthermore, FIGS. 5 to 7 are diagrams for explaining the interpolation procedure and status, and FIG. 9 is a diagram plotting the output of interpolated values in an applied example. FIG. 8 is a graph showing a step function for determining the number of occurrences of interpolated position data from the cusp angle. In the figure, 100, 101, 102, 10
3,104,105,106 are discrete (observation) point sequences, 400,401,402,403,404,
405, 406, 407 are interpolation intervals, 2 is an interpolation coefficient calculation block, 3 is an interpolation value calculation block, 5 is an interpolation position data generation number calculation block, 6 is an interpolation position data generator, 7 is a calculation unit, 8 is a stack memory, 150 and 151 are cusp angles, 211,
212, 213, 214 are the interpolated values of X, 311,
312, 313, 314 are interpolated values of Y, 111,
112, 113, 114 are the interpolated values of X and Y
The point 410 plotted on the Y coordinate is a broken line approximation of the interpolation curve.

Claims (1)

[Claims] 1. Numberable two-dimensional discrete point data (j=1 to n)
Pj: Input Xj, Yj to the data stack memory area, and calculate the interpolation coefficients a _j , b _j of the interpolation curve using the isoparametric polynomial that passes through the discrete point Pj based on the input discrete point data Pj. It is calculated and stored in the coefficient stack memory area, and the domain (0 The discrete point data Pj is determined by the interpolation position data t and the interpolation coefficients a _j and b _j determined in ~1).
A curve interpolation method for calculating interpolated values Xt, Yt of the interpolated curve between The number of data points k _j of the interpolation position data t between the discrete point data Pj is determined according to the angle α _j formed by _the straight lines on both sides of Interpolated position data (0≦t≦
1) is sequentially divided into two parts, and the interpolation coefficients a _j , b _j and interpolation position data t in the coefficient stack memory area are output.
When calculating the interpolated value with
A curve interpolation method characterized in that interpolation near Pj is calculated more densely than interpolation near the center between the discrete point data Pj.