wxdkdraw technical details

← Previous

↑ Home

→ Next

German version available: Technische Details zu wxdkdraw und wxd2lat

Technical details on wxdkdraw and wxd2lat

• Technical details on wxdkdraw and wxd2lat
  • Requirements
  • Conclusions
  • Selected mathematical problems
    • Calculating the WXD resolution
    • Arrowhead corrections
    • Polylines
      • Length correction for arrowheads
    • Arcs
      • Calculating center point and radius
      • Length correction for arrowheads
    • Rotated ellipses
      • Overview
      • Distance of a point to a straight line through the zero point
      • Bounding box of the rotated ellipse
    • Splines
      • Overview
      • Bezier splines
      • Bounding box of Bezier spline segments
      • Approximation of circular arcs using Bezier splines
      • X-splines
      • Approximation of X-splines by Bezier splines
      • Length calculation on splines
      • Length correction for arrowheads
  • Literature

Requirements

The following requirements were formulated when designing the file format and the wxdkdraw and wxd2lat programs:

• Use with LaTeX or pdfLaTeX
  The file formats used for export are PDF+TEX, EPS+TEX and PGF.
  For PDF+TEX and PGF output, either
  • a *.tex file can be created that is integrated into another *.tex file or
  • a *.tex file that can be processed directly by pdfLaTeX.
  
   
• Graphic elements
  The choice of available graphic elements should correspond approximately to the graphic elements available in XFig.
   
• Electronic circuits
  In electronic circuits, electrical connections between two intersecting lines are marked by a filled circle. A special graphic element (the filled dot) is provided for this purpose, a filled circle with a small radius, which is placed by center point. In contrast to the circle as a normal graphic element, this circle is filled with the drawing color, not the fill color. A white-filled circle with a small radius is used for ports (inputs/outputs) of circuits. The circles for connection points and ports are automatically placed in the layer above the current layer.
   
• Optical and magnetic grid
  Drawing takes place exclusively on a rectangular grid. The optical grid is displayed on the screen and is used for orientation. The graphic elements are aligned on the magnetic grid, which is finer than the optical grid.
   
• Inches and centimeters
  Drawing should be possible both in an inch-based grid and in a centimeter-based grid.
   
• Grid base 2 or 5
  It should be possible to choose whether half an inch or one centimeter is divided into 4 or 5 magnetic grid spacing intervals.
   
• Dynamic grid
  When zooming in, the grid should adjust dynamically. This means that zooming in not only enables more precise viewing but also finer drawing.
   
• Responsiveness of the drawing program
  The wxdkdraw program should interact with the user at normal speed.
   
• High-quality output for export
  The wxd2lat program is designed to generate high-quality graphics during export. More complex calculations are also accepted for this purpose.

---

Conclusions

• Integer coordinate values
  Integer values are used to store coordinates. However, as conversion to floating point numbers is required for export and some calculations, only 32-bit values can be used, as these can be converted to the “double” data type without loss. The “double” data type uses 51 bits in the mantissa field, this allows to represent 52 bit integer values. So we can not use 64 bit integer values for coordinates.
   
• Requirements for the WXD resolution
  The WXD resolution (number of wxd units per inch) is a compromise between two different requirements:
   
  • A high resolution allows fine drawing.
     
  • However, as only a numerical range of −2³¹ … 2³¹−1 is available for coordinates, a low resolution allows a larger extension of the drawing.
     
• Caching in the drawing program
  3 different cache bitmaps are used in wxdkdraw:
   
  • Grid
    The “deepest” drawing operations draw the border area in light blue, the drawing background in light gray and the optical grid in the form of horizontal and vertical lines. The result of these drawing operations is stored in a bitmap. The bitmap is only regenerated when required, e.g. when scrolling, zooming, or resizing the window.
     
  • Drawing
    The “middle” drawing operations first transfer the grid cache and draw the graphic elements on it, possibly with the exception of elements currently being edited. The result of these operations is in turn stored in a bitmap.
     
  • Markup
    The “top” drawing operations first transfer the drawing cache and draw the markup on top of it, e.g. the wxdkdraw cursor, the placement aid and graphic elements to be copied/moved or markers for candidates of copy/move/delete operations. The result of these operations is stored in a bitmap.
     
• Curved arrowheads, length correction for arrowheads
  High-quality output should be generated in the export file. The arrowheads should end exactly at the specified end point of a line. On curved lines (arcs and X-splines), the arrowheads should follow the curvature. For splines this requires complex calculations using iterative algorithms. This is acceptable for the wxd2lat export program, but not for the wxdkdraw interactive drawing program, as these calculations would result in stagnation when scrolling or moving graphic objects. Therefore, only an approximation of the arrowhead is displayed in wxdkdraw.

---

Selected mathematical problems

Calculating the WXD resolution

Users should have the choice between a grid based on inches and a grid based on centimeters. An integer number of wxd units should be used for both grids.
Equation (1) shows the conversion of the number of wxd units per inch into the number of wxd units per centimeter.
The WXD resolution (number of wxd units per inch) must contain the factor 127 so that the number of wxd units per centimeter is also an integer.

$$\begin{array}{cccc}\text{(1)}& r_{\text{wxd,cm}}& =& \frac{50}{127}{r}_{\text{wxd,inch}}\\ \text{(2)}& f_{\text{inch,cm}}& =& 127\end{array}$$

At zoom level 0 (factor 1=100%), one inch is divided into either 8 or 10 intervals to form the magnetic grid. One centimeter is divided into either 4 or 5 intervals.
To ensure that the points of the magnetic grid are also at integer values, the WXD resolution must contain a factor

$$\begin{array}{cccc}\text{(3)}& f_{\text{grid}}& =& \mathrm{lcm}(4,5,8,10)\\ & & =& 40\end{array}$$

The operator lcm(…) is used here to denote the least common multiple.

When zooming up to zoom level 14, zoom factors of up to 128 are possible. Decimal zooming up to a factor of 100 should also be possible.
So the WXD resolution must contain an additional factor

$$\begin{array}{cccc}\text{(4)}& f_{\text{zoom}}& =& \mathrm{lcm}(128,100)\\ & & =& 3200\end{array}$$

to ensure that the magnetic grid points lie on integer coordinates even if the magnetic grid interval is reduced by a factor of $\frac{1}{128}$ or $\frac{1}{100}$.

All three factors are used to calculate the WXD resolution:

$$\begin{array}{cccc}\text{(5)}& r_{\text{wxd,inch}}& =& f_{\text{inch,cm}}\cdot f_{\text{grid}}\cdot f_{\text{zoom}}\\ & & =& 127\cdot 40\cdot 3200\\ & & =& 16256000\end{array}$$

The WXD file format uses a resolution of 16256000 wxd units per inch.

Arrowhead corrections

The illustration shows a line coming from the left and ending at point P₀. An arrowhead is added to this line, which is drawn as a polyline P₁…P₀…P₂ using the same line width l as used for the actual line. As you can see, the arrowhead ends at point P_E with distance s to P₀.

The end point specified in the WXD file is point P_E. The actual line must therefore be shortened slightly so that it ends in the area between P_A and P_B. To end in P_A the line must be shortened by c_max, to end in P_B the line must be shortened by c_min.
If the opening angle of the arrowhead is denoted by α, we can calculate:

$$\begin{array}{cccc}\text{(6)}& \frac{l}{2}& =& s\cdot \sin \left(\frac{\alpha }{2}\right)=s\cdot \frac{\frac{w_{\text{a}}}{2}}{}\\ \text{(7)}& s& =& \frac{l}{w_{\text{a}}}\sqrt{l_{\text{a}}^2+\frac{1}{4}{l}_{\text{a}}^2}\\ \text{(8)}& \frac{\frac{l}{2}}{c_{\text{min}}}& =& \tan \left(\frac{\alpha }{2}\right)=\frac{w_{\text{a}}}{2l_{\text{a}}}\\ \text{(9)}& c_{\text{min}}& =& \frac{l\cdot l_{\text{a}}}{w_{\text{a}}}<s\\ \text{(10)}& c_{\text{max}}& =& 2s\\ \text{(11)}& c& =& \frac{1}{2}(c_{\text{max}}+c_{\text{min}})\\ \text{(12)}& \Delta c& =& \frac{1}{2}(c_{\text{max}}-c_{\text{min}})\end{array}$$

For polylines and circular arcs, the shortening is by c_min in each case; the end point or required end angle can be calculated exactly.
For splines, an iterative method is used to find a solution in order to achieve a reduction by $c$ according to equation 11 with a tolerance $\Delta c$ according to equation (12).

Polylines

Length correction for arrowheads

The following formulas are used for length correction on the final segment with penultimate point $P_0(x_0;y_0)$ and final point $P_1(x_1;y_1)$ if the second step results in a positive $q$ value:

$$\begin{array}{cccc}\text{(13)}& l_{\text{s}}& =& \sqrt{{(x_1-x_0)}^2+{(y_1-y_0)}^2}\\ \text{(14)}& q& =& \frac{l_{\text{s}}-c_{\text{min}}}{l_{\text{s}}}\\ \text{(15)}& x_1^{\text{'}}& =& x_0+q(x_1-x_0)\\ \text{(16)}& y_1^{\text{'}}& =& y_0+q(y_1-y_0)\end{array}$$

The final segment is drawn from point $P_0(x_0;y_0)$ to point $P_1^{\text{'}}(x_1^{\text{'}};y_1^{\text{'}})$.

Arcs

Calculating center point and radius

The following equations apply to an arc with center $P_{\text{c}}(x_{\text{c}};y_{\text{c}})$ and radius $r$ given by three consecutive points

• Start point $P_1(x_1;y_1)$,
• Point on arc $P_2(x_2;y_2)$ und
• Final point $P_3(x_3;y_3)$:

$$\begin{array}{cccc}\text{(17)}& r^2& =& {(x_1-x_{\text{c}})}^2+{(y_1-y_{\text{c}})}^2\\ \text{(18)}& r^2& =& {(x_2-x_{\text{c}})}^2+{(y_2-y_{\text{c}})}^2\\ \text{(19)}& r^2& =& {(x_3-x_{\text{c}})}^2+{(y_3-y_{\text{c}})}^2\end{array}$$

This system of equations (17,18,19) can be solved for $x_{\text{c}}$, $y_{\text{c}}$ and $r$.
The solutions for $x_{\text{c}}$ and $y_{\text{c}}$ are shown below in equations (20) and (21). The solution for $r$ is relatively complicated. It is easier to determine $r$ by substituting $x_{\text{c}}$ and $y_{\text{c}}$ into one of the equations above.

$$\begin{array}{cccc}\text{(20)}& x_{\text{c}}& =& -\frac{(y_2-y_1)y_3^2+(-y_2^2+y_1^2-x_2^2+x_1^2)y_3+y_1{y}_2^2+(-y_1^2+x_3^2-x_1^2)y_2+(x_2^2-x_3^2)y_1}{2\left(\right(x_2-x_1)y_3+(x_1-x_3)y_2+(x_3-x_2)y_1)}\\ \text{(21)}& y_{\text{c}}& =& \frac{(x_2-x_1)y_3^2+(x_1-x_3)y_2^2+(x_3-x_2)y_1^2+(x_2-x_1)x_3^2+(x_1^2-x_2^2)x_3+x_1{x}_2^2-x_1^2{x}_2}{2\left(\right(x_2-x_1)y_3+(x_1-x_3)y_2+(x_3-x_2)y_1)}\end{array}$$

We have to take care of the following special cases:

• Identical points
  2 or all 3 points are identical.
   
• Line
  The points are on a line.

The vector product $\overrightarrow{P_1{P}_2}\times \overrightarrow{P_2{P}_3}$ is considered to check for the special cases. Since $P_1$, $P_2$ and $P_3$ only have x- and y components, the vector product only has a z component:

$$\begin{array}{cc}\text{(22)}& z=(x_2-x_1)y_3+(x_1-x_3)y_2+(x_3-x_2)y_1\end{array}$$

If the z component is positive, the arc rotates in the mathematically positive direction (counterclockwise).
If the z component is negative, the arc rotates in the mathematically negative direction.
If the z component is 0, one of the above-mentioned special cases occurs. In this case, it is not a circular arc. $x_{\text{c}}$, $y_{\text{c}}$ and $r$ cannot be calculated.

Length correction for arrowheads

If a circular arc from $P_0$ to $P_1$is given by the radius $r$ and the angle $\alpha$ and is to be shortened so that the distance between the new end point $P_1^{\text{'}}$ and the old end point $P_1$ is $c$, the angle shortening ${\alpha }_{\text{c}}$ can be calculated as follows:

$$\begin{array}{cccc}\text{(23)}& c& =& \sqrt{{(x_1^{\text{'}}-x_1)}^2+{(y_1^{\text{'}}-y_1)}^2}\\ & & =& \sqrt{{(r\cos {\alpha }_{\text{c}}-r)}^2+{(0-r\sin {\alpha }_{\text{c}})}^2}\\ & & =& \sqrt{r^2-2r^2\cos {\alpha }_{\text{c}}+r^2{\cos }^2{\alpha }_{\text{c}}+r^2{\sin }^2{\alpha }_{\text{c}}}\\ & & =& r\sqrt{1-2\cos {\alpha }_{\text{c}}+{\cos }^2{\alpha }_{\text{c}}+{\sin }^2{\alpha }_{\text{c}}}\\ & & =& r\sqrt{2-2\cos {\alpha }_{\text{c}}}\\ \text{(24)}& 2-2\cos {\alpha }_{\text{c}}& =& {\left(\frac{c}{r}\right)}^2\\ \text{(25)}& 2\cos {\alpha }_{\text{c}}& =& 2-{\left(\frac{c}{r}\right)}^2\\ \text{(26)}& \cos {\alpha }_{\text{c}}& =& 1-\frac{c^2}{2r^2}\\ \text{(27)}& {\alpha }_{\text{c}}& =& \arccos (1-\frac{c^2}{2r^2})\end{array}$$

Rotated ellipses

Overview

To apply a fill pattern to a rotated ellipse, the bounding box of the rotated ellipse must be determined (minimum and maximum of the x and y extent of the ellipse).
The clip region is set to the path of the ellipse, then the fill pattern is drawn in the bounding box.

Distance of a point to a straight line through the zero point

For calculations on rotated ellipses, a formula for the distance $d$ of a point $P(x_{\text{p}};y_{\text{p}})$ to a straight line through the coordinate origin with the angle $\beta$ is required.

Equation (28) applies to the straight line:

$$\begin{array}{cccccc}\text{(28)}& {\tilde{k}}_{\text{G}}:& & \overrightarrow{r}\left(t\right)& =& t\cdot \left(\begin{array}{c}\cos \beta \\ \sin \beta \end{array}\right)\end{array}$$

For the distance between $P$ and a straight line point given by $t$, equation (29) applies:

$$\begin{array}{cccc}\text{(29)}& l\left(t\right)& =& \sqrt{{(t\cos \beta -x_{\text{p}})}^2+{(t\sin \beta -y_{\text{p}})}^2}\end{array}$$

The distance from the point to the straight line is equal to the length of the perpendicular from the point to the straight line. The scalar product of the perpendicular vector and the straight line vector must be 0.

$$\begin{array}{cccc}\text{(30)}& 0& =& \left(\overrightarrow{r}\right(t_{\text{L}})-{\overrightarrow{r}}_{\text{p}})·\overrightarrow{r}\left(t_{\text{L}}\right)\\ & & =& \left(\begin{array}{c}{t}_{\text{L}}\cos \beta -x_{\text{p}}\\ t_{\text{L}}\sin \beta -y_{\text{p}}\end{array}\right)·\left(\begin{array}{c}{t}_{\text{L}}\cos \beta \\ t_{\text{L}}\sin \beta \end{array}\right)\\ & & =& t_{\text{L}}^2{\cos }^2\beta -x_{\text{p}}{t}_{\text{L}}\cos \beta +t_{\text{L}}^2{\sin }^2\beta -y_{\text{p}}{t}_{\text{L}}\sin \beta \\ & & =& t_{\text{L}}(t_{\text{L}}-(x_{\text{p}}\cos \beta +y_{\text{p}}\sin \beta \left)\right)\\ \text{(31)}& t_{\text{L}}& =& x_{\text{p}}\cos \beta +y_{\text{p}}\sin \beta \\ \text{(32)}& d=l\left(t_{\text{L}}\right)& =& \sqrt{{(y_{\text{p}}-(y_{\text{p}}\sin \beta +x_{\text{p}}\cos \beta )\sin \beta )}^2+{(x_{\text{p}}-(y_{\text{p}}\sin \beta +x_{\text{p}}\cos \beta )\cos \beta )}^2}\end{array}$$

For the apparent solution $t_{\text{L}}=0$ the scalar product also results in 0, but not because of a right angle between the vectors, but because one vector has the length 0.

Bounding box of the rotated ellipse

To determine the bounding box of an ellipse rotated by $\alpha$, the height $h$ of the highest point and the width $w$ of the point furthest to the right are required.
In the left-hand diagram, $g_1$ is the upper horizontal tangent, $g_2$ is the right-hand vertical tangent. The height $h$ is the distance between the point of contact $P_h$ and the $x$-axis. The width $w$ is the distance between the point of contact $P_w$ and the $y$-axis.
For the calculation, the entire arrangement is rotated back by $-\alpha$, the ellipse is aligned with the axes again. The straight lines $g_1$ and $g_2$ are no longer parallel to the axes. The auxiliary lines $h_1$ and $h_2$ are obtained from the rotation of the axes. The height $h$ is now the distance from the point $P_h$ to the auxiliary line $h_1$ (formerly $x$-axis). The width $w$ is now the distance from the point $P_w$ to the auxiliary line $h_2$ (formerly $y$-axis).

$$\begin{array}{ccccccccc}\text{(33)}& & {\tilde{k}}_{\text{E}}:& & \overrightarrow{r}\left(t\right)& =& \left(\begin{array}{c}{r}_x\cos t\\ r_y\sin t\end{array}\right)& & 0\le t\le 2\mathrm{\pi }\\ \text{(34)}& & & & \frac{d}{dt}\overrightarrow{r}& =& \left(\begin{array}{c}-r_x\sin t\\ r_y\cos t\end{array}\right)\\ \text{(35)}& & & & \tan (\mathrm{\pi }-\alpha )& =& \frac{r_y\cos t_{\text{h}}}{-r_x\sin t_{\text{h}}}\\ \text{(36)}& & & & t_{\text{h}}& =& \arctan (-\frac{r_y}{r_x\tan (\mathrm{\pi }-\alpha )})\\ \text{(37)}& & & & tan(\frac{\mathrm{\pi }}{2}-\alpha )& =& \frac{r_y\cos t_{\text{w}}}{-r_x\sin t_{\text{w}}}\\ \text{(38)}& & & & t_{\text{w}}& =& \arctan (-\frac{r_y}{r_x\tan (\frac{\mathrm{\pi }}{2}-\alpha )})\end{array}$$

Equation (33) describes the curve of a non-rotated ellipse aligned along the axes as shown in the figure on the right. The ellipse is drawn in a mathematically positive sense.
The direction vector at each point is the first derivative according to equation (34).

For point $P_h$, this direction vector must have the angle $\mathrm{\pi }-\alpha$ according to equation (35).
This can be converted to equation (36) to determine $t_{\text{h}}$.

Similarly, the direction vector for point $P_w$ must have the angle $\frac{\mathrm{\pi }}{2}-\alpha$.
This means that $t_{\text{w}}$ can be determined using equation (38).

Using $t_{\text{h}}$ and $t_{\text{w}}$, we can calculate $P_{\text{h}}(x_{\text{h}};y_{\text{h}})$ and $P_{\text{w}}(x_{\text{w}};y_{\text{w}})$.

The height $h$ of the rotated ellipse is now the distance from the point $P_{\text{h}}(x_{\text{h}};y_{\text{h}})$ to the straight line $h_1$ through the coordinate origin with the angle ${\beta }_{\text{h}}=-\alpha$.

The width $w$ of the rotated ellipse is now the distance from the point $P_{\text{w}}(x_{\text{w}};y_{\text{w}})$ to the straight line $h_2$ through the coordinate origin with the angle ${\beta }_{\text{w}}=\frac{\mathrm{\pi }}{2}-\alpha$.

The following applies to the bounding box of a rotated ellipse with center in the coordinate origin:

$$\begin{array}{ccccc}\text{(39)}& x_{\text{l}}& =& -w& \text{ Left boundary}\\ \text{(40)}& x_{\text{r}}& =& w& \text{ Right boundary}\\ \text{(41)}& y_{\text{b}}& =& -h& \text{ Lower boundary}\\ \text{(42)}& y_{\text{t}}& =& h& \text{ Upper boundary}\end{array}$$

If the center of the rotated ellipse is not at the coordinates origin, the bounding box also shifts accordingly.

Splines

Overview

Curves in ${ℝ}^2$ can be described by equation:

$$\begin{array}{cccccccc}\text{(43)}& \tilde{k}:& & \overrightarrow{r}\left(t\right)& =& \left(\begin{array}{c}x\left(t\right)\\ y\left(t\right)\end{array}\right)& & t_{\text{s}}\le t\le t_{\text{e}}\end{array}$$

In the field of computer graphics, $0\le t\le 1$ is often used for the entire curve or for a curve segment.

A spline describes a continuous curve by a set of discrete values.

Bezier splines

For cubic Bezier splines, each segment is described by start point $P_{\text{s}}(x_{\text{s}};y_{\text{s}})$ and end point $P_{\text{e}}(x_{\text{e}};y_{\text{e}})$ as well as two control points $P_{\text{cs}}(x_{\text{cs}};y_{\text{cs}})$ and $P_{\text{ce}}(x_{\text{ce}};y_{\text{ce}})$.
$P_{\text{cs}}$ denotes the control point “to the right” of the start point. $P_{\text{ce}}$ denotes the control point “to the left” of the end point.
In the literature, the notation $P_i$ and $P_j$ is often used for the start and end points and $P_{i+}$ and $P_{j-}$ or $P_i^{+}$ and $P_j^{-}$ for the control points.

$$\begin{array}{cccc}\text{(44)}& \overrightarrow{r}\left(t\right)& =& {(1-t)}^3·{\overrightarrow{r}}_{\text{s}}+3·{(1-t)}^2·t·{\overrightarrow{r}}_{\text{cs}}+3·(1-t)·t^2·{\overrightarrow{r}}_{\text{ce}}+t^3·{\overrightarrow{r}}_{\text{e}}\\ \text{(45)}& \dot{\overrightarrow{r}}=\frac{d}{dt}\overrightarrow{r}& =& (-3+6t-3t^2){\overrightarrow{r}}_{\text{s}}+3(1-4t+3t^2){\overrightarrow{r}}_{\text{cs}}+3(2t-3t^2){\overrightarrow{r}}_{\text{ce}}+3t^2{\overrightarrow{r}}_{\text{e}}\\ \text{(46)}& \dot{\overrightarrow{r}}\left(0\right)& =& -3{\overrightarrow{r}}_{\text{s}}+3{\overrightarrow{r}}_{\text{cs}}\\ \text{(47)}& \dot{\overrightarrow{r}}\left(1\right)& =& -3{\overrightarrow{r}}_{\text{ce}}+3{\overrightarrow{r}}_{\text{e}}\\ \text{(48)}& {\overrightarrow{r}}_{\text{cs}}& =& {\overrightarrow{r}}_{\text{s}}+\frac{1}{3}\dot{\overrightarrow{r}}\left(0\right)\\ \text{(49)}& {\overrightarrow{r}}_{\text{ce}}& =& {\overrightarrow{r}}_{\text{e}}-\frac{1}{3}\dot{\overrightarrow{r}}\left(1\right)\end{array}$$

The segment is traversed with the parameter $t$ in the interval $0\le t\le 1$, resulting in curve point vectors according to equation (44).

The first derivative according to equation (45) gives the direction vectors.

This results in direction vectors at the boundary points corresponding to equations (46) and (47).

These equations can be rearranged to equations (48) and (49) in order to calculate the control points if the first derivative of the position vector in the boundary points is known.

One disadvantage of Bezier splines is that it is difficult for inexperienced users to estimate how manipulating the control points will affect the curve.

Bounding box of Bezier spline segments

To determine the bounding box of a Bezier spline segment, extreme points of the x and y values for $0\le t\le 1$ must be taken into account in addition to the start and end points.

$$\begin{array}{cccc}\text{(50)}& x\left(t\right)& =& {(1-t)}^3{x}_{\text{s}}+3{(1-t)}^{2}t{x}_{\text{cs}}+3(1-t)t^2{x}_{\text{ce}}+t^3{x}_{\text{e}}\\ \text{(51)}& & =& a{t}^3+b{t}^2+ct+d\\ \text{(52)}& a& =& x_{\text{e}}-3x_{\text{ce}}+3x_{\text{cs}}-x_{\text{s}}\\ \text{(53)}& b& =& 3x_{\text{ce}}-6x_{\text{cs}}+3x_{\text{s}}\\ \text{(54)}& c& =& 3x_{\text{cs}}-3x_{\text{s}}\\ \text{(55)}& d& =& x_{\text{s}}\\ \text{(56)}& 0& =& {\frac{dx}{dt}|}_{t=t_{\text{m}}}\\ \text{(57)}& t_{\text{m}}& =& \{\begin{array}{cc}\frac{-b\pm \sqrt{b^2-3ac}}{3a}& \text{ if }a\ne 0\\ -\frac{c}{2b}& \text{ if }a=0\text{ and }b\ne 0\\ \text{no solution}& \text{ if }a=0\text{ and }b=0\end{array}\end{array}$$

Equation (50) shows the calculation of the $x$ coordinate as a function of $t$.
This calculation can be simplified to a polynomial of $t$, the coefficients $a$…$d$ are determined using equations (52) to (55).

For local extrema, the first derivative is 0, see equation (56).

If equation (51) is a cubic polynomial with $a\ne 0$, there are 2 extreme points corresponding to equation (57).
If equation (51) is a quadratic polynomial with $a=0$ and $b\ne 0$, there is only one extreme point.
If both $a=0$ and $b=0$, the line is straight and there are no local extrema.

For the local extreme points $t_{\text{m}}$ with $0\le t_{\text{m}}\le 1$, the x values must be calculated and taken into account when determining the bounding box.

The same procedure must be followed for the y values.

Approximation of circular arcs using Bezier splines

The following investigation was inspired by the German Wikipedia page on “Bezierkurven” (Bezier curves). There a method is given how control points can be obtained for the approximate representation of a quarter circle by a Bezier spline segment. This method is generalized here in order to be able to represent circular arcs with any opening angle. In wxd2lat the formula is used for circular arc segments with $\left|\alpha \right|\le \frac{\mathrm{\pi }}{2}$, larger circular arcs are then realized by several Bezier segments. The previous section showed how the control points for a Bezier spline segment can be obtained from the start and end points of a parametric curve and the coordinate derivatives in the start and end points. This generates a Bezier spline segment that comes as close as possible to the $x\left(t\right)$ and $y\left(t\right)$ curves. However, the main aim of the approximation is to achieve the best possible approximation to the desired $x$-$y$-curves. It is therefore investigated here whether a variation of the control points leads to better results.

The Bezier curves, whose control points were obtained using equations (48) and (49), have the required radius at start and end point, but in the interior of the interval the curve runs inside the circle, i.e. the radius is undershot. To change the curve, the control points are moved a little further away from the start and end points, but they remain on the tangents at the start and end points. Due to the symmetry of the arrangement, both control points are kept at the same distance from the respective end point.

$$\begin{array}{ccccc}\text{(58)}& {\tilde{k}}_{\text{k}}:& {\overrightarrow{r}}_{\text{k}}\left(t\right)& =& \left(\begin{array}{c}r\cos (\alpha t)\\ r\sin (\alpha t)\end{array}\right)\\ \text{(59)}& & {\stackrel{·}{\overrightarrow{r}}}_{\text{k}}=\frac{d}{dt}{\overrightarrow{r}}_{\text{k}}& =& \left(\begin{array}{c}-r\alpha \sin (\alpha t)\\ r\alpha \cos (\alpha t)\end{array}\right)\\ \text{(60)}& & {\overrightarrow{r}}_{\text{s}}={\overrightarrow{r}}_{\text{k}}\left(0\right)& =& \left(\begin{array}{c}r\\ 0\end{array}\right)\\ \text{(61)}& & {\overrightarrow{r}}_{\text{e}}={\overrightarrow{r}}_{\text{k}}\left(1\right)& =& \left(\begin{array}{c}r\cos \alpha \\ r\sin \alpha \end{array}\right)\\ \text{(62)}& & {\overrightarrow{r}}_{\text{cs}}& =& {\overrightarrow{r}}_{\text{s}}+\kappa {\stackrel{·}{\overrightarrow{r}}}_{\text{k}}\left(0\right)\\ \text{(63)}& & {\overrightarrow{r}}_{\text{ce}}& =& {\overrightarrow{r}}_{\text{e}}-\kappa {\stackrel{·}{\overrightarrow{r}}}_{\text{k}}\left(1\right)\\ \text{(64)}& {\tilde{k}}_{\text{b}}:& {\overrightarrow{r}}_{\text{b}}\left(t\right)& =& {(1-t)}^3{\overrightarrow{r}}_{\text{s}}+3{(1-t)}^{2}t({\overrightarrow{r}}_{\text{s}}+\kappa {\stackrel{·}{\overrightarrow{r}}}_{\text{k}}(0\left)\right)+3(1-t)t^2({\overrightarrow{r}}_{\text{e}}-\kappa {\stackrel{·}{\overrightarrow{r}}}_{\text{k}}(1\left)\right)+t^3{\overrightarrow{r}}_{\text{e}}\\ \text{(65)}& & r& =& \left|{\overrightarrow{r}}_{\text{b}}\right(\frac{1}{2}\left)\right|\\ \text{(66)}& & \kappa & =& \frac{2\sqrt{8(1-\cos \alpha )}-4\sin \alpha }{3\alpha (1-\cos \alpha )}\end{array}$$

Equation (58) applies to the vectors of the points on the arc.
The direction vector at each point is calculated from the first derivative according to equation (59).
The start and end points of the arc are given by equations (60) and (61).
In the calculation of the control points with equations (62) and (63), the derivatives are not multiplied by a factor of $\frac{1}{3}$, but by a still unknown coefficient $\kappa$.
This coefficient $\kappa$ must be selected so that the center of the Bezier segment has the distance $r$ to the center of the circular arc. This requirement is formulated as equation (65).
If equation (64) is inserted into equation (65) and converted to $\kappa$, the solution corresponding to equation (66) is obtained.

This results in quite long equations. The mathematics software wxMaxima with the following commands was therefore used to insert, convert and solve equations:

/* x and y coordinates of the circular arc. */
X: R * cos(alpha * t);
Y: R * sin(alpha * t);

/* First and final point of the arc. */
xs: at(X, t=0);
ys: at(Y, t=0);
xe: at(X, t=1);
ye: at(Y, t=1);

/* First derivative of the coordinates. */
dXdt: diff(X, t);
dYdt: diff(Y, t);

/* Control point formulas, kappa is still unknown. */
xcs: xs + kappa * at(dXdt, t=0);
ycs: ys + kappa * at(dYdt, t=0);
xce: xe - kappa * at(dXdt, t=1);
yce: ye - kappa * at(dYdt, t=1);

/* x and y coordinates of the Bezier spline. */
xb: (1-t)^3*xs + 3*(1-t)^2*t*xcs + 3*(1-t)*t^2*xce + t^3*xe;
yb: (1-t)^3*ys + 3*(1-t)^2*t*ycs + 3*(1-t)*t^2*yce + t^3*ye;

/* For t=0.5 the distance from the center point to the
   Bezier spline point is required to be R.
   We are searching for an appropriate kappa.
*/
res: solve( at(xb,t=1/2)^2 + at(yb,t=1/2)^2 = R^2, kappa);

/* Simplify result. */
trigsimp(rhs(res[2]));

X-splines

Cross-splines (X-splines) were introduced in 1995 by Carole Blanc and Christophe Schlick. X-splines are not explained in detail here, please refer to the corresponding SIGGRAPH publication 〈BS1995〉. The description here is limited to the use of X-splines in WXD files and the handling in the programs wxdkdraw and wxd2lat.

$$\begin{array}{cccc}\text{(67)}& \mathrm{f}(u,p)& =& \{\begin{array}{cc}{u}^3(10-p+(2p-15)u+(6-p)u^2)& \text{ if }u\in [0;1]\\ 0& \text{ otherwise}\end{array}\\ \text{(68)}& \mathrm{e}(u,p,q)& =& \{\begin{array}{cc}qu+2q{u}^2-2q{u}^4-q{u}^5& \text{ if }u\in [-1;0)\\ qu+2q{u}^2+(10-12q-p)u^3+(2p+14q-15)u^4+(6-5q-p)u^5& \text{ if }u\in [0;1]\\ 0& \text{ otherwise}\end{array}\\ \text{(69)}& \mathrm{r}(u,p)=\frac{d\mathrm{f}}{du}& =& \{\begin{array}{cc}5(6-p)u^4+4(2p-15)u^3+3(10-p)u^2& \text{ if }u\in [0;1]\\ 0& \text{ otherwise}\end{array}\\ \text{(70)}& \mathrm{s}(u,p,q)=\frac{d\mathrm{e}}{du}& =& \{\begin{array}{cc}q+4qu-8q{u}^3-5q{u}^4& \text{ if }u\in [-1;0)\\ 5(6-5q-p)u^4+4(2p+14q-15)u^3+3(10-12q-p)u^2+4qu+q& \text{ if }u\in [0;1]\\ 0& \text{ otherwise}\end{array}\end{array}$$

The function $\mathrm{f}\left(u\right)$ with parameter $p$ is used as blending function for the approximation, see equation (67).
The function $\mathrm{e}\left(u\right)$ with parameters $p$ and $q$ is used as blending function for the interpolation, see equation (68).
Equations (69) and (70) show the derivatives of the functions.

When using X-splines in WXD files, equidistant control points with $\Delta t=1$ are assumed.
An X-spline is described by $n$ control points with indices in the range from 0 to $n-1$, whereby each control point $P_k$ at time $t=T_k$ is assigned an additional parameter $s_k$ with $-1\le s_k\le 1$.
Points with $-1\le s_k<0$ are interpolation points. Points with $0\le s_k\le 1$ are approximation points; angular points are possible for $s_k=0$.

Each control point $P_k$ has a left-sided blending function $F_k^{-}$ and a right-sided blending function $F_k^{+}$. These blending functions indicate how strongly the control point affects the course in the adjacent segments. The blending functions each extend over up to 2 segments, so a control point can influence a total of 4 segments.
A curve segment is influenced by the two control points at the segment ends and by their neighbors. The $s_k$ value of each control point $P_k$ determines the type and parameters of the right- and left-sided blending functions of the neighboring points (but not of the point $P_k$ itself).

The following applies to approximation points, $0\le s_k\le 1$:

$$\begin{array}{ccccccc}\text{(71)}& T_{k-1}^{\mathrm{+}}& =& T_k+s_k& T_{k+1}^{\mathrm{-}}& =& T_k-s_k\\ \text{(72)}& p_{k-1}^{\mathrm{+}}& =& 2{(T_{k-1}^{+}-T_{k-1})}^2& p_{k+1}^{\mathrm{-}}& =& 2{(T_{k+1}^{-}-T_{k+1})}^2\\ \text{(73)}& F_{k-1}^{\mathrm{+}}\left(t\right)& =& \mathrm{f}(\frac{t-T_{k-1}^{+}}{T_{k-1}-T_{k-1}^{+}},p_{k-1}^{+})& F_{k+1}^{\mathrm{-}}\left(t\right)& =& \mathrm{f}(\frac{t-T_{k+1}^{-}}{T_{k+1}-T_{k+1}^{-}},p_{k+1}^{-})\\ \text{(74)}& \frac{d}{dt}{F}_{k-1}^{\mathrm{+}}& =& \frac{1}{T_{k-1}-T_{k-1}^{+}}·\mathrm{r}(\frac{t-T_{k-1}^{+}}{T_{k-1}-T_{k-1}^{+}},p_{k-1}^{+})& \frac{d}{dt}{F}_{k+1}^{\mathrm{-}}& =& \frac{1}{T_{k+1}-T_{k+1}^{-}}·\mathrm{r}(\frac{t-T_{k+1}^{-}}{T_{k+1}-T_{k+1}^{-}},p_{k+1}^{-})\end{array}$$

Equation (71) shows how far the effective range of the blending functions of the neighboring points extends.
Equation (72) is used to determine the $p$ parameter of the blending function.
The function $\mathrm{f}(u,p)$ is used as the right-sided blending function of the left neighboring point and as the left-sided blending function of the right neighboring point, see equation (73).
Equation (74) shows the first derivatives of the blending functions.

The following applies to interpolation points, $-1\le s_k<0$:

$$\begin{array}{ccccccc}\text{(75)}& p_{k-1}^{\mathrm{+}}& =& 2& p_{k+1}^{\mathrm{-}}& =& 2\\ \text{(76)}& q_{k-1}^{\mathrm{+}}& =& -\frac{s_k}{2}& q_{k+1}^{\mathrm{-}}& =& -\frac{s_k}{2}\\ \text{(77)}& F_{k-1}^{\mathrm{+}}\left(t\right)& =& \mathrm{e}(T_k-t,p_{k-1}^{+},q_{k-1}^{+})& F_{k+1}^{\mathrm{-}}\left(t\right)& =& \mathrm{e}(t-T_k,p_{k+1}^{-},q_{k+1}^{-})\\ \text{(78)}& \frac{d}{dt}{F}_{k-1}^{\mathrm{+}}& =& -\mathrm{s}(T_k-t,p_{k-1}^{+},q_{k-1}^{+})& \frac{d}{dt}{F}_{k+1}^{\mathrm{-}}& =& \mathrm{s}(t-T_k,p_{k+1}^{-},q_{k+1}^{-})\end{array}$$

Equations (75) and (76) are used to calculate the parameters $p$ and $q$ for the blending functions of the neighboring points.
The function $\mathrm{e}(u,p,q)$ is used as the right-sided blending function of the left neighboring point and as the left-sided blending function of the right neighboring point, see equation (77).
Equation (78) shows the first derivatives of the blending functions.

After the functions $F_k^{-}$ and $F_k^{+}$ have been defined for all points $P_k$, curve points and first derivatives of the coordinates can be calculated for each curve segment with start point $P_i$ and end point $P_{i+1}$ using:

$$\begin{array}{cccc}\text{(79)}& z_x\left(t\right)& =& x_{i-1}·F_{i-1}^{+}\left(t\right)+x_i·F_i^{+}\left(t\right)+x_{i+1}·F_{i+1}^{-}\left(t\right)+x_{i+2}·F_{i+2}^{-}\left(t\right)\\ \text{(80)}& z_y\left(t\right)& =& y_{i-1}·F_{i-1}^{+}\left(t\right)+y_i·F_i^{+}\left(t\right)+y_{i+1}·F_{i+1}^{-}\left(t\right)+y_{i+2}·F_{i+2}^{-}\left(t\right)\\ \text{(81)}& n\left(t\right)& =& F_{i-1}^{+}\left(t\right)+F_i^{+}\left(t\right)+F_{i+1}^{-}\left(t\right)+F_{i+2}^{-}\left(t\right)\\ \text{(82)}& z_x^{\text{'}}\left(t\right)=\frac{d{z}_x}{dt}& =& x_{i-1}·\frac{d}{dt}{F}_{i-1}^{+}\left(t\right)+x_i·\frac{d}{dt}{F}_i^{+}\left(t\right)+x_{i+1}·\frac{d}{dt}{F}_{i+1}^{-}\left(t\right)+x_{i+2}·\frac{d}{dt}{F}_{i+2}^{-}\left(t\right)\\ \text{(83)}& z_y^{\text{'}}\left(t\right)=\frac{d{z}_y}{dt}& =& y_{i-1}·\frac{d}{dt}{F}_{i-1}^{+}\left(t\right)+y_i·\frac{d}{dt}{F}_i^{+}\left(t\right)+y_{i+1}·\frac{d}{dt}{F}_{i+1}^{-}\left(t\right)+y_{i+2}·\frac{d}{dt}{F}_{i+2}^{-}\left(t\right)\\ \text{(84)}& n^{\text{'}}\left(t\right)=\frac{dn}{dt}& =& \frac{d}{dt}{F}_{i-1}^{+}\left(t\right)+\frac{d}{dt}{F}_i^{+}\left(t\right)+\frac{d}{dt}{F}_{i+1}^{-}\left(t\right)+\frac{d}{dt}{F}_{i+2}^{-}\left(t\right)\\ \text{(85)}& x\left(t\right)& =& \frac{z_x\left(t\right)}{n\left(t\right)}\\ \text{(86)}& y\left(t\right)& =& \frac{z_y\left(t\right)}{n\left(t\right)}\\ \text{(87)}& x^{\text{'}}\left(t\right)=\frac{dx}{dt}& =& \frac{n\left(t\right)·z_x^{\text{'}}\left(t\right)-z_x\left(t\right)·n^{\text{'}}\left(t\right)}{n^2\left(t\right)}\\ \text{(88)}& y^{\text{'}}\left(t\right)=\frac{dy}{dt}& =& \frac{n\left(t\right)·z_y^{\text{'}}\left(t\right)-z_y\left(t\right)·n^{\text{'}}\left(t\right)}{n^2\left(t\right)}\end{array}$$

For open splines, the first summand for the first segment and the last summand for the last segment are omitted in equations (79…84).
To simplify the calculation program, each X-spline segment is placed in an arrangement with four points $A$, $B$, $C$, and $D$ so that the control point for the start of the segment is at $B$ and the control point for the end point of the segment is at $C$. $A$ then corresponds to the “left” neighboring control point, $D$ to the “right”.

Approximation of X-splines by Bezier splines

The output formats provided by wxd2lat support Bezier splines. It is necessary to approximate X-splines using Bezier splines.
First, curve points are calculated that correspond to the control points ($t=T_1$, $t=T_2$…). To calculate the control points for the Bezier splines, the derivative in the curve points is required. As X-splines can have angular points in the curve points that correspond to the control points, both a “left-sided” and a “right-sided” derivative are calculated.
X-splines are fifth-degree curves and therefore differ from third-degree Bezier splines. It makes sense to represent each X-spline segment by several Bezier spline segments.
For this purpose, curve points and derivatives are also calculated between the curve points calculated in the previous step. No angular points can occur here, so it is sufficient to calculate the derivative once in each point.
If each X-spline segment is represented by several ($m$) Bezier spline segments, the slopes must be corrected. Bezier splines start and end at $t=0$ and $t=1$. However, the slopes calculated so far refer to areas with $t=t_{\text{s}}$ and $t=t_{\text{s}}+\frac{1}{m}$. Using the calculated curve points as the start and end points of Bezier splines corresponds to a stretching along the $t$ axis by the factor $m$. This is accompanied by a reduction in the slope, so all previously calculated derivatives must be corrected by dividing them by $m$.

Length calculation on splines

The length calculation for X and Bezier splines or spline segments is approximated in wxd2lat. For this purpose, the spline is divided into intervals with even $t$ steps and the points are calculated for the interval boundaries. The distances between these points are added up.
In each pass, the number of intervals is doubled until the change in the sum from one pass to the following pass falls below the desired accuracy limit.

Length correction for arrowheads

Length correction on splines is relatively difficult, as the formulas cannot be analytically rearranged to obtain a $t$ for a given distance to the end point.
To determine a $t$ for which the length from the associated point to the end of the spline has the specified value $s$, an iterative method (Regula falsi modified according to Anderson-Björck) is used. First, it is checked whether $s$ is smaller than the total length of the spline. If so, the $t$ for the first point (0) and the final point (n-1) are used as starting values for the interval limits.

---

Literature

〈BS1995〉

Carole Blanc, Christophe Schlick:
X-Splines: A Spline Model Designed for the End-User
Proceedings of the SIGGRAPH 1995

← Previous

↑ Home

→ Next