← Back to branch summary

~ubuntu-branches/ubuntu/maverick/freecad/maverick

« back to all changes in this revision

Viewing changes to src/Base/Tools2D.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Teemu Ikonen
  • Date: 2009-07-16 18:37:41 UTC
  • Revision ID: james.westby@ubuntu.com-20090716183741-oww9kcxqrk991i1n
Tags: upstream-0.8.2237
Import upstream version 0.8.2237

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/Base/Tools2D.cpp
 
1
/***************************************************************************
 
2
 *   Copyright (c) 2005 Imetric 3D GmbH                                    *
 
3
 *                                                                         *
 
4
 *   This file is part of the FreeCAD CAx development system.              *
 
5
 *                                                                         *
 
6
 *   This library is free software; you can redistribute it and/or         *
 
7
 *   modify it under the terms of the GNU Library General Public           *
 
8
 *   License as published by the Free Software Foundation; either          *
 
9
 *   version 2 of the License, or (at your option) any later version.      *
 
10
 *                                                                         *
 
11
 *   This library  is distributed in the hope that it will be useful,      *
 
12
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 
13
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 
14
 *   GNU Library General Public License for more details.                  *
 
15
 *                                                                         *
 
16
 *   You should have received a copy of the GNU Library General Public     *
 
17
 *   License along with this library; see the file COPYING.LIB. If not,    *
 
18
 *   write to the Free Software Foundation, Inc., 59 Temple Place,         *
 
19
 *   Suite 330, Boston, MA  02111-1307, USA                                *
 
20
 *                                                                         *
 
21
 ***************************************************************************/
 
22
 
 
23
 
 
24
#include "PreCompiled.h"
 
25
 
 
26
#ifndef _PreComp_
 
27
# include <cstdlib>
 
28
# include <set>
 
29
#endif
 
30
 
 
31
#include "Tools2D.h"
 
32
#include "Vector3D.h"
 
33
 
 
34
using namespace Base;
 
35
 
 
36
float Vector2D::GetAngle (const Vector2D &rclVect) const
 
37
{
 
38
  float fDivid, fNum;
 
39
  
 
40
  fDivid = Length() * rclVect.Length();
 
41
 
 
42
  if ((fDivid < -1e-10f) || (fDivid > 1e-10f))
 
43
  {
 
44
    fNum = (*this * rclVect) / fDivid;
 
45
    if (fNum < -1)
 
46
      return F_PI;
 
47
    else
 
48
      if (fNum > 1)
 
49
        return 0.0F;
 
50
      else
 
51
        return float(acos(fNum));
 
52
  }
 
53
  else
 
54
    return -FLOAT_MAX; // division by zero
 
55
}
 
56
 
 
57
void Vector2D::ProjToLine (const Vector2D &rclPt, const Vector2D &rclLine)
 
58
{
 
59
  float l  = rclLine.Length();
 
60
  float t1 = (rclPt * rclLine) / l;
 
61
  Vector2D clNormal = rclLine;
 
62
  clNormal.Normalize();
 
63
  clNormal.Scale(t1);  
 
64
  *this = clNormal;
 
65
}
 
66
 
 
67
/********************************************************/
 
68
/** BOUNDBOX2D ********************************************/
 
69
 
 
70
bool BoundBox2D::operator|| (const Line2D &rclLine) const
 
71
{
 
72
  Line2D clThisLine;
 
73
  Vector2D clVct;
 
74
 
 
75
  // first line 
 
76
  clThisLine.clV1.fX = fMinX;
 
77
  clThisLine.clV1.fY = fMinY;
 
78
  clThisLine.clV2.fX = fMaxX;
 
79
  clThisLine.clV2.fY = fMinY;
 
80
  if (clThisLine.IntersectAndContain (rclLine, clVct)) 
 
81
    return true;
 
82
 
 
83
  // second line
 
84
  clThisLine.clV1 = clThisLine.clV2;
 
85
  clThisLine.clV2.fX = fMaxX;
 
86
  clThisLine.clV2.fY = fMaxY;
 
87
  if (clThisLine.IntersectAndContain (rclLine, clVct)) 
 
88
    return true;
 
89
 
 
90
  // third line
 
91
  clThisLine.clV1 = clThisLine.clV2;
 
92
  clThisLine.clV2.fX = fMinX;
 
93
  clThisLine.clV2.fY = fMaxY;
 
94
  if (clThisLine.IntersectAndContain (rclLine, clVct)) 
 
95
    return true;
 
96
 
 
97
  // fourth line
 
98
  clThisLine.clV1 = clThisLine.clV2;
 
99
  clThisLine.clV2.fX = fMinX;
 
100
  clThisLine.clV2.fY = fMinY;
 
101
  if (clThisLine.IntersectAndContain (rclLine, clVct)) 
 
102
    return true;
 
103
 
 
104
  return false;
 
105
}
 
106
 
 
107
bool BoundBox2D::operator|| (const BoundBox2D &rclBB) const
 
108
{
 
109
//// compare bb2-points to this
 
110
//if (Contains (Vector2D (rclBB.fMinX, rclBB.fMinY))) return TRUE;
 
111
//if (Contains (Vector2D (rclBB.fMaxX, rclBB.fMinY))) return TRUE;
 
112
//if (Contains (Vector2D (rclBB.fMaxX, rclBB.fMaxY))) return TRUE;
 
113
//if (Contains (Vector2D (rclBB.fMinX, rclBB.fMaxY))) return TRUE;
 
114
//
 
115
//// compare this-points to bb2
 
116
//if (rclBB.Contains (Vector2D (fMinX, fMinY))) return TRUE;
 
117
//if (rclBB.Contains (Vector2D (fMaxX, fMinY))) return TRUE;
 
118
//if (rclBB.Contains (Vector2D (fMaxX, fMaxY))) return TRUE;
 
119
//if (rclBB.Contains (Vector2D (fMinX, fMaxY))) return TRUE;
 
120
 
 
121
  if (fMinX       < rclBB.fMaxX  &&
 
122
      rclBB.fMinX < fMaxX        &&
 
123
      fMinY       < rclBB.fMaxY  &&
 
124
      rclBB.fMinY < fMaxY         )
 
125
      return true;
 
126
  else // no intersection
 
127
      return false;
 
128
}
 
129
 
 
130
bool BoundBox2D::operator|| (const Polygon2D &rclPoly) const
 
131
{
 
132
  unsigned long i;
 
133
  Line2D clLine;
 
134
  
 
135
  // points contained in boundbox
 
136
  for (i = 0; i < rclPoly.GetCtVectors(); i++)
 
137
    if (Contains (rclPoly[i]))
 
138
      return true;    /***** RETURN INTERSECTION *********/
 
139
 
 
140
  // points contained in polygon
 
141
  if (rclPoly.Contains (Vector2D (fMinX, fMinY)) ||
 
142
      rclPoly.Contains (Vector2D (fMaxX, fMinY)) ||
 
143
      rclPoly.Contains (Vector2D (fMaxX, fMaxY)) ||
 
144
      rclPoly.Contains (Vector2D (fMinX, fMaxY)))
 
145
    return true;    /***** RETURN INTERSECTION *********/
 
146
      
 
147
  // test intersections of bound-lines
 
148
  if (rclPoly.GetCtVectors() < 3) return false;
 
149
  for (i = 0; i < rclPoly.GetCtVectors(); i++)
 
150
  {
 
151
    if (i == rclPoly.GetCtVectors() - 1)
 
152
    {
 
153
      clLine.clV1 = rclPoly[i];
 
154
      clLine.clV2 = rclPoly[0];
 
155
    }
 
156
    else
 
157
    {
 
158
      clLine.clV1 = rclPoly[i];
 
159
      clLine.clV2 = rclPoly[i + 1];
 
160
    }
 
161
    if (*this || clLine) 
 
162
      return true;    /***** RETURN INTERSECTION *********/
 
163
  }
 
164
  // no intersection
 
165
  return false;
 
166
}
 
167
 
 
168
bool BoundBox2D::Contains (const Vector2D &rclV) const
 
169
{
 
170
  return
 
171
    (rclV.fX >= fMinX) && (rclV.fX <= fMaxX) &&
 
172
    (rclV.fY >= fMinY) && (rclV.fY <= fMaxY);
 
173
}
 
174
 
 
175
/********************************************************/
 
176
/** LINE2D **********************************************/
 
177
 
 
178
BoundBox2D Line2D::CalcBoundBox (void) const
 
179
{
 
180
  BoundBox2D clBB;
 
181
  clBB.fMinX = std::min<float> (clV1.fX, clV2.fX);
 
182
  clBB.fMinY = std::min<float> (clV1.fY, clV2.fY);
 
183
  clBB.fMaxX = std::max<float> (clV1.fX, clV2.fX);
 
184
  clBB.fMaxY = std::max<float> (clV1.fY, clV2.fY);
 
185
  return clBB;
 
186
}
 
187
 
 
188
bool Line2D::Intersect (const Line2D& rclLine, Vector2D &rclV) const
 
189
{
 
190
  float m1, m2, b1, b2;
 
191
  
 
192
  // calc coefficients
 
193
  if (fabs (clV2.fX - clV1.fX) > 1e-10)
 
194
    m1 = (clV2.fY - clV1.fY) / (clV2.fX - clV1.fX);
 
195
  else
 
196
    m1 = FLOAT_MAX;
 
197
  if (fabs (rclLine.clV2.fX - rclLine.clV1.fX) > 1e-10)
 
198
    m2 = (rclLine.clV2.fY - rclLine.clV1.fY) / (rclLine.clV2.fX - rclLine.clV1.fX);
 
199
  else
 
200
    m2 = FLOAT_MAX;
 
201
  if (m1 == m2)     /****** RETURN ERR (parallel lines) *************/
 
202
    return false;
 
203
  
 
204
  b1 = clV1.fY - m1 * clV1.fX;
 
205
  b2 = rclLine.clV1.fY - m2 * rclLine.clV1.fX;
 
206
 
 
207
  // calc intersection
 
208
  if (m1 == FLOAT_MAX)
 
209
  {
 
210
    rclV.fX = clV1.fX;
 
211
    rclV.fY = m2 * rclV.fX + b2;
 
212
  }
 
213
  else
 
214
  if (m2 == FLOAT_MAX)
 
215
  {
 
216
    rclV.fX = rclLine.clV1.fX;
 
217
    rclV.fY = m1 * rclV.fX + b1;
 
218
  }
 
219
  else
 
220
  {
 
221
    rclV.fX = (b2 - b1) / (m1 - m2);
 
222
    rclV.fY = m1 * rclV.fX + b1;  
 
223
  }
 
224
  
 
225
  return true;    /*** RETURN TRUE (intersection) **********/
 
226
}
 
227
 
 
228
Vector2D Line2D::FromPos (float fDistance) const
 
229
{
 
230
  Vector2D clDir(clV2 - clV1);
 
231
  clDir.Normalize();
 
232
  return Vector2D(clV1.fX + (clDir.fX * fDistance), clV1.fY + (clDir.fY * fDistance));
 
233
}
 
234
 
 
235
bool Line2D::IntersectAndContain (const Line2D& rclLine, Vector2D &rclV) const
 
236
{
 
237
  bool rc = Intersect (rclLine, rclV);
 
238
  if (rc)
 
239
    rc = Contains (rclV) && rclLine.Contains (rclV);
 
240
  return rc;
 
241
}
 
242
 
 
243
/********************************************************/
 
244
/** POLYGON2D ********************************************/
 
245
 
 
246
BoundBox2D Polygon2D::CalcBoundBox (void) const
 
247
{
 
248
  unsigned long i;
 
249
  BoundBox2D clBB;
 
250
  for (i = 0; i < _aclVct.size(); i++)
 
251
  {
 
252
    clBB.fMinX = std::min<float> (clBB.fMinX, _aclVct[i].fX);
 
253
    clBB.fMinY = std::min<float> (clBB.fMinY, _aclVct[i].fY);
 
254
    clBB.fMaxX = std::max<float> (clBB.fMaxX, _aclVct[i].fX);
 
255
    clBB.fMaxY = std::max<float> (clBB.fMaxY, _aclVct[i].fY);
 
256
  }
 
257
  return clBB;  
 
258
}
 
259
 
 
260
static short _CalcTorsion (float *pfLine, float fX, float fY)
 
261
{
 
262
  short sQuad[2], i;
 
263
  float fResX;
 
264
 
 
265
  // Klassifizierung der beiden Polygonpunkte in Quadranten
 
266
  for (i = 0; i < 2; i++)
 
267
  {
 
268
    if (pfLine[i * 2] <= fX)
 
269
      sQuad[i] = (pfLine[i * 2 + 1] > fY) ? 0 : 3;
 
270
    else
 
271
      sQuad[i] = (pfLine[i * 2 + 1] > fY) ? 1 : 2;
 
272
  }
 
273
 
 
274
  // Abbruch bei Linienpunkten innerhalb eines Quadranten
 
275
  // Abbruch bei nichtschneidenden Linienpunkten
 
276
  if (abs (sQuad[0] - sQuad[1]) <= 1) return 0;
 
277
 
 
278
  // Beide Punkte links von ulX
 
279
  if (abs (sQuad[0] - sQuad[1]) == 3)
 
280
    return (sQuad[0] == 0) ? 1 : -1;
 
281
 
 
282
  // Restfaelle : Quadrantendifferenz von 2
 
283
  // mathematischer Test auf Schnitt
 
284
  fResX = pfLine[0] + (fY - pfLine[1]) /
 
285
                ((pfLine[3] - pfLine[1]) / (pfLine[2] - pfLine[0]));
 
286
  if (fResX < fX)
 
287
 
 
288
    // oben/unten oder unten/oben
 
289
    return (sQuad[0] <= 1) ? 1 : -1;
 
290
 
 
291
  // Verbleibende Faelle ?
 
292
  return 0;
 
293
}
 
294
 
 
295
bool Polygon2D::Contains (const Vector2D &rclV) const
 
296
{
 
297
  // Ermittelt mit dem Verfahren der Windungszahl, ob ein Punkt innerhalb 
 
298
  // eines Polygonzugs enthalten ist.
 
299
  // Summe aller Windungszahlen gibt an, ob ja oder nein.
 
300
  float pfTmp[4];
 
301
  unsigned long i;
 
302
  short sTorsion = 0;
 
303
 
 
304
  // Fehlercheck
 
305
  if (GetCtVectors() < 3)  return false;
 
306
 
 
307
  // fuer alle Polygon-Linien
 
308
  for (i = 0; i < GetCtVectors(); i++)
 
309
  {
 
310
    // Linienstruktur belegen
 
311
    if (i == GetCtVectors() - 1)
 
312
    {
 
313
      // Polygon automatisch schliessen
 
314
      pfTmp[0] = _aclVct[i].fX;
 
315
      pfTmp[1] = _aclVct[i].fY;
 
316
      pfTmp[2] = _aclVct[0].fX;
 
317
      pfTmp[3] = _aclVct[0].fY;
 
318
    }
 
319
    else
 
320
    {
 
321
      // uebernehmen Punkt i und i+1
 
322
      pfTmp[0] = _aclVct[i].fX;
 
323
      pfTmp[1] = _aclVct[i].fY;
 
324
      pfTmp[2] = _aclVct[i + 1].fX;
 
325
      pfTmp[3] = _aclVct[i + 1].fY;
 
326
    }
 
327
 
 
328
    // Schnitt-Test durchfuehren und Windungszaehler berechnen
 
329
    sTorsion += _CalcTorsion (pfTmp, rclV.fX, rclV.fY);
 
330
  }
 
331
 
 
332
  // Windungszaehler auswerten
 
333
  return sTorsion != 0;
 
334
}
 
335
 
 
336
void Polygon2D::Intersect (const Polygon2D &rclPolygon, std::list<Polygon2D> &rclResultPolygonList) const
 
337
{
 
338
  // trimmen des uebergebenen Polygons mit dem aktuellen, Ergebnis ist eine Liste von Polygonen (Untermenge des uebergebenen Polygons)
 
339
  // das eigene (Trim-) Polygon ist geschlossen
 
340
  //
 
341
  if ((rclPolygon.GetCtVectors() < 2) || (GetCtVectors() < 2))
 
342
    return;
 
343
 
 
344
  // position of first points (in or out of polygon)
 
345
  bool bInner = Contains(rclPolygon[0]);
 
346
 
 
347
  Polygon2D clResultPolygon;
 
348
  if (bInner == true)  // add first point if inner trim-polygon
 
349
    clResultPolygon.Add(rclPolygon[0]);
 
350
 
 
351
  // for each polygon segment
 
352
  size_t ulPolyCt = rclPolygon.GetCtVectors();
 
353
  size_t ulTrimCt = GetCtVectors();
 
354
  for (size_t ulVec = 0; ulVec < (ulPolyCt-1); ulVec++)
 
355
  {
 
356
    Vector2D clPt0 = rclPolygon[ulVec];
 
357
    Vector2D clPt1 = rclPolygon[ulVec+1];
 
358
    Line2D clLine(clPt0, clPt1);
 
359
 
 
360
    // try to intersect with each line of the trim-polygon
 
361
    std::set<float> afIntersections;  // set of intersections (sorted by line parameter)
 
362
    Vector2D clTrimPt2;  // second line point
 
363
    for (size_t i = 0; i < ulTrimCt; i++)
 
364
    {
 
365
      clTrimPt2 = At((i + 1) % ulTrimCt);
 
366
      Line2D clToTrimLine(At(i), clTrimPt2);
 
367
   
 
368
      Vector2D clV;
 
369
      if (clLine.IntersectAndContain(clToTrimLine, clV) == true)
 
370
      {
 
371
        // save line parameter of intersection point
 
372
        float fDist = (clV - clPt0).Length();
 
373
        afIntersections.insert(fDist);
 
374
      }
 
375
    }
 
376
 
 
377
    if (afIntersections.size() > 0)  // intersections founded
 
378
    {
 
379
      for (std::set<float>::iterator pF = afIntersections.begin(); pF != afIntersections.end(); pF++)
 
380
      {
 
381
        // intersection point
 
382
        Vector2D clPtIS = clLine.FromPos(*pF);
 
383
        if (bInner == true)
 
384
        {
 
385
          clResultPolygon.Add(clPtIS);
 
386
          rclResultPolygonList.push_back(clResultPolygon);
 
387
          clResultPolygon.DeleteAll();
 
388
          bInner = false;
 
389
        }
 
390
        else
 
391
        {
 
392
          clResultPolygon.Add(clPtIS);
 
393
          bInner = true;
 
394
        }
 
395
      }        
 
396
 
 
397
      if (bInner == true) // add line end point if inside
 
398
        clResultPolygon.Add(clPt1);
 
399
    }
 
400
    else
 
401
    {  // no intersections, add line (means second point of it) if inside trim-polygon
 
402
      if (bInner == true)
 
403
        clResultPolygon.Add(clPt1);
 
404
    }
 
405
  }  
 
406
 
 
407
  // add last segment
 
408
  if (clResultPolygon.GetCtVectors() > 0)
 
409
    rclResultPolygonList.push_back(clResultPolygon);
 
410
}
 
411