home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga 12 / MA_Cover_12.iso / source / xpdf-0.80 / xpdf / poly.h < prev    next >
Encoding:
C/C++ Source or Header  |  1999-05-20  |  6.1 KB  |  276 lines
  1. //========================================================================
  2. //
  3. // poly.h
  4. //
  5. // Copyright 1999 Emmanuel Lesueur
  6. //
  7. // A basic polygon manipulation package. This is experimental.
  8. // There are probably much better algorythms...
  9. // There is plenty of room for optimizations.
  10. //
  11. //========================================================================
  12.  
  13. #ifndef POLY_H
  14.  
  15. #ifdef __GNUC__
  16. #pragma interface
  17. #endif
  18.  
  19. static const double epsilon=1e-6;
  20.  
  21.  
  22. #ifdef __SASC
  23. inline void* operator new (size_t,void* p) { return p; }
  24. #   ifndef throw
  25. #       include <stdio.h>
  26. #       define throw(x) {printf("Exception: %s\n",(x)); exit(EXIT_FAILURE);}
  27. #       define nothrow
  28. #       define rethrow
  29. #       define try
  30. #       define catch(x) if(0)
  31. #   endif
  32. #else
  33. #   define nothrow  throw()
  34. #   define rethrow  throw
  35. static inline void* operator new (size_t,void* p) { return p; }
  36. #endif
  37.  
  38. #if MWDEBUG
  39. #   include "sc:extras/memlib/memwatch.h"
  40.     extern char* memdbg_file;
  41.     extern int memdbg_line;
  42. #   define new    (memdbg_file=__FILE__,memdbg_line=__LINE__),new
  43. #   define delete (memdbg_file=__FILE__,memdbg_line=__LINE__),delete
  44. #endif
  45.  
  46. #include <math.h>
  47. #if defined(__SASC) && !defined(__PPC__)
  48. #   include <m68881.h>
  49. #endif
  50.  
  51. template<class T> inline int compare(T x,T y) {
  52.     return x<y?-1:(x==y?0:1);
  53. }
  54.  
  55. inline int compare(double x,double y) {
  56.     return fabs(x-y)<=epsilon*(fabs(x)+fabs(y))?0:(x<y?-1:1);
  57. }
  58. inline int compare(float x,float y) {
  59.     return fabs(x-y)<=epsilon*(fabs(x)+fabs(y))?0:(x<y?-1:1);
  60. }
  61. inline int compare(long double x,long double y) {
  62.     return fabs(x-y)<=epsilon*(fabs(x)+fabs(y))?0:(x<y?-1:1);
  63. }
  64.  
  65.  
  66. /*int compare(double x,double y) {
  67.     return x<y?-1:(x==y?0:1);
  68. }*/
  69.  
  70. //
  71. // General array class. Much like the standard 'vector' class,
  72. // except that it is reference-counted with 'copy on write'
  73. // semantic, so that passing arrays by value is cheap.
  74. //
  75. template<class T> class array {
  76.   public:
  77.     typedef size_t size_type;
  78.     typedef T* iterator;
  79.     typedef const T* const_iterator;
  80.  
  81.     array() : d(NULL),pbeg(NULL),pend(NULL),pcur(NULL) {}
  82.     array(const array& a)
  83.     : d(a.d),pbeg(a.pbeg),pcur(a.pcur),pend(a.pend) {
  84.     if(d)
  85.         ++d->count;
  86.     }
  87.     ~array() { destroy(); }
  88.  
  89.     array& operator = (const array& a) {
  90.     if(&a!=this) {
  91.         destroy();
  92.         d=a.d;
  93.         if(d)
  94.         ++d->count;
  95.         pbeg=a.pbeg;
  96.         pcur=a.pcur;
  97.         pend=a.pend;
  98.     }
  99.     return *this;
  100.     }
  101.  
  102.     size_type size() const { return pcur-pbeg; }
  103.     bool empty() const { return pcur==pbeg; }
  104.     void reserve(size_type);
  105.  
  106.     const T& operator [] (int n) const { return pbeg[n]; }
  107.     //T& operator [] (int n) { return pbeg[n]; }
  108.     class modifier;
  109.     friend class modifier;
  110.     class modifier {
  111.       public:
  112.     explicit modifier(array& a) : arr(a) { a.resize(0); }
  113.     T& operator [] (int n) const { return arr.pbeg[n]; }
  114.       private:
  115.     array& arr;
  116.     };
  117.  
  118.     //iterator begin();
  119.     //iterator end();
  120.     const_iterator begin() const { return pbeg; }
  121.     const_iterator end() const { return pcur; }
  122.  
  123.     //iterator rbegin();
  124.     //iterator rend();
  125.     //const_iterator rbegin() const;
  126.     //const_iterator rend() const;
  127.  
  128.     void push_back(const T& x) {
  129.     if(pcur==pend || d->count!=1)
  130.         resize(1);
  131.     new (pcur) T(x);
  132.     ++pcur;
  133.     }
  134.  
  135.     void pop_back() {
  136.     (--pcur)->~T();
  137.     }
  138.  
  139.     const T& back() const { return pcur[-1]; }
  140.     //T& back() { return pcur[-1]; }
  141.  
  142.     void insert(const_iterator,const T&);
  143.     void erase(const_iterator);
  144.  
  145.     void clear() {
  146.     destroy();
  147.     d=NULL;
  148.     pbeg=pcur=pend=NULL;
  149.     }
  150.  
  151.   private:
  152.     struct data {
  153.     int count;
  154.     T buf[1];
  155.     };
  156.     data* d;
  157.     T* pbeg;
  158.     T* pcur;
  159.     T* pend;
  160.     void destroy();
  161.     void resize(size_type);
  162.     static void destroy(iterator,iterator);
  163.     static void copy(iterator,const_iterator,const_iterator);
  164.     static void move_forward(iterator,iterator,int);
  165.     static void move_backward(iterator,iterator,int);
  166. #ifdef __SASC // SASC has no oprator new/delete[]
  167.     static void* myalloc(size_t sz) { return operator new (sz); }
  168.     static void myfree(void* p) { operator delete (p); }
  169. #else
  170.     static void* myalloc(size_t sz) { return operator new [] (sz); }
  171.     static void myfree(void* p) { operator delete [] (p); }
  172. #endif
  173. };
  174.  
  175.  
  176. template<class T> class Vertex {
  177.   public:
  178.     Vertex() {}
  179.     Vertex(T a,T b) : x(a),y(b) {}
  180.     T x,y;
  181. };
  182.  
  183. template<class T> class Vector {
  184.   public:
  185.     Vector(const Vertex<T>& v1,const Vertex<T>& v2) {
  186.     vertex[0]=v1;
  187.     vertex[1]=v2;
  188.     }
  189.     const Vertex<T>& operator [] (int n) const { return vertex[n]; }
  190.   private:
  191.     Vertex<T> vertex[2];
  192. };
  193.  
  194.  
  195. template<class T> class Line {
  196.   public:
  197.     Line(const Vector<T>& w) {
  198.     T u=w[1].y-w[0].y;
  199.     T v=w[0].x-w[1].x;
  200.     T d=sqrt(u*u+v*v);
  201.     a=u/d;
  202.     b=v/d;
  203.     c=-a*w[0].x-b*w[0].y;
  204.     }
  205.     Line(const Vertex<T>& v1,const Vertex<T>& v2) {
  206.     T u=v2.y-v1.y;
  207.     T v=v1.x-v2.x;
  208.     T d=sqrt(u*u+v*v);
  209.     a=u/d;
  210.     b=v/d;
  211.     c=-a*v1.x-b*v1.y;
  212.     }
  213.     Line(T u,T v,T w) {
  214.     T d=sqrt(u*u+v*v);
  215.     a=u/d;
  216.     b=v/d;
  217.     c=w/d;
  218.     }
  219.  
  220.     Vertex<T> intersection(const Line&) const;
  221.  
  222.     int side(const Vertex<T>&) const;
  223.  
  224.     T a,b,c;
  225. };
  226.  
  227.  
  228. template<class T> class Polygon : public array<Vertex<T> > {
  229.   public:
  230.     Polygon() : convex(false) {}
  231.     //~Polygon();
  232.  
  233.     void is_convex(bool c) { convex=c; }
  234.     bool is_convex() const { return convex; }
  235.     Vertex<T> center() const;
  236.     bool is_rectangle() const;
  237.     void reduce();
  238.  
  239.   private:
  240.     bool convex;
  241. };
  242.  
  243. // Area bounded by a family of polygons.
  244. template<class T> class PArea : public array<Polygon<T> > {
  245.   public:
  246.     enum Rule { even_odd,winding };
  247.  
  248.     PArea() : rule_val(even_odd),convex_union(false) {}
  249.     //~PArea();
  250.  
  251.     void even_odd_rule() { rule_val=even_odd; }
  252.     void winding_rule() { rule_val=winding; }
  253.  
  254.     void rule(Rule r) { rule_val=r; }
  255.     Rule rule() const { return rule_val; }
  256.  
  257.     bool is_convex_union() const { return convex_union; }
  258.     void is_convex_union(bool c) { convex_union=c; }
  259.     bool split(PArea&,PArea&,const Line<T>&) const;
  260.     PArea make_convex_union() const;
  261.  
  262.     void reduce();
  263.  
  264.     bool is_rectangle_union() const;
  265.     bool is_disjoint_rectangle_union() const;
  266.  
  267.   private:
  268.     Rule rule_val;
  269.     bool convex_union;
  270. };
  271.  
  272. template<class T> PArea<T> operator & (const PArea<T>&,const PArea<T>&);
  273.  
  274. #endif
  275.  
  276.