JPH03202979A - Polygon approximation system - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Summary] Regarding a polygonal approximation method for arcs that approximates and displays circles or arcs using regular N-gons, the purpose is to draw circles at high speed, and when displaying polygons, The length is determined from the radius of the circle to be displayed and the thickness of the circle to be displayed, and the position of the first point to determine one side of the polygon for polygon approximation is determined by the circle to be drawn. from the center point of the circle to be drawn and the length, the position of the gathering point for determining the side is determined from the center point of the circle to be drawn and the length, and the distance between the first point and the second point is determined from the center point of the circle to be drawn and the length A line determined by a line segment that connects the first point and the second point, is parallel to the first line, and is separated by the thickness of the circle line in the direction of the center of the circle. It is characterized by drawing a thick line sandwiched between .

[Industrial application field]

The present invention relates to a circle polygon approximation method.

[Conventional technology]

Conventionally, when drawing a circle on a display or the like, a polygonal approximation method has been used.

A conventional polygonal approximation method is shown in FIG. 5, FIG. 6, and FIG. 7.

FIG. 5 shows a case where a circle with a radius R (here R is expressed by the number of pixels) is approximated by an N-gon. ○ is the center point of the circle, and A, B, and C are the vertices of the polygon.

To calculate the vertex, a calculation formula obtained from θ using a −Funatsuri trigonometric function is used.

A certain vertex (x, y) of a circle with radius R is determined from θ by the following equation.

χ=RXcos θ 〜・・−・−・〜・・−・−−−
1-・・・・−・−・■y=RX5inθ Polygonal approximation is one in which the angle θ is increased by a constant value Δθ, and the vertices obtained one after another are connected and used instead of a circle. (
If Δθ is selected from divisors of 360°, it will approximate a regular n-gon. ) It is desirable to calculate Δθ so that the difference between the radii of the inscribed circle and the circumscribed circle of the approximated polygon is less than one plane element as shown in FIG.

Δθ= 2 cos -'(1-R-') -----
−−−−−−−−−■ When drawing a line with an arbitrary line width, if you simply thicken one side of the polygon, "missing" will occur outside of each vertex. To compensate for this, use vertex processing. There is.

An example of vertex processing will be explained with reference to FIG.

A, B, and C in FIG. 7 are the positions of vertices determined by the calculation described in FIG. 5.

If the thickness of the circle is ε, after points A and B are determined,
Rectangles a, a, and b with line AB passing through their centers.

Draw b4. As shown in FIG. 7, it appears as if the line segment AB is thickened by half the line thickness by ε/2 on both sides.

That is, this is to draw a line of thickness ε between points A1 and 8, and is to use normal straight line drawing processing.

Therefore, after drawing the straight line 1aAB and the straight line BC, the vertex B
If it is placed at position b, a gap will occur at position B.

If the thickness of the line is thin, the omission is not noticeable, but when the line thickness reaches a certain level, the omission becomes noticeable.

Therefore, as a process to fill in the gaps, a process of drawing a circle with radius ε/2 centered on point B is performed. Correction of omissions is not limited to this, but corrections are made for as many vertices as there are.

[Problem that the invention seeks to solve]

If vertex processing was performed for each vertex generated by conventional polygon approximation, as the number of vertices increases, the processing of the figure drawing control processor increases, so it takes time to finish drawing the arc. .

[Means to solve problems]

In the arc polygon approximation method that approximates and displays circles and arcs using regular N-gons, when displaying a polygon, the radius of the circle to be displayed and the length of the line to be displayed are determined from the thickness of the circle. , determine the position of the first point for determining one side of the polygon for polygonal approximation from the center point of the circle to be drawn and the length, and determine the position of the first point for determining the one side of the polygon. Determine the position of the second point from the center point of the circle to be drawn and the length, connect the first point and the second point, and connect the first point and the second point. A thick line is drawn that is parallel to the first line and is sandwiched between lines determined by line segments separated in the direction of the center of the circle by the thickness of the circle line.

[Effect]

After determining the positions of the first point and the second point for determining one side of the polygon for polygon approximation from the center point and the length of the circle to be drawn, Draw a line connecting the second point that is thickened by the thickness of the circle line toward the center of the circle.

That is, since the line connecting the first point and the second point is not thickened toward the center, no omissions are displayed.

〔Example〕

The outline of this embodiment will first be shown below with reference to FIG.

○ is the center point of the circle, and A, B, and C are a group of vertices calculated by polygonal approximation.

Point F, which is found when point B is subjected to vertex processing, is on the extension line of OB.

That is, by adding a certain value ε to the radius, F can be directly determined. Take advantage of this.

(In the sentence, / means parallel.) A case will be explained in which the vertex processing is performed on point B and point F is obtained.

AO, BO, CO are vectors from the center to the vertices,
All are the same length.

It can be seen that ZAOB=ZCOB=ΔθyoΔAOBmiΔCOB.

DB can be said to be the short side of the thick line drawn with respect to string AB,
AB above DB.

DF is an extension when a rectangle pqr D, in which AB is drawn as a thick line, is extended in the direction of A→B, and becomes AB/DF. Similarly, it is CB Sat BEIEF, so it is CB/EF.

Here, from AB/DF and CB/EF, ZABC=ZDF
E=2α. The two halves of these two angles are still equal, and Z
ABO=ZDEB=α.

From the above, it is OB/BF. That is, point F is on the extension line of OB.

In other words, if we calculate the vertex by adding a certain value ε to the radius, we can directly find F. Strictly speaking, a value corrected for line width must be used for ε. In other words, D.F.
The correct line width in the forward direction is a matter of how you take it, but ε is in the BF force direction, making it thinner than it actually is. This correction uses the following formula for line width Δθ ε= sec ・−・−−−−−−−
■2 If Δθ is sufficiently small, secβ will be close to 1, so
There is no problem even if the line width is used as ε.

Embodiments will be described in detail below with reference to FIGS. 1 to 3.

FIG. 1 is a flowchart of a circle drawing program for drawing a circle according to this embodiment.

FIG. 2 shows tables used by the circle drawing program to determine the positions of the vertices of a polygon; FIG. 2(a) is a cosine table, and FIG. 2(b) is a radius-angle correspondence table.

FIG. 3 shows the configuration of the system, in which 31 is a drawing processor, 32 is a memory, 33 is a display memory, and 34 is a display.

The drawing processor 31 reads the contents of the memory 32 and processes them. The memory 32 includes the circle drawing program 321 shown in FIG. 1, the cosine table shown in FIG.
The radius-angle correspondence table b) is stored.

The drawing processor 31 and the circle drawing program 321 map a circle to the display memory 33, and the circle or arc is displayed on the display 34 according to the display memory 33.

The following description will be made assuming that a circle with a line width of 10 and a radius of 500 is processed in FIG. 5(a). Here, point A50°B50
Find the line and draw the line. For processing purposes, the angle value used here is
Use units different from those used in mathematics.

This is because in order to reduce the calculation of trigonometric functions, the value of cos θ is stored in advance as a table as shown in Figure 4.1 (al), and that index is used as the angle.

Step I: Find Δθ with R=500.

The steps below are those of the circle drawing program shown in FIG.

In reality, cos-' is not calculated by substituting it into the formula (2), but is prepared in advance as a table, as shown in Figure 4.1 (bl), so that it can be calculated directly from R.

Δθ=3.5156° (Internally treated as an integer 10) Step 2 Next, the correction value ε is calculated.

It is calculated by substituting into the formula ■, but when formula ■ is substituted, it becomes as follows.

This shows that the larger the radius, the more 5ecx#1 there is, and there is no problem in ignoring it. In this case, ε=line width/2=5
It will be.

Step 3 Add the correction value ε to the radius. The new radius value will be 505.

Step 4 Calculate the - point as θ-〇.

A50 (505, O).

Refer to the cos table using θ as an index. If you shift the sin and refer to it, you can use the cos.

x1=RXcos θ=505X1=505y,=Rx
sin θ-505XO=0 Ste-knob 5 Calculate by adding Δθ to θ. The second point is B50 (504,30) θ-θ+Δθ= O+3.5156=3.5156x,
=RXcos θ=505 Xo, 998 =504.
049y2=RXsin θ=505 Xo, 061
=30.967Stenob6 Draw a thick line from the two calculated points.

We need to make the circle thicker towards the inside, but since θ is simply increased, we can see that it is drawn counterclockwise. In other words, make it fatter on the left side.

Step 7 Move the coordinates of the second point to the first point.

If the edge 8 θ is within 1024, steps 5 to 7 are repeated until the entire circumference is drawn. θ
When it reaches -1024, it ends.

As described above, in the present invention, there is no vertex processing, so the drawing speed is significantly increased.

〔effect〕

According to the present invention, when a circular arc with an arbitrary line width is approximated as a polygon, since vertex processing is no longer required, the processing can be performed at a higher speed than in the case where vertex processing is performed for each -point.

[Brief explanation of drawings]

Fig. 1 is a flowchart of an embodiment of the present invention, Fig. 2 is a cosine table and a radius-angle correspondence table, Fig. 3 is the hardware configuration country of this embodiment, and Fig. 4 is a polygon approximation diagram of the present invention. Explanatory drawings, FIG. 5(a) is an example of drawing a circle, FIG. 5(b) is an explanatory diagram of conventional polygonal approximation, FIG. 6 is an explanatory diagram of conventional polygonal approximation, and FIG. The figure is an explanatory diagram of conventional vertex processing. 31・−・−・・−・−−−−−・−−1−−Drawing processor 321−・−・−・−・−・・Circle drawing program 322 Cosine table 323 −−−−−1 radius Angle compatible table real
1 Ki 1 Ida 11 Man 2 Figure J Figure Binary device actual example Figure Figure I Shiba pot (b) 'ff1s Figure I J Sui Otsu diagram

Claims (1)

[Claims] In a polygonal approximation method for arcs in which a circle or arc is approximated and displayed using a regular N-gon, the length is determined from the radius of the circle to be displayed and the thickness of the line of the circle to be displayed, The position of the first point for determining one side of the polygon for polygon approximation is determined from the center point of the circle to be drawn and the length, and the position of the second point for determining the one side is determined. A first line whose position is determined from the center point of the circle to be drawn and the length, which connects the first point and the second point, and which connects the first point and the second point. A polygonal approximation method characterized by drawing a thick line sandwiched between lines that are parallel to the line and are determined by line segments separated in the direction of the center of the circle by the thickness of the line of the circle.