home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / plane.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  14.8 KB  |  612 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  plane.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18. #ifndef PLANEH
  19. #define PLANEH
  20.  
  21. #include <LEDA/list.h>
  22. #include <LEDA/vector.h>
  23.  
  24. class point;
  25. class segment;
  26.  
  27. //------------------------------------------------------------------------------
  28. // points
  29. //------------------------------------------------------------------------------
  30.  
  31. class point_rep  {
  32.  
  33. friend class point;
  34. friend class segment_rep;
  35. friend class segment;
  36. friend class line_rep;
  37. friend class line;
  38. friend class circle_rep;
  39. friend class circle;
  40.  
  41. public:
  42.  
  43. double x;
  44. double y;
  45. int  count;
  46.  
  47.  
  48. point_rep();     
  49. point_rep(double a, double b);
  50.  
  51.  
  52. OPERATOR_NEW(5)
  53. OPERATOR_DEL(5)
  54.  
  55. };
  56.  
  57. //------------------------------------------------------------------------------
  58.  
  59. class point   {
  60.  
  61. friend class segment_rep;
  62. friend class segment;
  63. friend class line_rep;
  64. friend class line;
  65. friend class circle_rep;
  66. friend class circle;
  67.  
  68. point_rep* ptr;
  69.  
  70. public:
  71.  
  72. point();
  73. point(double, double);
  74. point(vector);
  75. point(point&);
  76. point(ent);
  77. point(int);
  78. void clear();
  79.  
  80. ~point()                 { clear(); }
  81.  
  82. operator  vector()       { return vector(ptr->x,ptr->y); }
  83.  
  84. double xcoord()  const   { return ptr->x; }
  85. double ycoord()  const   { return ptr->y; }
  86.  
  87. double  distance(point);
  88. double  distance();
  89.  
  90. point   translate(double,double);
  91. point   translate(const vector&);
  92.  
  93. point   rotate(point,double);
  94. point   rotate(double);
  95.  
  96. point& operator=(const point& p);
  97.  
  98. point operator+(vector& v) { return translate(v); }
  99.  
  100. int operator==(const point&);
  101.  
  102. int operator!=(const point& p) { return !operator==(p);}
  103.  
  104. friend ostream& operator<<(ostream& out, const point& p) ;
  105. friend istream& operator>>(istream& in, point& p) ;
  106.  
  107. friend void Print(point& p, ostream& out = cout) { out << p; } 
  108. friend void Read(point& p,  istream& in = cin)   { in >> p; }
  109.  
  110. friend void Clear(point& p) { p.clear(); }
  111. friend ent  Init(point& p)  { p.ptr->count++; return ent(p.ptr); }
  112. friend ent  Copy(const point& p)  { p.ptr->count++; return ent(p.ptr); }
  113.  
  114. friend ent  Ent(const point& p)   { return p.ptr; }
  115.  
  116. friend int compare(point&, point&);
  117.  
  118. };
  119.  
  120. declare(list,point)
  121.  
  122.  
  123. //------------------------------------------------------------------------------
  124. // POINT(cmp): points with user defined linear order cmp
  125. //------------------------------------------------------------------------------
  126.  
  127. #define POINT(cmp) name2(point_,cmp)
  128.  
  129. #define POINTdeclare(cmp)\
  130. struct POINT(cmp) : public point \
  131. {  POINT(cmp)(ent p)               : point(p)   {}\
  132.    POINT(cmp)(int p)               : point(p)   {}\
  133.    POINT(cmp)(point  p )           : point(p)   {}\
  134.    POINT(cmp)(POINT(cmp)& p)       : point(p)   {}\
  135.    POINT(cmp)() {}\
  136.  ~ POINT(cmp)() {}\
  137. };\
  138. \
  139. int compare(POINT(cmp)& x, POINT(cmp)& y) { return cmp(x,y); }
  140.  
  141.  
  142. //------------------------------------------------------------------------------
  143. // segments
  144. //------------------------------------------------------------------------------
  145.  
  146. class segment_rep {
  147.  
  148. friend class segment;
  149. friend class line_rep;
  150. friend class line;
  151. friend class circle_rep;
  152. friend class circle;
  153.  
  154. public:
  155.  
  156. point start;
  157. point end;
  158.  
  159. int count;
  160.  
  161. segment_rep(point p, point q);
  162. segment_rep();  
  163.  
  164.  
  165.  
  166. OPERATOR_NEW(3)
  167. OPERATOR_DEL(3)
  168.  
  169. };
  170.  
  171. //------------------------------------------------------------------------------
  172.  
  173. class segment  {
  174.  
  175. friend class line_rep;
  176. friend class line;
  177. friend class circle_rep;
  178. friend class circle;
  179.  
  180. segment_rep* ptr;
  181.  
  182. public:
  183.  
  184. segment();                 
  185. segment(point x, point y); 
  186. segment(double x1, double y1, double x2, double y2) ;
  187. segment(point p, double length, double alpha);
  188. segment(segment&);      
  189. segment(ent);          
  190. segment(int);          
  191. void clear();           
  192.  
  193. ~segment()                { clear(); }
  194.  
  195.  
  196. operator vector()  { return vector(xcoord2()-xcoord1(), ycoord2()-ycoord1()); }
  197.  
  198. bool intersection(segment s, point& inter);
  199.  
  200. point start()  const      { return ptr->start; }
  201. point end()    const      { return ptr->end; }
  202.  
  203. double xcoord1()             { return ptr->start.ptr->x; }
  204. double xcoord2()             { return ptr->end.ptr->x;   }
  205. double ycoord1()             { return ptr->start.ptr->y; }
  206. double ycoord2()             { return ptr->end.ptr->y;   }
  207.  
  208. segment translate(double,double);
  209. segment translate(const vector&);
  210.  
  211. double  angle(segment);
  212. double  angle();
  213. double  direction()          { return angle();}
  214. double  distance(segment);
  215. double  distance(point);
  216. double  distance();
  217. double  slope();
  218. double  y_abs();
  219. double  length();
  220.  
  221. segment rotate(double);
  222. segment rotate(point,double);
  223.  
  224. bool  vertical();
  225. bool  horizontal();
  226.  
  227. bool  right()             { return ptr->start.ptr->x < ptr->end.ptr->x; }
  228. bool  left()              { return ptr->start.ptr->x > ptr->end.ptr->x; }
  229. bool  up()                { return ptr->start.ptr->y < ptr->end.ptr->y; }
  230. bool  down()              { return ptr->start.ptr->y > ptr->end.ptr->y; }
  231.  
  232. segment& operator=(const segment& s);
  233.  
  234. segment operator+(const vector& v) { return translate(v); }
  235.  
  236. int operator==(const segment& s) 
  237. { return (ptr->start == s.ptr->start && ptr->end == s.ptr->end); }
  238.  
  239. int operator!=(const segment& s) { return !operator==(s);}
  240.  
  241. friend ostream& operator<<(ostream& out, const segment& s);
  242. friend istream& operator>>(istream& in, segment& s);
  243.  
  244. friend void Print(segment& s, ostream& out = cout) { out << s << "<" << s.ptr->count << ">"; } 
  245. friend void Read(segment& s,  istream& in = cin)   { in >> s; }
  246.  
  247. friend void Clear(segment& s) { s.clear(); }
  248. friend ent  Init(segment& s)  { s.ptr->count++; return ent(s.ptr); }
  249. friend ent  Copy(const segment& s)  { s.ptr->count++; return ent(s.ptr); }
  250.  
  251. friend ent  Ent(const segment& p)   { return p.ptr; }
  252.  
  253. };
  254.  
  255. declare(list,segment)
  256.  
  257.  
  258. //------------------------------------------------------------------------------
  259. // SEGMENT(cmp): segments with user defined linear order cmp
  260. //------------------------------------------------------------------------------
  261.  
  262. #define SEGMENT(cmp) name2(segment_,cmp)
  263.  
  264. #define SEGMENTdeclare(cmp)\
  265. struct SEGMENT(cmp) : public point \
  266. {  SEGMENT(cmp)(ent p)               : segment(p)   {}\
  267.    SEGMENT(cmp)(int p)               : segment(p)   {}\
  268.    SEGMENT(cmp)(segment  p )         : segment(p)   {}\
  269.    SEGMENT(cmp)(SEGMENT(cmp)& p)     : segment(p)   {}\
  270.    SEGMENT(cmp)() {}\
  271.  ~ SEGMENT(cmp)() {}\
  272. };\
  273. \
  274. int compare(SEGMENT(cmp)& x, SEGMENT(cmp)& y) { return cmp(x,y); }
  275.  
  276.  
  277. //------------------------------------------------------------------------------
  278. // straight lines
  279. //------------------------------------------------------------------------------
  280.  
  281.  
  282. struct line_rep 
  283. {
  284.   segment  seg; 
  285.   int   count;
  286.  
  287.   line_rep(segment s);
  288.   line_rep();
  289.  
  290.  
  291. OPERATOR_NEW(2)
  292. OPERATOR_DEL(2)
  293.  
  294. };
  295.  
  296.  
  297. //------------------------------------------------------------------------------
  298.  
  299. class line  {
  300.  
  301. line_rep* ptr;
  302.  
  303. public:
  304.  
  305. line();
  306. line(line&);
  307. line(segment);
  308. line(ent);
  309. line(int);
  310. line(point, point);
  311. line(point, double);
  312. void clear();
  313.  
  314. ~line()                { clear(); }
  315.  
  316.  
  317.  
  318. bool intersection(line l, point& inter);
  319. bool intersection(segment s, point& inter);
  320.  
  321. bool vertical()        { return ptr->seg.vertical();  }
  322. bool horizontal()      { return ptr->seg.horizontal();}
  323.  
  324. double distance()        { return ptr->seg.distance();  }
  325. double distance(point p) { return ptr->seg.distance(p); }
  326. double angle(line l)     { return ptr->seg.angle(l.ptr->seg); }
  327. double angle()           { return ptr->seg.angle();     }
  328. double direction()       { return angle();}
  329. double slope()           { return ptr->seg.slope();     }
  330. double y_abs()           { return ptr->seg.y_abs();    }
  331.  
  332. segment perpendicular(point q);
  333.  
  334. line    translate(double alpha, double d) { return ptr->seg.translate(alpha,d); }
  335. line    translate(const vector& v)        { return ptr->seg.translate(v); }
  336.  
  337. line    rotate(point o, double alpha){ return ptr->seg.rotate(o,alpha); }
  338. line    rotate(double alpha)         { return rotate(point(0,0),alpha);}
  339.  
  340. double y_proj(double);
  341. double x_proj(double);
  342.  
  343. bool contains(point);
  344. bool contains(segment);
  345.  
  346. line& operator=(const line& l);
  347.  
  348. line operator+(const vector& v) { return translate(v); }
  349.  
  350. int operator==(const line& l) { return contains(l.ptr->seg); }
  351. int operator!=(const line& l) { return !contains(l.ptr->seg); };
  352.  
  353. friend ostream& operator<<(ostream& out, const line& l);
  354. friend istream& operator>>(istream& in, line& l);  
  355.  
  356. friend void Clear(line& l) { l.clear(); }
  357. friend ent  Init(line& l)  { l.ptr->count++; return ent(l.ptr); }
  358.  
  359. friend void Print(line& l, ostream& out = cout) { out << l; } 
  360. friend void Read(line& l,  istream& in = cin)   { in >> l; }
  361.  
  362. friend ent  Copy(const line& l)  { l.ptr->count++; return ent(l.ptr); }
  363.  
  364. friend ent  Ent(const line& p)   { return p.ptr; }
  365.  
  366. };
  367.  
  368. declare(list,line)
  369.  
  370.  
  371. //------------------------------------------------------------------------------
  372. // LINE(cmp): lines with user defined linear order cmp
  373. //------------------------------------------------------------------------------
  374.  
  375. #define LINE(cmp) name2(line_,cmp)
  376.  
  377. #define LINEdeclare(cmp)\
  378. struct LINE(cmp) : public line \
  379. {  LINE(cmp)(ent p)              : line(p)   {}\
  380.    LINE(cmp)(int p)              : line(p)   {}\
  381.    LINE(cmp)(line  p )           : line(p)   {}\
  382.    LINE(cmp)(LINE(cmp)& p)       : line(p)   {}\
  383.    LINE(cmp)() {}\
  384.  ~ LINE(cmp)() {}\
  385. };\
  386. \
  387. int compare(LINE(cmp)& x, LINE(cmp)& y) { return cmp(x,y); }
  388.  
  389.  
  390. //------------------------------------------------------------------------------
  391. // circles
  392. //------------------------------------------------------------------------------
  393.  
  394. struct circle_rep 
  395. {
  396.   double  radius;  // exchanging radius and center yields a compiler error
  397.   point   center; 
  398.   int     count;
  399.  
  400.   circle_rep(point p, double r);
  401.   circle_rep();
  402.  
  403.  
  404. OPERATOR_NEW(4)
  405. OPERATOR_DEL(4)
  406.  
  407. };
  408.  
  409. //------------------------------------------------------------------------------
  410.  
  411. class circle {
  412.  
  413. circle_rep* ptr;
  414.  
  415. public:
  416.  
  417. circle();
  418. circle(circle& l);
  419. circle(point c, double r);
  420. circle(double x, double y, double r);
  421. circle(ent);
  422. circle(int);
  423. void clear();
  424.  
  425. ~circle()                { clear(); }
  426.  
  427.  
  428. circle& operator=(const circle& C) { ptr = C.ptr; ptr->count++; return *this; }
  429.  
  430. circle operator+(const vector& v) { return translate(v); }
  431.  
  432.  
  433. int operator==(const circle&) ;
  434.  
  435. int operator!=(const circle& c) { return !operator==(c); };
  436.  
  437. point center()    const  { return ptr->center; } 
  438. double  radius()  const  { return ptr->radius; }
  439.  
  440.  
  441. double    distance(point);
  442. double    distance(line);
  443. double    distance(circle);
  444. bool    inside(point);
  445. segment left_tangent(point);
  446. segment right_tangent(point);
  447.  
  448. bool    outside(point p) { return !inside(p); };
  449.  
  450. circle  translate(double,double) ;
  451. circle  translate(const vector&) ; 
  452.  
  453. circle  rotate(point, double);
  454. circle  rotate(double);
  455.  
  456.  
  457. list(point) intersection(circle);
  458. list(point) intersection(line);
  459. list(point) intersection(segment);
  460.  
  461. friend ostream& operator<<(ostream& out, const circle& c);
  462. friend istream& operator>>(istream& in, circle& c);  
  463.  
  464. friend void Clear(circle& c) { c.clear(); }
  465. friend ent  Init(circle& c)  { c.ptr->count++; return ent(c.ptr); }
  466.  
  467. friend void Print(circle& c, ostream& out = cout) { out << c; } 
  468. friend void Read(circle& c,  istream& in = cin)   { in >> c; }
  469.  
  470. friend ent  Copy(const circle& c)  { c.ptr->count++; return ent(c.ptr); }
  471.  
  472. friend ent  Ent(const circle& p)   { return p.ptr; }
  473.  
  474. };
  475.  
  476. declare(list,circle)
  477.  
  478.  
  479. //------------------------------------------------------------------------------
  480. // CIRCLE(cmp): circles with user defined linear order cmp
  481. //------------------------------------------------------------------------------
  482.  
  483. #define CIRCLE(cmp) name2(circle_,cmp)
  484.  
  485. #define CIRCLEdeclare(cmp)\
  486. struct CIRCLE(cmp) : public circle \
  487. {  CIRCLE(cmp)(ent p)               : circle(p)   {}\
  488.    CIRCLE(cmp)(int p)               : circle(p)   {}\
  489.    CIRCLE(cmp)(circle  p )          : circle(p)   {}\
  490.    CIRCLE(cmp)(CIRCLE(cmp)& p)      : circle(p)   {}\
  491.    CIRCLE(cmp)() {}\
  492.  ~ CIRCLE(cmp)() {}\
  493. };\
  494. \
  495. int compare(CIRCLE(cmp)& x, CIRCLE(cmp)& y) { return cmp(x,y); }
  496.  
  497.  
  498. //------------------------------------------------------------------------------
  499. // polygons
  500. //------------------------------------------------------------------------------
  501.  
  502. struct polygon_rep 
  503. {
  504.   list(segment) seg_list;
  505.   int   count;
  506.  
  507.   polygon_rep(list(segment) L);
  508.   polygon_rep();
  509.  
  510.  
  511. OPERATOR_NEW(6)
  512. OPERATOR_DEL(6)
  513.  
  514. };
  515.  
  516.  
  517. //------------------------------------------------------------------------------
  518.  
  519. class list(polygon);
  520.  
  521. class polygon {
  522.  
  523.  
  524. polygon_rep* ptr;
  525.  
  526. bool check();
  527.  
  528. public:
  529.  
  530. polygon();
  531. polygon(list(point)&, bool=true);
  532. polygon(polygon& P);
  533. polygon(ent);
  534. polygon(int);
  535. void clear();
  536.  
  537. ~polygon()                { clear(); }
  538.  
  539.  
  540. list(point)   vertices() const;  
  541. list(segment) segments() const { return ptr->seg_list; }
  542.  
  543. bool          inside  (point p); 
  544. bool          outside (point p); 
  545.  
  546. list(point)   intersection(segment s);
  547. list(point)   intersection(line l);  
  548. list(polygon) intersection(polygon P);
  549.  
  550. polygon       translate(double, double);
  551. polygon       translate(const vector&);
  552.  
  553. polygon       rotate(point, double);
  554. polygon       rotate(double);
  555.  
  556. int         size()                  { return ptr->seg_list.size(); }
  557. bool        empty()                 { return ptr->seg_list.empty(); }
  558.  
  559. polygon& operator=(const polygon& P) { ptr = P.ptr; ptr->count++; return *this; }
  560.  
  561. polygon operator+(const vector& v) { return translate(v); }
  562.  
  563. friend ostream& operator<<(ostream& out, const polygon& p);
  564. friend istream& operator>>(istream& in,  polygon& p);
  565.  
  566. friend void Print(polygon& P, ostream& out = cout){ out << P; } 
  567. friend void Read(polygon& P, istream& in = cin) { in  >> P; }
  568.  
  569. friend void Clear(polygon& P){ P.clear(); }
  570. friend ent  Init(polygon& P) { P.ptr->count++; return ent(P.ptr); }
  571. friend ent  Copy(const polygon& P) { P.ptr->count++; return ent(P.ptr); }
  572.  
  573. friend ent  Ent(const polygon& p)  { return p.ptr; }
  574.  
  575. };
  576.  
  577. declare(list,polygon)
  578.  
  579.  
  580. //------------------------------------------------------------------------------
  581. // POLYGON(cmp): polygons with user defined linear order cmp
  582. //------------------------------------------------------------------------------
  583.  
  584. #define POLYGON(cmp) name2(polygon_,cmp)
  585.  
  586. #define POLYGONdeclare(cmp)\
  587. struct POLYGON(cmp) : public polygon \
  588. {  POLYGON(cmp)(ent p)               : polygon(p)   {}\
  589.    POLYGON(cmp)(int p)               : polygon(p)   {}\
  590.    POLYGON(cmp)(polygon  p )         : polygon(p)   {}\
  591.    POLYGON(cmp)(POLYGON(cmp)& p)     : polygon(p)   {}\
  592.    POLYGON(cmp)() {}\
  593.  ~ POLYGON(cmp)() {}\
  594. };\
  595. \
  596. int compare(POLYGON(cmp)& x, POLYGON(cmp)& y) { return cmp(x,y); }
  597.  
  598.  
  599. //------------------------------------------------------------------------------
  600. // some usefull functions
  601. //------------------------------------------------------------------------------
  602.  
  603. extern bool right_turn(point,point,point);
  604. extern bool left_turn(point,point,point);
  605. extern line p_bisector(point p, point q);
  606.  
  607.  
  608. /* #include <LEDA/plane_alg.h> */
  609.  
  610.  
  611. #endif 
  612.