next up previous contents
Next: Return code Up: Solving systems of distance Previous: Principle   Contents

Implementation

A system of $m$ distance functions has a specific description. First consider distance function that involve only points of constant. Such function may be written as:

\begin{displaymath}
\sum (x_i-x_j)^2+L_i =0
\end{displaymath}

where the maximal number of square term is $n$ and is described by a row of 2 matrices APOW, ACONS and a vector LI. APOW is an integer matrix with $2n$ columns and $m$ rows that contain the unknown number of each term in the function and in which a 0 means that the unknown is a constant. The value of theses constants are given in the matrix of real ACONS of size $m \times 2n$. Finally the value of the constant $L_i$ is indicated in the vector LI of size $m$. For example consider a system involving the 4 unknowns $x_1, x_2, y_1, y_2$ numbered from 1 to 4:

\begin{eqnarray*}
&&x_1^2+(y_1-4)^2-6 =0\\
&&(x_1-x_2)^2+(y_1-y_2)^2-12=0
\end{eqnarray*}

In that case APOW, ACONS, LI will be:

\begin{displaymath}
{\tt APOW}= \left( \begin{tabular}{cccc}
1& 0& 3& 0\\
1& 2 ...
...I}= \left( \begin{tabular}{c} -6\\ -12\\ \end{tabular} \right)
\end{displaymath}

The two first elements of the first row of APOW (1, 0) describes the first square term of the first equation and state that it is $(x_1-a)^2$, the value of $a$ being given in the ACONS(1,2). Note that each square term must be written as (unknown-unknown or constant$)^2$ and not as (constant -unknown$)^2$.

Consider now function involving virtual points. Each square term may thus be written as:

\begin{displaymath}
(\sum \lambda_j x_j -X_k)^2
\end{displaymath}

where $X_k$ may be either a constant, an unknown or the coordinate of a virtual point. Let $k$ be the number of term of the form $\sum \lambda_j x_j$ existing in the system. Such equation is described by a matrix AVARV with $k$ rows and a number of columns equal to the number of unknowns. Each term $\sum \lambda_j x_j$ is numbered from 1 to k and the row $i$ of AVARV will contain in position $j$ the value of $\lambda_j$. The existence of the coordinate of a virtual point in a distance function will be indicated in APOW by a negative number whose opposite is the number of the virtual coordinates. Hence if we add to the previous system the third equation:

\begin{displaymath}
(0.1 x_1-0.2 x_2-3)^2+(0.1 y_1-0.2y_2-1)^2-10 =0
\end{displaymath}

the third row of APOW will be (-1 0 -2 0), the third row of ACONS will be (0 3 0 1) and the third row of LI will be -10. AVARV will have 2 row and 4 columns and is given as:

\begin{displaymath}
{\tt AVARV}= \left( \begin{tabular}{cccc}
0.1 & -0.2 & 0 & 0\\
0 & 0 & 0.1 & -0.2\\
\end{tabular} \right)
\end{displaymath}

Among the $m$ equations there will be $p$ equations involving virtual points. The system must be written in such way that first are defined the $m-p$ equations not involving virtual points and then the $p$ equations. Note also that in the current implementation inequalities are handled although with less efficiency than equations. The algorithm is implemented as:
 
int Solve_Distance(int DimVar,int DimEq,
                   INTEGER_VECTOR &Type_Eq,
                   INTEGER_MATRIX &APOW,MATRIX &ACONS,VECTOR &LI,
                   int p,int k,MATRIX &AVARV,
                   INTERVAL_VECTOR & TheDomain, 
                   int M,
                   double epsilonf,
                   int Stop,
                   INTERVAL_MATRIX & Solution,int Nb,
                   int (* Simp_Proc)(INTERVAL_VECTOR &))
The arguments are: The argument Simp_Proc in this procedure may be omitted.

The following variables play also a role in the computation:



Subsections
next up previous contents
Next: Return code Up: Solving systems of distance Previous: Principle   Contents
Jean-Pierre Merlet 2012-12-20