home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga 12 / MA_Cover_12.iso / source / xpdf-0.80 / xpdf / poly.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1999-05-19  |  19.4 KB  |  787 lines
  1. //========================================================================
  2. //
  3. // Poly.cc
  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. #ifdef __GNUC__
  14. #pragma implementation
  15. #endif
  16.  
  17. // the "export" keyword not yet supported by compilers
  18. #define export
  19.  
  20. #include <stdio.h>
  21. #include <stdlib.h>
  22. #include "poly.h"
  23.  
  24. #undef STR
  25. #define STR(x)      #x
  26. #define MYASSERT(x) {if(!(x)) {printf(__FILE__"/%d\n",__LINE__);throw("Internal Error");};}
  27.  
  28. #if 0
  29.  
  30. #   define DB(x) x
  31.     template<class T> void showp(const Polygon<T>& p) {
  32.     printf("poly(%d):",p.size());
  33.     for(typename Polygon<T>::const_iterator i(p.begin());i!=p.end();++i)
  34.         printf(" (%g,%g)",double(i->x),double(i->y));
  35.     printf("\n");
  36.     }
  37. #   if 0
  38.     extern bool show_steps;
  39.     void clear();
  40.     void draw(int color,int x0,int y0,const Vector<double>&);
  41.     void draw(int color,int x0,int y0,const Polygon<double>&);
  42.     void draw(int color,int x0,int y0,const PArea<double>&);
  43.     bool wait();
  44. #       define CLEAR       {if(show_steps) clear();}
  45. #       define DRAW(c,x)   {if(show_steps) draw(c,370,250,(x));}
  46. #       define WAIT        {if(show_steps && wait()) return res;}
  47. #   else
  48. #       define CLEAR
  49. #       define DRAW(c,x)
  50. #       define WAIT
  51. #   endif
  52.  
  53. #else
  54.  
  55. #   define DB(x)
  56.  
  57. #endif
  58.  
  59. export template<class T> void array<T>::destroy(iterator p,iterator q) {
  60.     while(q!=p)
  61.        (--q)->~T();
  62. }
  63.  
  64. export template<class T> void array<T>::destroy() {
  65.     if(d && --d->count==0) {
  66.     destroy(pbeg,pcur);
  67.     myfree(d);
  68.     }
  69. }
  70.  
  71. export template<class T> void array<T>::copy(iterator p,const_iterator q,const_iterator r) {
  72.     iterator s=p;
  73.     try {
  74.     while(q!=r) {
  75.         new (p) T(*q);
  76.         ++p;
  77.         ++q;
  78.     }
  79.     }
  80.     catch(...) {
  81.     destroy(s,p);
  82.     rethrow;
  83.     }
  84. }
  85.  
  86. export template<class T> void array<T>::reserve(size_type sz) {
  87.     if(pend-pbeg<sz || (d && d->count>1)) {
  88.     data* d1=static_cast<data*>(myalloc(sizeof(data)-sizeof(T)+sizeof(T)*sz));
  89.     d1->count=1;
  90.     try {
  91.         if(pbeg!=pcur)
  92.         copy(d1->buf,pbeg,pcur);
  93.     }
  94.     catch(...) {
  95.         myfree(d1);
  96.         rethrow;
  97.     }
  98.     destroy();
  99.     d=d1;
  100.     pcur=d1->buf+(pcur-pbeg);
  101.     pbeg=d1->buf;
  102.     pend=pbeg+sz;
  103.     }
  104. }
  105.  
  106. export template<class T> void array<T>::resize(size_type sz) {
  107.     size_type s=size();
  108.     size_type t=s/2;
  109.     if(sz>=t)
  110.     t+=sz;
  111.     if(t<10)
  112.     t+=10;
  113.     reserve(s+t);
  114. }
  115.  
  116. export template<class T> void array<T>::move_forward(iterator p,iterator q,int n) {
  117.     iterator r=q;
  118.     try {
  119.     while(q!=p) {
  120.         --q;
  121.         new (q+n) T(*q);
  122.     }
  123.     }
  124.     catch(...) {
  125.     destroy(q+n+1,r+n);
  126.     destroy(p,q);
  127.     rethrow;
  128.     }
  129. }
  130.  
  131. export template<class T> void array<T>::move_backward(iterator p,iterator q,int n) {
  132.     iterator r=p;
  133.     try {
  134.     while(p!=q) {
  135.         new (p-n) T(*p);
  136.         ++p;
  137.     }
  138.     }
  139.     catch(...) {
  140.     destroy(r-n,p-n);
  141.     destroy(p,q);
  142.     rethrow;
  143.     }
  144. }
  145.  
  146. export template<class T> void array<T>::insert(const_iterator p,const T& x) {
  147.     int k=p-pbeg;
  148.     if(pcur==pend || d->count!=1)
  149.     resize(1);
  150.     try {
  151.     move_forward(pbeg+k,pcur,1);
  152.     }
  153.     catch(...) {
  154.     pcur=pbeg+k;
  155.     rethrow;
  156.     }
  157.     ++pcur;
  158.     try {
  159.     new (pbeg+k) T(x);
  160.     }
  161.     catch(...) {
  162.     destroy(pbeg+k+1,pcur);
  163.     pcur=pbeg+k;
  164.     rethrow;
  165.     }
  166. }
  167.  
  168. export template<class T> void array<T>::erase(const_iterator p) {
  169.     int k=p-pbeg;
  170.     resize(0);
  171.     pbeg[k].~T();
  172.     try {
  173.     move_backward(pbeg+k+1,pcur,1);
  174.     }
  175.     catch(...) {
  176.     pcur=pbeg+k;
  177.     rethrow;
  178.     }
  179.     --pcur;
  180. }
  181.  
  182. /*
  183.  *  Class Line.
  184.  */
  185.  
  186. export template<class T> Vertex<T> Line<T>::intersection(const Line<T>& l) const {
  187.     T d=b*l.a-a*l.b;
  188.     return Vertex<T>((c*l.b-b*l.c)/d,(a*l.c-c*l.a)/d);
  189. }
  190.  
  191. export template<class T> int Line<T>::side(const Vertex<T>& v) const {
  192.     T d=a*v.x+b*v.y+c;
  193.     return d<-0.01?-1:(d>0.01?1:0);
  194. }
  195.  
  196. /*
  197.  *  Class Polygon.
  198.  */
  199.  
  200. export template<class T> Vertex<T> Polygon<T>::center() const {
  201.     Vertex<T> r(0,0);
  202.     if(!empty()) {
  203.     for(const_iterator i(begin());i!=end();++i) {
  204.         r.x+=i->x;
  205.         r.y+=i->y;
  206.     }
  207.     r.x/=size();
  208.     r.y/=size();
  209.     }
  210.     return r;
  211. }
  212.  
  213. export template<class T> bool Polygon<T>::is_rectangle() const {
  214.     return (size()==4 ||
  215.         (size()==5 && (*this)[0].x==(*this)[4].x &&
  216.          (*this)[0].y==(*this)[4].y)) &&
  217.         (((*this)[0].x==(*this)[1].x &&
  218.           (*this)[2].x==(*this)[3].x &&
  219.           (*this)[0].y==(*this)[3].y &&
  220.           (*this)[1].y==(*this)[2].y) ||
  221.          ((*this)[1].x==(*this)[2].x &&
  222.           (*this)[0].x==(*this)[3].x &&
  223.           (*this)[0].y==(*this)[1].y &&
  224.           (*this)[2].y==(*this)[3].y));
  225. }
  226.  
  227. export template<class T> void Polygon<T>::reduce() {
  228.     if(!empty() && !compare(begin()->x,back().x) &&
  229.        !compare(begin()->y,back().y))
  230.     pop_back();
  231. }
  232.  
  233.  
  234. /*
  235.  *  Split a polygon along a line.
  236.  */
  237.  
  238. template<class T> class splitter {
  239.     friend bool PArea<T>::split(PArea<T>&,PArea<T>&,const Line<T>&) const;
  240.  
  241.     struct vinfo {
  242.     Vertex<T> vertex;
  243.     signed char side;
  244.     signed char real_side;
  245.     };
  246.     typedef array<vinfo> varray;
  247.     typedef array<varray> parray;
  248.     typedef typename array<vinfo>::const_iterator viterator;
  249.     typedef typename array<varray>::const_iterator piterator;
  250.  
  251.     struct iinfo {
  252.     piterator poly;
  253.     viterator vertex;
  254.     int dir; // 1 if going from - to +, -1 otherwise.
  255.     bool inside;
  256.     bool pos_side_done;
  257.     bool neg_side_done;
  258.     };
  259.  
  260.     typedef array<iinfo> iarray;
  261.     typedef typename array<iinfo>::const_iterator iiterator;
  262.  
  263.     void follow(PArea<T>& res,piterator p,viterator q,
  264.         int dir,int side,bool,int,viterator stop);
  265.  
  266.     iarray inter;
  267. };
  268.  
  269. template<class T> void splitter<T>::follow(PArea<T>& r,
  270.                        piterator p,
  271.                        viterator q,
  272.                        int dir,
  273.                        int side,
  274.                        bool odd,
  275.                        int inum,
  276.                        viterator stop) {
  277.     DB(printf("following until (%g,%g,%d)\n",double(stop->vertex.x),double(stop->vertex.y),stop->side);)
  278.     DB(printf("(%g,%g,%d)\n",double(q->vertex.x),double(q->vertex.y),q->side);)
  279.     Polygon<T> res;
  280.     res.push_back(q->vertex);
  281.     bool is_non_trivial=false;
  282.     viterator first(p->begin());
  283.     viterator last(p->end());
  284.     viterator lastq=stop;
  285.     viterator lastlastq;
  286.     viterator q0=q;
  287.     typename iarray::modifier interm(inter);
  288.     int check=inter.size();
  289.     while(true) {
  290.     lastlastq=lastq;
  291.     lastq=q;
  292.     if(dir==1) {
  293.         ++q;
  294.         if(q==last)
  295.         q=first;
  296.     } else {
  297.         if(q==first)
  298.         q=last;
  299.         --q;
  300.     }
  301.     if(q->real_side!=0)
  302.         is_non_trivial=true;
  303.     else {
  304.         if(lastq->side==0 && lastlastq->side==0) {
  305.         DB(printf("...removing last\n");)
  306.         res.pop_back();
  307.         lastq=lastlastq;
  308.         }
  309.     }
  310.     DB(printf("...(%g,%g,%d)\n",double(q->vertex.x),double(q->vertex.y),q->side);)
  311.     res.push_back(q->vertex);
  312.     if(q->side==0) {
  313.         MYASSERT(check-->=0);
  314.         int i=0;
  315.         while(inter[i].vertex!=q) {
  316.         ++i;
  317.         MYASSERT(i<inter.size());
  318.         }
  319.         DB(printf("this is intersection %d\n",i);)
  320.         if(side==1)
  321.         interm[i].pos_side_done=true;
  322.         else
  323.         interm[i].neg_side_done=true;
  324.         if(q==stop)
  325.         break;
  326.         if(i>inum) {
  327.         int k=inum;
  328.         while(k<i && inter[k].inside)
  329.             ++k;
  330.         if(k==i)
  331.             break;
  332.         }
  333.         if(!(i&1)) {
  334.  
  335.         int check=inter.size();
  336.         do {
  337.             ++i;
  338.             if(i==inter.size()) // might happen for winding rule
  339.             i=0;            // and self-intersecting polygons.
  340.             MYASSERT(check-->=0);
  341.         } while((side==1 && inter[i].pos_side_done) ||
  342.             (side==-1 && inter[i].neg_side_done));
  343.         } else {
  344.  
  345.         int check=inter.size();
  346.         do {
  347.             if(i==0)            // idem.
  348.             i=(int)inter.size()-1;
  349.             else
  350.             --i;
  351.             MYASSERT(check-->=0);
  352.         } while((side==1 && inter[i].pos_side_done) ||
  353.             (side==-1 && inter[i].neg_side_done));
  354.         }
  355.         if(side==1)
  356.         interm[i].pos_side_done=true;
  357.         else
  358.         interm[i].neg_side_done=true;
  359.         p=inter[i].poly;
  360.         first=p->begin();
  361.         last=p->end();
  362.         lastlastq=lastq;
  363.         lastq=q;
  364.         q=inter[i].vertex;
  365.         dir=inter[i].dir*side;
  366.         DB(printf("next=%d, dir=%d\n",i,dir);)
  367.         if(q==stop)
  368.         break;
  369.         if(q->real_side!=0)
  370.         is_non_trivial=true;
  371.         else {
  372.         if(lastq->side==0 && lastlastq->side==0) {
  373.             DB(printf("...removing last\n");)
  374.             res.pop_back();
  375.             lastq=lastlastq;
  376.         }
  377.         }
  378.         DB(printf("...(%g,%g,%d)\n",double(q->vertex.x),double(q->vertex.y),q->side);)
  379.         res.push_back(q->vertex);
  380.     }
  381.     }
  382.     if(q0->real_side!=0)
  383.     is_non_trivial=true;
  384.     else {
  385.     if(lastq->side==0 && lastlastq->side==0) {
  386.         DB(printf("...removing last\n");)
  387.         res.pop_back();
  388.     }
  389.     }
  390.     if(is_non_trivial) {
  391.     DB(printf("follow: added ");showp(res);)
  392.     r.push_back(res);
  393.     }
  394. }
  395.  
  396. export template<class T> bool PArea<T>::split(PArea<T>& pos,PArea<T>& neg,const Line<T>& line) const {
  397.  
  398.     DB(printf("*** splitting along (%g,%g,%g)\n",double(line.a),double(line.b),double(line.c));)
  399.  
  400.     splitter<T> sp;
  401.  
  402.     typedef typename splitter<T>::parray parray;
  403.     typedef typename splitter<T>::varray varray;
  404.     typedef typename splitter<T>::iarray iarray;
  405.     typedef typename splitter<T>::viterator viterator;
  406.     typedef typename splitter<T>::iiterator iiterator;
  407.     typedef typename splitter<T>::vinfo vinfo;
  408.     typedef typename splitter<T>::iinfo iinfo;
  409.  
  410.     parray area;
  411.     array<signed char> side;
  412.     area.reserve(size());
  413.     bool has_true_inter=false;
  414.  
  415.     for(const_iterator p(begin());p!=end();++p) {
  416.     DB(printf("split1: ");showp(*p);)
  417.     if(p->empty())
  418.         continue;
  419.     vinfo lastv;
  420.     lastv.vertex=p->end()[-1];
  421.     lastv.side=(signed char)line.side(lastv.vertex);
  422.     varray poly;
  423.  
  424.     // Get the list of all vertices, with their sides.
  425.     // Add all intersection points.
  426.     bool has_pos_side=false;
  427.     bool has_neg_side=false;
  428.     for(typename Polygon<T>::const_iterator i(p->begin());i!=p->end();++i) {
  429.         vinfo v;
  430.         v.vertex=*i;
  431.         v.real_side=(signed char)line.side(v.vertex);
  432.         v.side=v.real_side;
  433.         if(v.side==1)
  434.         has_pos_side=true;
  435.         else if(v.side==-1)
  436.         has_neg_side=true;
  437.         if(v.side!=0 && v.side+lastv.side==0) {
  438.         vinfo vi;
  439.         vi.vertex=line.intersection(Line<T>(lastv.vertex,v.vertex));
  440.         vi.side=0;
  441.         vi.real_side=0;
  442.         DB(printf("(%g,%g,0)\n",double(vi.vertex.x),double(vi.vertex.y));)
  443.         poly.push_back(vi);
  444.         }
  445.         DB(printf("(%g,%g,%d)\n",double(v.vertex.x),double(v.vertex.y),v.side);)
  446.         poly.push_back(v);
  447.         lastv=v;
  448.     }
  449.     if(has_pos_side && has_neg_side)
  450.         has_true_inter=true;
  451.  
  452.     int k=0;
  453.     size_t n=poly.size();
  454.     while(k<n && poly[k].side==0)
  455.         ++k;
  456.     if(k!=n) {
  457.         DB(printf("normalizing\n");)
  458.         int k0=k;
  459.         //  ... + 0 ... 0 - ... -> ... + 0 - ...
  460.         //  ... + 0 ... 0 + ... -> ... + 0 0 + ...
  461.         signed char s1=poly[k].side;
  462.         signed char s2=s1;
  463.         {
  464.         typename varray::modifier polym(poly);
  465.         do {
  466.             int l=k;
  467.             ++k;
  468.             if(k==n)
  469.             k=0;
  470.             signed char s=poly[k].side;
  471.             //printf("l=%d k=%d s=%d s1=%d s2=%d\n",l,k,s,s1,s2);
  472.             if(s==0) {
  473.             if(s1==0)
  474.                 polym[k].side=(signed char)-s2;
  475.             else
  476.                 s2=s1;
  477.             } else {
  478.             if(s1==0 && s==s2) {
  479.                 if(poly[l].side==0) {
  480.                 //  |/      |  /
  481.                 //  +   ==  | |
  482.                 //  |\      |  \
  483.                 //printf("-> (%g,%g,%d) !!\n",poly[l].vertex.x,poly[l].vertex.y,poly[l].side);
  484.                 //printf("l=%d k=%d s=%d s1=%d s2=%d\n",l,k,s,s1,s2);
  485.                 polym[l].side=s2;
  486.                 //printf("-> (%g,%g,%d) !!\n",poly[l].vertex.x,poly[l].vertex.y,poly[l].side);
  487.                 } else
  488.                 polym[l].side=0;
  489.             }
  490.             }
  491.             s1=s;
  492.         } while (k!=k0);
  493.         DB(printf("poly(%d):",poly.size());
  494.            for(viterator i(poly.begin());i!=poly.end();++i)
  495.                printf(" (%g,%g,%d)",double(i->vertex.x),double(i->vertex.y),i->side);
  496.            printf("\n");)
  497.         }
  498.  
  499.         area.push_back(poly);
  500.         // Collect intersection points.
  501.         bool has_inter=false;
  502.         s1=poly[n-1].side;
  503.         for(int i=0;i<n;++i) {
  504.         if(poly[i].side==0) {
  505.             has_inter=true;
  506.             iinfo t;
  507.             t.poly=area.end()-1;
  508.             t.vertex=t.poly->begin()+i;
  509.             if(s1==0) {
  510.             if(i==n-1)
  511.                 t.dir=poly[0].side;
  512.             else
  513.                 t.dir=poly[i+1].side;
  514.             } else
  515.             t.dir=-s1;
  516.  
  517.             // insert sorted.
  518.             size_t l=sp.inter.size();
  519.             iiterator q(sp.inter.begin());
  520.             while(l) {
  521.             size_t k=l/2;
  522.             iiterator q1(q+k);
  523.             T tst=line.a*(t.vertex->vertex.y-q1->vertex->vertex.y)-
  524.                   line.b*(t.vertex->vertex.x-q1->vertex->vertex.x);
  525.             if(tst>0) {
  526.                 q=q1+1;
  527.                 l-=k+1;
  528.             } else if(tst==0) {
  529.                 q=q1;
  530.                 break;
  531.             } else
  532.                 l=k;
  533.             }
  534.             sp.inter.insert(q,t);
  535.         }
  536.         s1=poly[i].side;
  537.         }
  538.  
  539.         DB(printf("inter(%d):",sp.inter.size());
  540.            for(iiterator i(sp.inter.begin());i!=sp.inter.end();++i)
  541.            printf(" (%g,%g,%d)",double(i->vertex->vertex.x),double(i->vertex->vertex.y),i->dir);
  542.            printf("\n");)
  543.  
  544.  
  545.         if(!has_inter) {
  546.         side.push_back(0);
  547.         area.pop_back();
  548.         if(has_neg_side) {
  549.             DB(printf("adding to - side: ");showp(*p);)
  550.             neg.push_back(*p);
  551.         } else {
  552.             DB(printf("adding to + side: ");showp(*p);)
  553.             pos.push_back(*p);
  554.         }
  555.         } else {
  556.         MYASSERT(!(sp.inter.size()&1));
  557.         side.push_back((signed char)(has_neg_side?-1:1));
  558.         }
  559.     } else {
  560.         // The polygon is degenerated and on the line.
  561.         //pos.push_back(*p);
  562.         side.push_back(0);
  563.     }
  564.     }
  565.  
  566.     if(has_true_inter) {
  567.     int num_segs=sp.inter.size()-1;
  568.     int w=0;
  569.     typename iarray::modifier m(sp.inter);
  570.     for(int k=0;k<num_segs+1;++k) {
  571.         w+=m[k].dir;
  572.         m[k].inside=!(k&1) || (rule()==winding && w);
  573.         m[k].pos_side_done=false;
  574.         m[k].neg_side_done=false;
  575.     }
  576.     for(int k=0;k<num_segs;++k) {
  577.         iinfo& i=m[k];
  578.         if(i.inside) {
  579.         if(!i.pos_side_done) {
  580.             DB(printf("following + side of intersection %d\n",k);)
  581.             i.pos_side_done=true;
  582.             sp.follow(pos,i.poly,i.vertex,
  583.                   i.dir,1,k&1,k,sp.inter[k+1].vertex);
  584.         }
  585.         if(!i.neg_side_done) {
  586.             DB(printf("following - side of intersection %d\n",k);)
  587.             i.neg_side_done=true;
  588.             sp.follow(neg,i.poly,i.vertex,
  589.                   -i.dir,-1,k&1,k,sp.inter[k+1].vertex);
  590.         }
  591.         }
  592.     }
  593.     return true;
  594.     } else {
  595.     DB(printf("No real intersection.\n");)
  596.     array<signed char>::const_iterator q(side.begin());
  597.     for(const_iterator p(begin());p!=end() && q!=side.end();++p)
  598.         if(!p->empty()) {
  599.         if(*q) {
  600.             if(*q==1) {
  601.             DB(printf("adding to + side: ");showp(*p);)
  602.             pos.push_back(*p);
  603.             } else {
  604.             DB(printf("adding to - side: ");showp(*p);)
  605.             neg.push_back(*p);
  606.             }
  607.         }
  608.         ++q;
  609.         }
  610.     return false;
  611.     }
  612. }
  613.  
  614. /*
  615.  *  Transform a PArea into a union of interiors of convex polygons.
  616.  */
  617. // Issue: it does not work correctly for areas bounded by
  618. // non-convex polygons with empty interior.
  619.  
  620. export template<class T> PArea<T> PArea<T>::make_convex_union() const {
  621.  
  622.     if(is_convex_union())
  623.     return *this;
  624.  
  625.     PArea<T> res;
  626.     res.rule(rule());
  627.  
  628.     if(!empty()) {
  629.     array<PArea<T> > stack;
  630.  
  631.     stack.push_back(*this);
  632.     do {
  633.         PArea<T> a(stack.back());
  634.         stack.pop_back();
  635.  
  636.         DB(CLEAR;DRAW(1,a);printf("----pop\n");WAIT;)
  637.  
  638.         bool splitted=false;
  639.         for(const_iterator poly(a.begin());!splitted && poly!=a.end();++poly)
  640.         if(!poly->empty()) {
  641.             typename Polygon<T>::const_iterator v(poly->end()-1);
  642.             typename Polygon<T>::const_iterator u(poly->begin());
  643.             while(!splitted && u!=poly->end()) {
  644.             if(compare(u->x,v->x) || compare(u->y,v->y)) {
  645.  
  646.                 DB(CLEAR;DRAW(1,a);DRAW(2,Vector<T>(*v,*u));printf("----splitting\n");WAIT;)
  647.  
  648.                 Line<T> line(*v,*u);
  649.                 PArea<T> pos;
  650.                 PArea<T> neg;
  651.                 pos.rule(rule());
  652.                 neg.rule(rule());
  653.                 a.split(pos,neg,line);
  654.                 if(!pos.empty() && !neg.empty()) {
  655.                 DB(CLEAR;DRAW(1,pos);DRAW(2,neg);printf("----splitted\n");WAIT;)
  656.                 stack.push_back(pos);
  657.                 stack.push_back(neg);
  658.                 splitted=true;
  659.                 } else {
  660.                 v=u;
  661.                 ++u;
  662.                 }
  663.             } else {
  664.                 v=u;
  665.                 ++u;
  666.             }
  667.             }
  668.         }
  669.         if(!splitted) {
  670.         // 'a' is a convex area. Its border is made
  671.         // of exactly one polygon.
  672.         const_iterator p(a.begin());
  673.         while(p!=a.end() && p->empty())
  674.             ++p;
  675.         if(p!=a.end()) { // just in case...
  676.             Polygon<T> x(*p);
  677.             x.is_convex(true);
  678.             res.push_back(x);
  679.         }
  680.         }
  681.     } while(!stack.empty());
  682.     }
  683.     res.is_convex_union(true);
  684.     return res;
  685. }
  686.  
  687. export template<class T> PArea<T> operator & (const PArea<T>& a,const PArea<T>& b) {
  688.     PArea<T> a1(a.make_convex_union());
  689.     PArea<T> res;
  690.  
  691.     for(typename PArea<T>::const_iterator i(a1.begin());i!=a1.end();++i) {
  692.     if(!i->empty()) {
  693.         PArea<T> c(b);
  694.         Vertex<T> o(i->center());
  695.         typename Polygon<T>::const_iterator v(i->end()-1);
  696.         typename Polygon<T>::const_iterator u(i->begin());
  697.         while(u!=i->end()) {
  698.         if(compare(u->x,v->x) || compare(u->y,v->y)) {
  699.             Line<T> line(*v,*u);
  700.             PArea<T> pos;
  701.             PArea<T> neg;
  702.             pos.rule(b.rule());
  703.             neg.rule(b.rule());
  704.             c.split(pos,neg,line);
  705.             if(line.side(o)==-1)
  706.             c=neg;
  707.             else
  708.             c=pos;
  709.         }
  710.         v=u;
  711.         ++u;
  712.         }
  713.         for(typename PArea<T>::const_iterator j(c.begin());j!=c.end();++j)
  714.         res.push_back(*j);
  715.     }
  716.     }
  717.     return res;
  718. }
  719.  
  720. export template<class T> void PArea<T>::reduce() {
  721.     typename array<Polygon<T> >::modifier m(*this);
  722.     for(int k=0;k<size();++k)
  723.     m[k].reduce();
  724. }
  725.  
  726. export template<class T> bool PArea<T>::is_rectangle_union() const {
  727.     for(const_iterator p(begin());p!=end();++p)
  728.     if(!p->is_rectangle())
  729.         return false;
  730.     return true;
  731. }
  732.  
  733. // not really implemented...
  734. export template<class T> bool PArea<T>::is_disjoint_rectangle_union() const {
  735.     return size()==1 && begin()->is_rectangle();
  736. }
  737.  
  738.  
  739. // until compilers support the "export" keyword...
  740.  
  741. template int Line<double>::side(const Vertex<double>&) const;
  742. template Vertex<double> Line<double>::intersection(const Line<double>&) const;
  743. template void Polygon<double>::reduce();
  744. template Vertex<double> Polygon<double>::center() const;
  745. template bool PArea<double>::split(PArea<double>&,PArea<double>&,const Line<double>&) const;
  746. template PArea<double> PArea<double>::make_convex_union() const;
  747. template PArea<double> operator & (const PArea<double>&,const PArea<double>&);
  748. template void PArea<double>::reduce();
  749. template void splitter<double>::follow(PArea<double>&,piterator,viterator,int,int,bool,int,viterator);
  750.  
  751. template void array<Vertex<double> >::reserve(size_type);
  752. template void array<Vertex<double> >::resize(size_type);
  753. template void array<Vertex<double> >::destroy();
  754. template void array<Polygon<double> >::reserve(size_type);
  755. template void array<Polygon<double> >::resize(size_type);
  756. template void array<Polygon<double> >::destroy();
  757. template void array<PArea<double> >::reserve(size_type);
  758. template void array<PArea<double> >::resize(size_type);
  759. template void array<PArea<double> >::destroy();
  760.  
  761. template void array<splitter<double>::iinfo>::reserve(size_type);
  762. template void array<splitter<double>::iinfo>::resize(size_type);
  763. template void array<splitter<double>::iinfo>::destroy();
  764. //template void array<splitter<double>::iinfo>::destroy(iterator,iterator);
  765. template void array<splitter<double>::vinfo>::reserve(size_type);
  766. template void array<splitter<double>::vinfo>::resize(size_type);
  767. template void array<splitter<double>::vinfo>::destroy();
  768. template void array<array<splitter<double>::vinfo> >::reserve(size_type);
  769. template void array<array<splitter<double>::vinfo> >::resize(size_type);
  770. template void array<array<splitter<double>::vinfo> >::destroy();
  771.  
  772. template void array<Vertex<short> >::reserve(size_type);
  773. template void array<Vertex<short> >::resize(size_type);
  774. template void array<Vertex<short> >::destroy();
  775. template void array<Polygon<short> >::reserve(size_type);
  776. template void array<Polygon<short> >::resize(size_type);
  777. template void array<Polygon<short> >::destroy();
  778. template bool PArea<short>::is_disjoint_rectangle_union() const;
  779. template bool PArea<short>::is_rectangle_union() const;
  780. template bool Polygon<short>::is_rectangle() const;
  781. //template void PArea<short>::reduce();
  782.  
  783. template void array<signed char>::reserve(size_type);
  784. template void array<signed char>::resize(size_type);
  785. template void array<signed char>::destroy();
  786.  
  787.