include/basegfx/matrix/hommatrixtemplate.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #pragma once
  21
  22 #include <sal/types.h>
  23 #include <basegfx/numeric/ftools.hxx>
  24 #include <cmath>
  25
  26 namespace basegfx::internal
  27     {
  28
  29         inline constexpr double implGetDefaultValue(sal_uInt16 nRow, sal_uInt16 nColumn)
  30         {
  31             if(nRow == nColumn)
  32                 return 1.0;
  33             return 0.0;
  34         }
  35
  36         template < sal_uInt16 RowSize > class ImplMatLine
  37         {
  38             double                                          mfValue[RowSize];
  39
  40         public:
  41             ImplMatLine() = default;
  42
  43             explicit ImplMatLine(sal_uInt16 nRow)
  44             {
  45                 for(sal_uInt16 a(0); a < RowSize; a++)
  46                 {
  47                     mfValue[a] = implGetDefaultValue(nRow, a);
  48                 }
  49             }
  50
  51             double get(sal_uInt16 nColumn) const
  52             {
  53                 return mfValue[nColumn];
  54             }
  55
  56             void set(sal_uInt16 nColumn, const double& rValue)
  57             {
  58                 mfValue[nColumn] = rValue;
  59             }
  60         };
  61
  62         template < sal_uInt16 RowSize > class ImplHomMatrixTemplate
  63         {
  64             ImplMatLine< RowSize >                          maLine[RowSize];
  65
  66         public:
  67             // Is last line used?
  68             bool isLastLineDefault() const
  69             {
  70                 for(sal_uInt16 a(0); a < RowSize; a++)
  71                 {
  72                     const double fDefault(implGetDefaultValue((RowSize - 1), a));
  73                     const double fLineValue(maLine[RowSize-1].get(a));
  74
  75                     if(fDefault != fLineValue)
  76                     {
  77                         return false;
  78                     }
  79                 }
  80                 return true;
  81             }
  82
  83             ImplHomMatrixTemplate()
  84             {
  85                 // complete initialization with identity matrix, all lines
  86                 // were initialized with a trailing 1 followed by 0's.
  87                 for(sal_uInt16 a(0); a < RowSize; a++)
  88                 {
  89                     for(sal_uInt16 b(0); b < RowSize; b++)
  90                         maLine[a].set(b, implGetDefaultValue(a, b) );
  91                 }
  92             }
  93
  94             ImplHomMatrixTemplate(const ImplHomMatrixTemplate& rToBeCopied)
  95             {
  96                 operator=(rToBeCopied);
  97             }
  98
  99             ImplHomMatrixTemplate& operator=(const ImplHomMatrixTemplate& rToBeCopied)
 100             {
 101                 if (this != &rToBeCopied)
 102                 {
 103                     // complete initialization using copy
 104                     for(sal_uInt16 a(0); a < RowSize; a++)
 105                     {
 106                         maLine[a] = rToBeCopied.maLine[a];
 107                     }
 108                 }
 109                 return *this;
 110             }
 111
 112             static sal_uInt16 getEdgeLength() { return RowSize; }
 113
 114             double get(sal_uInt16 nRow, sal_uInt16 nColumn) const
 115             {
 116                 return maLine[nRow].get(nColumn);
 117             }
 118
 119             void set(sal_uInt16 nRow, sal_uInt16 nColumn, const double& rValue)
 120             {
 121                 maLine[nRow].set(nColumn, rValue);
 122             }
 123
 124             // Left-upper decomposition
 125             bool ludcmp(sal_uInt16 nIndex[], sal_Int16& nParity)
 126             {
 127                 double fBig, fSum, fDum;
 128                 double fStorage[RowSize];
 129                 sal_uInt16 a, b, c;
 130
 131                 // #i30874# Initialize nAMax (compiler warns)
 132                 sal_uInt16 nAMax = 0;
 133
 134                 nParity = 1;
 135
 136                 // Calc the max of each line. If a line is empty,
 137                 // stop immediately since matrix is not invertible then.
 138                 for(a = 0; a < RowSize; a++)
 139                 {
 140                     fBig = 0.0;
 141
 142                     for(b = 0; b < RowSize; b++)
 143                     {
 144                         double fTemp(fabs(get(a, b)));
 145
 146                         if(::basegfx::fTools::more(fTemp, fBig))
 147                         {
 148                             fBig = fTemp;
 149                         }
 150                     }
 151
 152                     if(::basegfx::fTools::equalZero(fBig))
 153                     {
 154                         return false;
 155                     }
 156
 157                     fStorage[a] = 1.0 / fBig;
 158                 }
 159
 160                 // start normalizing
 161                 for(b = 0; b < RowSize; b++)
 162                 {
 163                     for(a = 0; a < b; a++)
 164                     {
 165                         fSum = get(a, b);
 166
 167                         for(c = 0; c < a; c++)
 168                         {
 169                             fSum -= get(a, c) * get(c, b);
 170                         }
 171
 172                         set(a, b, fSum);
 173                     }
 174
 175                     fBig = 0.0;
 176
 177                     for(a = b; a < RowSize; a++)
 178                     {
 179                         fSum = get(a, b);
 180
 181                         for(c = 0; c < b; c++)
 182                         {
 183                             fSum -= get(a, c) * get(c, b);
 184                         }
 185
 186                         set(a, b, fSum);
 187                         fDum = fStorage[a] * fabs(fSum);
 188
 189                         if(::basegfx::fTools::moreOrEqual(fDum, fBig))
 190                         {
 191                             fBig = fDum;
 192                             nAMax = a;
 193                         }
 194                     }
 195
 196                     if(b != nAMax)
 197                     {
 198                         for(c = 0; c < RowSize; c++)
 199                         {
 200                             fDum = get(nAMax, c);
 201                             set(nAMax, c, get(b, c));
 202                             set(b, c, fDum);
 203                         }
 204
 205                         nParity = -nParity;
 206                         fStorage[nAMax] = fStorage[b];
 207                     }
 208
 209                     nIndex[b] = nAMax;
 210
 211                     // here the failure of precision occurs
 212                     const double fValBB(fabs(get(b, b)));
 213
 214                     if(::basegfx::fTools::equalZero(fValBB))
 215                     {
 216                         return false;
 217                     }
 218
 219                     if(b != (RowSize - 1))
 220                     {
 221                         fDum = 1.0 / get(b, b);
 222
 223                         for(a = b + 1; a < RowSize; a++)
 224                         {
 225                             set(a, b, get(a, b) * fDum);
 226                         }
 227                     }
 228                 }
 229
 230                 return true;
 231             }
 232
 233             void lubksb(const sal_uInt16 nIndex[], double fRow[]) const
 234             {
 235                 sal_uInt16 b, ip;
 236                 sal_Int16 a, a2 = -1;
 237                 double fSum;
 238
 239                 for(a = 0; a < RowSize; a++)
 240                 {
 241                     ip = nIndex[a];
 242                     fSum = fRow[ip];
 243                     fRow[ip] = fRow[a];
 244
 245                     if(a2 >= 0)
 246                     {
 247                         for(b = a2; b < a; b++)
 248                         {
 249                             fSum -= get(a, b) * fRow[b];
 250                         }
 251                     }
 252                     else if(!::basegfx::fTools::equalZero(fSum))
 253                     {
 254                         a2 = a;
 255                     }
 256
 257                     fRow[a] = fSum;
 258                 }
 259
 260                 for(a = (RowSize - 1); a >= 0; a--)
 261                 {
 262                     fSum = fRow[a];
 263
 264                     for(b = a + 1; b < RowSize; b++)
 265                     {
 266                         fSum -= get(a, b) * fRow[b];
 267                     }
 268
 269                     const double fValueAA(get(a, a));
 270
 271                     if(!::basegfx::fTools::equalZero(fValueAA))
 272                     {
 273                         fRow[a] = fSum / get(a, a);
 274                     }
 275                 }
 276             }
 277
 278             bool isIdentity() const
 279             {
 280                 for(sal_uInt16 a(0); a < RowSize; a++)
 281                 {
 282                     for(sal_uInt16 b(0); b < RowSize; b++)
 283                     {
 284                         const double fDefault(implGetDefaultValue(a, b));
 285                         const double fValueAB(get(a, b));
 286
 287                         if(!::basegfx::fTools::equal(fDefault, fValueAB))
 288                         {
 289                             return false;
 290                         }
 291                     }
 292                 }
 293
 294                 return true;
 295             }
 296
 297             bool isInvertible() const
 298             {
 299                 ImplHomMatrixTemplate aWork(*this);
 300                 sal_uInt16 nIndex[RowSize];
 301                 sal_Int16 nParity;
 302
 303                 return aWork.ludcmp(nIndex, nParity);
 304             }
 305
 306             void doInvert(const ImplHomMatrixTemplate& rWork, const sal_uInt16 nIndex[])
 307             {
 308                 double fArray[RowSize];
 309
 310                 for(sal_uInt16 a(0); a < RowSize; a++)
 311                 {
 312                     // prepare line
 313                     sal_uInt16 b;
 314                     for( b = 0; b < RowSize; b++)
 315                     {
 316                         fArray[b] = implGetDefaultValue(a, b);
 317                     }
 318
 319                     // expand line
 320                     rWork.lubksb(nIndex, fArray);
 321
 322                     // copy line transposed to this matrix
 323                     for( b = 0; b < RowSize; b++)
 324                     {
 325                         set(b, a, fArray[b]);
 326                     }
 327                 }
 328             }
 329
 330             double doDeterminant() const
 331             {
 332                 ImplHomMatrixTemplate aWork(*this);
 333                 sal_uInt16 nIndex[RowSize];
 334                 sal_Int16 nParity;
 335                 double fRetval(0.0);
 336
 337                 if(aWork.ludcmp(nIndex, nParity))
 338                 {
 339                     fRetval = static_cast<double>(nParity);
 340                     for(sal_uInt16 a(0); a < RowSize; a++)
 341                     {
 342                         fRetval *= aWork.get(a, a);
 343                     }
 344                 }
 345
 346                 return fRetval;
 347             }
 348
 349             void doAddMatrix(const ImplHomMatrixTemplate& rMat)
 350             {
 351                 for(sal_uInt16 a(0); a < RowSize; a++)
 352                 {
 353                     for(sal_uInt16 b(0); b < RowSize; b++)
 354                     {
 355                         set(a, b, get(a, b) + rMat.get(a, b));
 356                     }
 357                 }
 358             }
 359
 360             void doSubMatrix(const ImplHomMatrixTemplate& rMat)
 361             {
 362                 for(sal_uInt16 a(0); a < RowSize; a++)
 363                 {
 364                     for(sal_uInt16 b(0); b < RowSize; b++)
 365                     {
 366                         set(a, b, get(a, b) - rMat.get(a, b));
 367                     }
 368                 }
 369             }
 370
 371             void doMulMatrix(const double& rfValue)
 372             {
 373                 for(sal_uInt16 a(0); a < RowSize; a++)
 374                 {
 375                     for(sal_uInt16 b(0); b < RowSize; b++)
 376                     {
 377                         set(a, b, get(a, b) * rfValue);
 378                     }
 379                 }
 380             }
 381
 382             void doMulMatrix(const ImplHomMatrixTemplate& rMat)
 383             {
 384                 // create a copy as source for the original values
 385                 const ImplHomMatrixTemplate aCopy(*this);
 386
 387                 // TODO: maybe optimize cases where last line is [0 0 1].
 388
 389                 double fValue(0.0);
 390
 391                 for(sal_uInt16 a(0); a < RowSize; ++a)
 392                 {
 393                     for(sal_uInt16 b(0); b < RowSize; ++b)
 394                     {
 395                         fValue = 0.0;
 396
 397                         for(sal_uInt16 c(0); c < RowSize; ++c)
 398                             fValue += aCopy.get(c, b) * rMat.get(a, c);
 399
 400                         set(a, b, fValue);
 401                     }
 402                 }
 403             }
 404
 405             bool isEqual(const ImplHomMatrixTemplate& rMat) const
 406             {
 407                 for(sal_uInt16 a(0); a < RowSize; a++)
 408                 {
 409                     for(sal_uInt16 b(0); b < RowSize; b++)
 410                     {
 411                         const double fValueA(get(a, b));
 412                         const double fValueB(rMat.get(a, b));
 413
 414                         if(!::basegfx::fTools::equal(fValueA, fValueB))
 415                         {
 416                             return false;
 417                         }
 418                     }
 419                 }
 420
 421                 return true;
 422             }
 423         };
 424
 425 } // namespace basegfx::internal
 426
 427 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */