00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef GNASH_SNAPPINGRANGE_H
00020 #define GNASH_SNAPPINGRANGE_H
00021
00022 #include "Range2d.h"
00023
00024 #include <vector>
00025 #include <iterator>
00026 #include <algorithm>
00027 #include <ostream>
00028 #include <boost/cstdint.hpp>
00029
00030 namespace gnash {
00031
00032 namespace geometry {
00033
00038
00068
00069
00070 namespace {
00071
00073 template<typename T> inline bool snaptest(
00074 const geometry::Range2d<T>& range1,
00075 const geometry::Range2d<T>& range2, const float snapFactor);
00076 }
00077
00078 template <typename T>
00079 class SnappingRanges2d
00080 {
00081 public:
00082 typedef geometry::Range2d<T> RangeType;
00083 typedef std::vector<RangeType> RangeList;
00084 typedef typename RangeList::size_type size_type;
00085
00086 template<typename U> friend std::ostream& operator<<(std::ostream& os,
00087 const SnappingRanges2d<U>& r);
00088
00089 SnappingRanges2d()
00090 :
00091 _snapFactor(1.3f),
00092 _singleMode(false),
00093 _rangesLimit(50),
00094 _combineCounter(0)
00095 {
00096 }
00097
00099 template <typename U>
00100 SnappingRanges2d(const SnappingRanges2d<U>& from)
00101 :
00102 _snapFactor(from.getSnapFactor()),
00103 _singleMode(from.getSingleMode()),
00104 _rangesLimit(from.getRangeCountLimit()),
00105 _combineCounter(0)
00106 {
00107 if (from.isWorld()) setWorld();
00108 else if (from.isNull()) setNull();
00109 else {
00110
00111
00112
00113
00114 for (size_type i = 0, e = from.size(); i != e; ++i) {
00115 const Range2d<U>& r = from.getRange(i);
00116 RangeType rc(r);
00117 add(rc);
00118 }
00119 }
00120 }
00121
00124 void setSnapFactor(const float factor) {
00125 assert(factor > 1.0f);
00126 _snapFactor = factor;
00127 }
00128
00129 float getSnapFactor() const {
00130 return _snapFactor;
00131 }
00132
00134 void setSingleMode(const bool mode) {
00135 _singleMode = mode;
00136 }
00137
00138 bool getSingleMode() const {
00139 return _singleMode;
00140 }
00141
00144 void setRangeCountLimit(const size_type limit) {
00145 _rangesLimit = limit;
00146 }
00147
00148 size_type getRangeCountLimit() const {
00149 return _rangesLimit;
00150 }
00151
00154 void inheritConfig(const SnappingRanges2d<T>& from) {
00155 _snapFactor = from._snapFactor;
00156 _singleMode = from._singleMode;
00157 }
00158
00160 struct ExpandToIfSnap
00161 {
00162 public:
00163 ExpandToIfSnap(const RangeType& rt, const float snapFactor)
00164 :
00165 _rt(rt),
00166 _snapFactor(snapFactor)
00167 {}
00168
00169 bool operator()(RangeType& r) {
00170 if (snaptest(r, _rt, _snapFactor)) {
00171 r.expandTo(_rt);
00172 return false;
00173 }
00174 return true;
00175 }
00176 private:
00177 const RangeType& _rt;
00178 const float _snapFactor;
00179 };
00180
00181 class Scale
00182 {
00183 public:
00184 Scale(const float scale) : _scale(scale) {}
00185 void operator()(RangeType& r) {
00186 r.scale(_scale);
00187 }
00188 private:
00189 const float _scale;
00190 };
00191
00192 class GrowBy
00193 {
00194 public:
00195 GrowBy(const float factor) : _factor(factor) {}
00196 void operator()(RangeType& r) {
00197 r.growBy(_factor);
00198 }
00199 private:
00200 const float _factor;
00201 };
00202
00203 class AddTo
00204 {
00205 public:
00206 AddTo(SnappingRanges2d<T>& us) : _this(us) {}
00207 void operator()(const RangeType& r) {
00208 _this.add(r);
00209 }
00210 private:
00211 SnappingRanges2d<T>& _this;
00212 };
00213
00214 class IntersectsRange
00215 {
00216 public:
00217 IntersectsRange(const RangeType& range) : _range(range) {}
00218 bool operator()(const RangeType& us) {
00219 return us.intersects(_range);
00220 }
00221 private:
00222 const RangeType& _range;
00223 };
00224
00225 class ContainsPoint
00226 {
00227 public:
00228 ContainsPoint(const T x, const T y) : _x(x), _y(y) {}
00229 bool operator()(const RangeType& us) {
00230 return us.contains(_x, _y);
00231 }
00232 private:
00233 const T _x, _y;
00234 };
00235
00236 class ContainsRange
00237 {
00238 public:
00239 ContainsRange(const RangeType& range) : _range(range) {}
00240 bool operator()(const RangeType& us) {
00241 return us.contains(_range);
00242 }
00243 private:
00244 const RangeType& _range;
00245 };
00246
00247
00249 void add(const RangeType& range) {
00250 if (range.isWorld()) {
00251 setWorld();
00252 return;
00253 }
00254
00255 if (range.isNull()) return;
00256
00257 if (_singleMode) {
00258 if (_ranges.empty()) _ranges.resize(1);
00259 _ranges[0].expandTo(range);
00260 return;
00261 }
00262
00263 ExpandToIfSnap exp(range, _snapFactor);
00264 if (visit(exp)) return;
00265
00266
00267 _ranges.push_back(range);
00268
00269 combineRangesLazy();
00270 }
00271
00273 void add(const SnappingRanges2d<T>& other) {
00274 const RangeList& rl = other._ranges;
00275 std::for_each(rl.begin(), rl.end(), AddTo(*this));
00276 }
00277
00279 void growBy(const T amount) {
00280
00281 if (isWorld() || isNull()) return;
00282
00283 std::for_each(_ranges.begin(), _ranges.end(), GrowBy(amount));
00284 combineRangesLazy();
00285 }
00286
00288 void scale(const float factor) {
00289
00290 if (isWorld() || isNull()) return;
00291
00292 std::for_each(_ranges.begin(), _ranges.end(), Scale(factor));
00293 combineRangesLazy();
00294 }
00295
00297 void setNull() {
00298 _ranges.clear();
00299 }
00300
00302 void setWorld() {
00303 if (isWorld()) return;
00304 _ranges.resize(1);
00305 _ranges[0].setWorld();
00306 }
00307
00309 bool isWorld() const {
00310 return ((size()==1) && (_ranges.front().isWorld()));
00311 }
00312
00314 bool isNull() const {
00315 return _ranges.empty();
00316 }
00317
00319 size_type size() const {
00320 finalize();
00321 return _ranges.size();
00322 }
00323
00325 const RangeType& getRange(size_type index) const {
00326 finalize();
00327 assert(index<size());
00328 return _ranges[index];
00329 }
00330
00333 RangeType getFullArea() const {
00334 RangeType range;
00335
00336 range.setNull();
00337
00338 int rcount = _ranges.size();
00339
00340 for (int rno=0; rno<rcount; rno++)
00341 range.expandTo(_ranges[rno]);
00342
00343 return range;
00344 }
00345
00346
00348
00352 bool intersects(const RangeType& r) const {
00353
00354 finalize();
00355 return std::find_if(_ranges.begin(), _ranges.end(), IntersectsRange(r))
00356 != _ranges.end();
00357 }
00358
00360 bool contains(T x, T y) const {
00361
00362 finalize();
00363 return std::find_if(_ranges.begin(), _ranges.end(), ContainsPoint(x, y))
00364 != _ranges.end();
00365 }
00366
00368
00372 bool contains(const RangeType& r) const {
00373
00374 finalize();
00375 return std::find_if(_ranges.begin(), _ranges.end(), ContainsRange(r))
00376 != _ranges.end();
00377 }
00378
00387 bool contains(const SnappingRanges2d<T>& o) const
00388 {
00389
00390 finalize();
00391
00392
00393
00394 if ( isNull() ) return false;
00395 if ( o.isNull() ) return false;
00396
00397
00398 if ( isWorld() ) return true;
00399
00400
00401
00402
00403
00405 for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++)
00406 {
00407 RangeType r = o.getRange(rno);
00408 if ( ! contains(r) )
00409 {
00410 return false;
00411 }
00412 }
00413
00414 return true;
00415
00416 }
00417
00418
00424 void intersect(const SnappingRanges2d<T>& o)
00425 {
00426 if (o.isNull()) {
00427 setNull();
00428 return;
00429 }
00430
00431 if (o.isWorld()) return;
00432
00433
00434
00435
00436
00437 std::vector<SnappingRanges2d<T> > list;
00438 list.reserve(o.size());
00439
00440
00441 for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++) {
00442
00443
00444 list.push_back(*this);
00445
00446
00447 list.back().intersect(o.getRange(rno));
00448
00449 }
00450
00451
00452 setNull();
00453 for (size_type lno=0, lcount=list.size(); lno<lcount; lno++) {
00454 add(list[lno]);
00455 }
00456
00457 }
00458
00459
00462 void intersect(const RangeType& r)
00463 {
00464
00465 finalize();
00466
00467 if (isWorld()) {
00468 setNull();
00469 add(r);
00470 return;
00471 }
00472
00473 if (isNull()) return;
00474
00475 if (r.isNull()) {
00476 setNull();
00477 return;
00478 }
00479
00480 if (r.isWorld()) return;
00481
00482
00483 for (int rno=_ranges.size()-1; rno>=0; rno--) {
00484
00485 RangeType newrange = Intersection(_ranges[rno], r);
00486
00487 if (newrange.isNull())
00488 _ranges.erase(_ranges.begin() + rno);
00489 else
00490 _ranges[rno] = newrange;
00491 }
00492 }
00493
00496 void combineRanges() const {
00497
00498
00499 if (_singleMode) return;
00500
00501 bool restart = true;
00502
00503 _combineCounter = 0;
00504
00505 while (restart) {
00506
00507 int rcount = _ranges.size();
00508
00509 restart=false;
00510
00511 for (int i=0; i<rcount; i++) {
00512
00513 for (int j=i+1; j<rcount; j++) {
00514
00515 if (snaptest(_ranges[i], _ranges[j], _snapFactor)) {
00516
00517 _ranges[i].expandTo(_ranges[j]);
00518
00519 _ranges.erase(_ranges.begin() + j);
00520
00521 restart=true;
00522 break;
00523
00524 }
00525 }
00526
00527 if (restart) break;
00528 }
00529 }
00530
00531
00532 if (_ranges.size() > _rangesLimit) {
00533
00534
00535
00536
00537
00538 RangeType single = getFullArea();
00539 _ranges.resize(1);
00540 _ranges[0] = single;
00541
00542 }
00543
00544 }
00545
00547
00556 template<class V> inline bool visit(V& visitor) const
00557 {
00558 typename RangeList::iterator it, e;
00559 for (it = _ranges.begin(), e = _ranges.end(); it != e; ++it) {
00560 if (!visitor(*it)) break;
00561 }
00562 return it != _ranges.end();
00563 }
00564
00566
00572 template<class V> inline void visitAll(V& visitor) const
00573 {
00574 for_each(_ranges.begin(), _ranges.end(), visitor);
00575 }
00576
00577 private:
00578
00579
00582 void combineRangesLazy() {
00583 const size_type max = 5;
00584 ++_combineCounter;
00585 if (_combineCounter > max) combineRanges();
00586 }
00587
00588 void finalize() const {
00589 if (_combineCounter > 0) combineRanges();
00590 }
00591
00593
00596 mutable RangeList _ranges;
00597
00599 float _snapFactor;
00600
00602 bool _singleMode;
00603
00605 size_type _rangesLimit;
00606
00608 mutable size_type _combineCounter;
00609
00610 };
00611
00612 template <class T>
00613 std::ostream&
00614 operator<< (std::ostream& os, const SnappingRanges2d<T>& r)
00615 {
00616 if ( r.isNull() ) return os << "NULL";
00617 if ( r.isWorld() ) return os << "WORLD";
00618
00619 typedef typename SnappingRanges2d<T>::RangeList R;
00620
00621 const R& ranges = r._ranges;
00622
00623 std::copy(ranges.begin(), ranges.end(),
00624 std::ostream_iterator<typename R::value_type>(os, ","));
00625
00626 return os;
00627 }
00628
00629 namespace {
00630
00631 template<typename T>
00632 inline bool snaptest(const geometry::Range2d<T>& range1,
00633 const geometry::Range2d<T>& range2, const float snapFactor)
00634 {
00635
00636
00637
00638
00639
00640 if (range1.intersects(range2)) return true;
00641
00642 geometry::Range2d<T> temp = range1;
00643 temp.expandTo(range2);
00644
00645 return (range1.getArea() + range2.getArea()) * snapFactor >
00646 temp.getArea();
00647
00648 }
00649
00650 }
00651 }
00652
00654 typedef geometry::SnappingRanges2d<boost::int32_t> InvalidatedRanges;
00655
00656 }
00657
00658 #endif