← Back to branch summary

~ubuntu-branches/ubuntu/precise/ipe/precise

« back to all changes in this revision

Viewing changes to src/ipelets/visibility-polygon/visibility-polygon.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Steve M. Robbins
  • Date: 2007-01-09 23:14:51 UTC
  • mfrom: (3.1.4 feisty)
  • Revision ID: james.westby@ubuntu.com-20070109231451-3nd095g7ishc108l
Tags: 6.0pre27-3
http://bugs.debian.org/378537
* debian/gsfonts-fontmap.xml: New.  Fontmap for fonts from gsfonts package.
* debian/rules: Use gsfonts-fontmap.xml instead of tetex-fontmap.xml.
* debian/control: Add texlive-latex-base dependency as alternative to
  tetex-bin (for pdflatex) and replace tetex-extra by gsfonts (for font
  files).  Patch courtesy of Norbert Preining.  Closes: #378537.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/ipelets/visibility-polygon/visibility-polygon.cpp
 
1
/*
 
2
 
 
3
    This file is part of the extensible drawing editor Ipe.
 
4
    Copyright (C) 1993-2005  Otfried Cheong
 
5
 
 
6
    Ipe is free software; you can redistribute it and/or modify it
 
7
    under the terms of the GNU General Public License as published by
 
8
    the Free Software Foundation; either version 2 of the License, or
 
9
    (at your option) any later version.
 
10
 
 
11
    As a special exception, you have permission to link Ipe with the
 
12
    CGAL library and distribute executables, as long as you follow the
 
13
    requirements of the Gnu General Public License in regard to all of
 
14
    the software in the executable aside from CGAL.
 
15
 
 
16
    Ipe is distributed in the hope that it will be useful, but WITHOUT
 
17
    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 
18
    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
 
19
    License for more details.
 
20
 
 
21
    You should have received a copy of the GNU General Public License
 
22
    along with Ipe; if not, you can find it at
 
23
    "http://www.gnu.org/copyleft/gpl.html", or write to the Free
 
24
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
25
 
 
26
*/
 
27
/*
 
28
  visibility-polygon.cpp: ipelet for finding the visibility polygon of
 
29
  a point inside a polygon
 
30
 
 
31
  Author: Chris Gray <cgray@win.tue.nl>
 
32
  License: Same as ipe (GPL with CGAL exception)
 
33
  Date: Thu Aug 11 14:51:03 CEST 2005
 
34
 
 
35
  Commentary: This ipelet computes the visibility polygon of a point
 
36
  inside a polygon.  The algorithm is adapted from the book _Art
 
37
  Gallery Theorems and Algorithms_ by Joseph O'Rourke (which was in
 
38
  turn based on the algorithm by Lee from 1985).
 
39
 
 
40
 */
 
41
 
 
42
#include "ipelet.h"
 
43
#include "ipepath.h"
 
44
#include "ipepage.h"
 
45
#include "ipevisitor.h"
 
46
#include "ipemark.h"
 
47
 
 
48
#include <list>
 
49
using std::list;
 
50
 
 
51
static const char *aboutText =
 
52
"Written by Chris Gray (www.win.tue.nl/~cgray/ipelets.html)";
 
53
 
 
54
// --------------------------------------------------------------------
 
55
 
 
56
int TurnType (IpeVector *a, IpeVector *b, IpeVector *c);
 
57
class VisibilityStack;
 
58
 
 
59
class VisibilityPolygonIpelet : public Ipelet {
 
60
public:
 
61
  virtual int IpelibVersion() const { return IPELIB_VERSION; }
 
62
  virtual const char *Label() const { return "Visibility Polygon"; }
 
63
  virtual const char *About() const { return aboutText; }
 
64
  virtual void Run(int, IpePage *page, IpeletHelper *helper);
 
65
private:
 
66
  virtual VisibilityStack *FindVisibilityPolygon(IpeVector **poly,
 
67
                                                 IpeVector *point,
 
68
                                                 int npoints);
 
69
  virtual IpeVector **RenumberPoly(IpeVector **poly, IpeVector *point,
 
70
                                   int npoints);
 
71
 
 
72
};
 
73
 
 
74
class VisibilityStack {
 
75
private:
 
76
  IpeVector **poly;
 
77
  double *polyAlphas;
 
78
  IpeVector *point;
 
79
  int npoints;
 
80
  int stackSize;
 
81
  list<IpeVector *> myStack;
 
82
  list<double> alphaStack;
 
83
  IpeVector *top() { return myStack.front(); }
 
84
  double alphaTop() { return alphaStack.front(); }
 
85
  void push (IpeVector *pt, double alpha)
 
86
  { myStack.push_front(pt); alphaStack.push_front(alpha); stackSize++; }
 
87
  void pop ()
 
88
  { IpeVector *pt = top(); myStack.pop_front(); delete pt; stackSize--;
 
89
  alphaStack.pop_front(); }
 
90
  int stopPop (int i, IpeVector *prevPoint, double prevAlpha,
 
91
               IpeVector &outPoint);
 
92
 
 
93
public:
 
94
  void SetPoly (IpeVector **p, int num) { poly = p; npoints = num; }
 
95
  void SetPoint (IpeVector *p) { point = p; }
 
96
  void Run ();
 
97
  IpeVector **ToPolygon ();
 
98
  VisibilityStack() { poly = NULL; point = NULL; stackSize = 0; npoints = 0; }
 
99
  int Length() { return stackSize; }
 
100
  ~VisibilityStack();
 
101
};
 
102
 
 
103
VisibilityStack::~VisibilityStack ()
 
104
{
 
105
  int i;
 
106
  for (i = 0; i < npoints; i++) {
 
107
    delete poly[i];
 
108
  }
 
109
  delete [] poly;
 
110
  delete [] polyAlphas;
 
111
}
 
112
 
 
113
// Returns 0, 1, or 2.
 
114
// 0 means "don't stop"
 
115
// 1 means "stop because case a happened"
 
116
// 2 means "stop because case b happened"
 
117
// If 1 or 2 is returned, outPoint is filled with the appropriate point.
 
118
int VisibilityStack::stopPop(int i, IpeVector *prevPoint,
 
119
                             double prevAlpha, IpeVector &outPoint)
 
120
{
 
121
  double currentAlpha = alphaTop();
 
122
  IpeVector *currentPoint = top();
 
123
 
 
124
  IpeSegment seg(*(point), *currentPoint);
 
125
  IpeSegment seg2(*(poly[i]), *(poly[(i + 1) % npoints]));
 
126
  IpeSegment seg3(*(poly[(i + 1) % npoints]), *(poly[(i + 2) % npoints]));
 
127
  IpeSegment seg4(*currentPoint, *prevPoint);
 
128
  if ((fabs(currentAlpha - prevAlpha) <= 1e-10
 
129
       || fabs(fabs(currentAlpha - prevAlpha) - 2 * M_PI) <= 1e-10)
 
130
      && (seg4.Intersects(seg3, outPoint)
 
131
          || seg4.Intersects(seg2, outPoint))) {
 
132
    IpeVector v1 = outPoint - *point;
 
133
    IpeVector v2 = *currentPoint - *point;
 
134
    if (v2.SqLen() < v1.SqLen()) {
 
135
      return 2;
 
136
    }
 
137
  }
 
138
  if (prevAlpha >= polyAlphas[(i + 1) % npoints]
 
139
      && polyAlphas[(i + 1) % npoints] > currentAlpha) {
 
140
    IpeSegment seg(*(point), *(poly[(i + 1) % npoints]));
 
141
    IpeSegment seg2(*prevPoint, *currentPoint);
 
142
    seg2.Intersects(seg.Line(), outPoint);
 
143
    return 1;
 
144
  }
 
145
 
 
146
  return 0;
 
147
}
 
148
 
 
149
void VisibilityStack::Run ()
 
150
{
 
151
  int i;
 
152
  IpeSegment *W = new IpeSegment();
 
153
  IpeVector y;
 
154
  int stopReason = 0;
 
155
 
 
156
  if (npoints == 0) return;
 
157
 
 
158
  polyAlphas = new double[npoints];
 
159
 
 
160
  // fill in the polyAlphas array
 
161
  polyAlphas[0] = 0.0;
 
162
  for (i = 1; i < npoints; i++) {
 
163
    IpeVector v1 = *(poly[i]) - *point;
 
164
    IpeVector v2 = *(poly[i - 1]) - *point;
 
165
    polyAlphas[i] = polyAlphas[i - 1]
 
166
      + TurnType(point, poly[i - 1], poly[i])
 
167
      * acos((v1.iX * v2.iX + v1.iY * v2.iY) / (v1.Len() * v2.Len()));
 
168
  }
 
169
 
 
170
  push(new IpeVector(*poly[0]), 0.0);
 
171
  enum state { PUSH, POP, WAIT } state = PUSH;
 
172
  for (i = 0; i < npoints;) {
 
173
    int iplus1modn = (i + 1) % npoints;
 
174
    switch (state) {
 
175
    case PUSH:
 
176
      if (polyAlphas[iplus1modn] < 2 * M_PI
 
177
          || (fabs(polyAlphas[iplus1modn] - 2 * M_PI) <= 1e-10)) {
 
178
        push(new IpeVector(*poly[iplus1modn]), polyAlphas[iplus1modn]);
 
179
        i++;
 
180
        iplus1modn = (i + 1) % npoints;
 
181
        if (i == npoints) goto out;
 
182
        if (polyAlphas[iplus1modn] >= polyAlphas[i] || i == npoints - 1) {
 
183
          // nothing
 
184
        } else {
 
185
          if (TurnType(poly[i - 1], poly[i], poly[iplus1modn]) >= 0) {
 
186
            state = POP;
 
187
          } else {
 
188
            // Set W to s_t \infty in the direction from x to s_t
 
189
            state = WAIT;
 
190
            W->iP = *(top());
 
191
            IpeVector v = W->iP - *point;
 
192
            v *= 1e42;
 
193
            W->iQ = W->iP + v;
 
194
          }
 
195
        }
 
196
      } else {
 
197
        // push the intersection of the ray x v_0 with v_i v_{i + 1}
 
198
        // onto the stack and then call wait with W = v_0 s_t
 
199
        state = WAIT;
 
200
        // calculate the intersection between the horizontal line from
 
201
        // v_0 and v_i v_{i + 1}
 
202
        double pointY = point->iY;
 
203
        double edgeY1 = poly[i]->iY;
 
204
        double edgeY2 = poly[iplus1modn]->iY;
 
205
        if ((pointY < edgeY1 && pointY > edgeY2)
 
206
            || (pointY > edgeY1 && pointY < edgeY2)) {
 
207
          double a = (pointY - edgeY2) / (edgeY1 - edgeY2);
 
208
          double edgeX1 = poly[i]->iX;
 
209
          double edgeX2 = poly[iplus1modn]->iX;
 
210
          double xprime = (a * edgeX1) + ((1 - a) * edgeX2);
 
211
          // push the intersection with alpha 2\pi
 
212
          push(new IpeVector(xprime, pointY), 2 * M_PI);
 
213
          // set W to be v_0 s_t
 
214
          W->iQ = *(poly[0]);
 
215
          W->iP = *(top());
 
216
        } else {
 
217
          // something bad happened.
 
218
          assert(0);
 
219
        }
 
220
      }
 
221
      break;
 
222
    case POP:
 
223
      // pop until one of two things happens:
 
224
      // a) prevAlpha >= polyAlphas[i + 1] > alphaTop
 
225
      // b) prevAlpha = alphaTop >= polyAlphas[i + 1] and the
 
226
      // intersection of the ray from point through prevAlpha to the
 
227
      // next segment happens between prevAlpha and alphaTop
 
228
      double prevAlpha;
 
229
      IpeVector *prevPoint;
 
230
      do {
 
231
        prevAlpha = alphaTop();
 
232
        prevPoint = top();
 
233
        pop();
 
234
      } while (!(stopReason = stopPop(i, prevPoint, prevAlpha, y)));
 
235
 
 
236
      // what you do depends on whether a or b happened
 
237
      if (stopReason == 1) {
 
238
        IpeVector v = y - *point;
 
239
        push(new IpeVector(y), v.Angle().Normalize(0.0));
 
240
        i++;
 
241
        if (i == npoints) {
 
242
          goto out;
 
243
        }
 
244
        if (polyAlphas[i] > polyAlphas[(i + 1) % npoints]) {
 
245
          state = POP;
 
246
        } else {
 
247
          if (TurnType(poly[i - 1], poly[i], poly[(i + 1) % npoints]) < 0) {
 
248
            i--;
 
249
            state = PUSH;
 
250
          } else {
 
251
            //i--;
 
252
            state = WAIT;
 
253
            W->iQ = *(poly[i]);
 
254
            W->iP = *(top());
 
255
          }
 
256
        }
 
257
      } else {
 
258
        state = WAIT;
 
259
        W->iP = *(top());
 
260
        W->iQ = y;
 
261
      }
 
262
 
 
263
      break;
 
264
    case WAIT:
 
265
      // i is incremented until v_i v_{i + 1} intersects W at point y
 
266
      // from the correct direction.  When that occurs, y is pushed on
 
267
      // the stack, and either push or pop is called depending on
 
268
      // whether polyAlphas[i + 1] >= polyAlphas[i] or vice versa,
 
269
      // respectively.
 
270
 
 
271
      IpeVector pt;
 
272
      IpeSegment currentSeg;
 
273
      do {
 
274
        i++;
 
275
        currentSeg.iP = *(poly[i]);
 
276
        currentSeg.iQ = *(poly[(i + 1) % npoints]);
 
277
      } while (!(currentSeg.Intersects(*W, pt) &&
 
278
                 TurnType(&currentSeg.iP, &(W->iQ), &currentSeg.iQ) > 0));
 
279
 
 
280
      // push pt on the stack, after computing alpha
 
281
 
 
282
      IpeVector diff = pt - *point;
 
283
      push (new IpeVector(pt), diff.Angle().Normalize(0.0));
 
284
 
 
285
      // now figure out what to set the state to.
 
286
      if (polyAlphas[i] < polyAlphas[(i + 1) % npoints]) {
 
287
        state = PUSH;
 
288
      } else {
 
289
        state = POP;
 
290
      }
 
291
 
 
292
      break;
 
293
    }
 
294
  }
 
295
 out:;
 
296
  delete W;
 
297
}
 
298
 
 
299
IpeVector **VisibilityStack::ToPolygon()
 
300
{
 
301
  IpeVector **output = new IpeVector*[stackSize];
 
302
  int i = 0;
 
303
 
 
304
  while (stackSize) {
 
305
    output[i] = new IpeVector(*top());
 
306
    pop();
 
307
    i++;
 
308
  }
 
309
  return output;
 
310
}
 
311
 
 
312
IpeVector **VisibilityPolygonIpelet::RenumberPoly(IpeVector **poly,
 
313
                                                  IpeVector *point,
 
314
                                                  int npoints)
 
315
{
 
316
  int i;
 
317
  int nearestPointBetween = -1;
 
318
  int reverse;
 
319
  double nearest = 1e42; /* FIXME: bounding circle */
 
320
  IpeVector *nearestPoint = new IpeVector();
 
321
  IpeVector **output = new IpeVector*[npoints + 2];
 
322
 
 
323
  IpeVector farPoint(1e42, point->iY); /* FIXME: bounding circle */
 
324
  IpeSegment horizSegment(*point, farPoint);
 
325
 
 
326
  nearestPoint->iY = point->iY;
 
327
 
 
328
  for (i = 0; i < npoints; i++) {
 
329
    int j = (i + 1) % npoints;
 
330
    IpeVector pt;
 
331
    IpeSegment seg(*(poly[i]), *(poly[j]));
 
332
 
 
333
    if (horizSegment.Intersects(seg, pt)) {
 
334
      if (pt.iX > point->iX && pt.iX < nearest) {
 
335
        nearest = pt.iX;
 
336
        nearestPointBetween = j;
 
337
        nearestPoint->iX = pt.iX;
 
338
      }
 
339
    }
 
340
  }
 
341
 
 
342
  output[0] = nearestPoint;
 
343
  if (poly[(nearestPointBetween - 1 + npoints) % npoints]->iY
 
344
      < poly[nearestPointBetween]->iY) {
 
345
    reverse = 1;
 
346
  } else {
 
347
    reverse = -1;
 
348
    nearestPointBetween = (nearestPointBetween - 1 + npoints) % npoints;
 
349
  }
 
350
  for (i = 0; i < npoints; i++) {
 
351
    output[i + 1] = new IpeVector(*(poly[(reverse * i + nearestPointBetween
 
352
                                          + npoints) % npoints]));
 
353
  }
 
354
  output[npoints + 1] = new IpeVector(*nearestPoint);
 
355
  return output;
 
356
 
 
357
}
 
358
 
 
359
int TurnType (IpeVector *a, IpeVector *b, IpeVector *c)
 
360
{
 
361
  double area2 = (b->iX - a->iX) *
 
362
    (c->iY - a->iY) - (c->iX - a->iX) * (b->iY - a->iY);
 
363
 
 
364
  if (area2 > 0) {
 
365
    return 1;
 
366
  } else if (area2 < 0) {
 
367
    return -1;
 
368
  } else {
 
369
    return 0;
 
370
  }
 
371
}
 
372
 
 
373
VisibilityStack *VisibilityPolygonIpelet::FindVisibilityPolygon
 
374
(IpeVector **poly, IpeVector *point, int npoints)
 
375
{
 
376
  int i;
 
377
  IpeVector **renumbered = RenumberPoly (poly, point, npoints);
 
378
  npoints++;
 
379
  VisibilityStack *st = new VisibilityStack;
 
380
 
 
381
  for (i = 0; i < npoints - 1; i++) {
 
382
    delete poly[i];
 
383
  }
 
384
  delete [] poly;
 
385
 
 
386
  st->SetPoly (renumbered, npoints + 1);
 
387
  st->SetPoint (point);
 
388
  st->Run ();
 
389
 
 
390
  return st;
 
391
}
 
392
 
 
393
void VisibilityPolygonIpelet::Run(int, IpePage *page, IpeletHelper *helper)
 
394
{
 
395
  IpePage::iterator it;
 
396
  int length = 0;
 
397
  int have_point = 0;
 
398
  int i, j, k;
 
399
 
 
400
  for (it = page->begin(); it != page->end(); it++) {
 
401
    if (it->Select() && it->Object() && it->Object()->AsMark()) {
 
402
      have_point = 1;
 
403
    } else if (it->Select() && it->Object() && it->Object()->AsPath()) {
 
404
      IpePath *path = it->Object()->AsPath();
 
405
      for (j = 0; j < path->NumSubPaths(); j++) {
 
406
        if (path->SubPath(j)->Type() == IpeSubPath::ESegments) {
 
407
          const IpeSubPath *sp = it->Object()->AsPath()->SubPath(j);
 
408
          if (sp->AsSegs()) {
 
409
            length = sp->AsSegs()->NumSegments() + 1;
 
410
          }
 
411
        }
 
412
      }
 
413
    }
 
414
  }
 
415
  if (length < 2 || have_point == 0) {
 
416
    helper->Message("Too little selected");
 
417
    return;
 
418
  }
 
419
  IpeVector **points = new IpeVector*[length];
 
420
  IpeVector *point = NULL;
 
421
  i = 0;
 
422
  for (it = page->begin(); it != page->end(); it++) {
 
423
    if (it->Select() && it->Object()) {
 
424
      IpeMatrix m = it->Object()->Matrix();
 
425
      if (it->Object()->AsMark()) {
 
426
        point = new IpeVector(m * it->Object()->AsMark()->Position());
 
427
      } else if (it->Object()->AsPath()) {
 
428
        IpePath *path = it->Object()->AsPath();
 
429
        for (j = 0; j < path->NumSubPaths(); j++) {
 
430
          if (path->SubPath(j)->Type() == IpeSubPath::ESegments) {
 
431
            const IpeSegmentSubPath *sp = path->SubPath(j)->AsSegs();
 
432
            for (k = 0; k < sp->NumSegments(); k++) {
 
433
              points[i] = new IpeVector(m * sp->Segment(k).CP(0));
 
434
              i++;
 
435
            }
 
436
            points[i] = new IpeVector(m * sp->Segment(k - 1).CP(1));
 
437
            i++;
 
438
          }
 
439
        }
 
440
      }
 
441
    }
 
442
  }
 
443
 
 
444
  VisibilityStack *output = FindVisibilityPolygon (points, point, length);
 
445
  delete point;
 
446
 
 
447
  length = output->Length();
 
448
 
 
449
  IpePath *path = new IpePath(helper->Attributes());
 
450
  IpeSegmentSubPath *sp = new IpeSegmentSubPath;
 
451
 
 
452
  IpeVector **newpoints = output->ToPolygon();
 
453
 
 
454
  for (i = 1; i < length; i++) {
 
455
    sp->AppendSegment (*(newpoints[i - 1]), *(newpoints[i]));
 
456
  }
 
457
  sp->SetClosed(true);
 
458
  path->AddSubPath(sp);
 
459
  page->push_back(IpePgObject(IpePgObject::EPrimary, helper->CurrentLayer(),
 
460
                              path));
 
461
 
 
462
  for (i = 0; i < length; i++) {
 
463
    delete newpoints[i];
 
464
  }
 
465
  delete [] newpoints;
 
466
 
 
467
  delete output;
 
468
}
 
469
 
 
470
IPELET_DECLARE Ipelet *NewIpelet()
 
471
{
 
472
  return new VisibilityPolygonIpelet;
 
473
}