src/polyarea.h

   1 /*
   2       poly_Boolean: a polygon clip library
   3       Copyright (C) 1997  Alexey Nikitin, Michael Leonov
   4       leonov@propro.iis.nsk.su
   5
   6       This library is free software; you can redistribute it and/or
   7       modify it under the terms of the GNU Library General Public
   8       License as published by the Free Software Foundation; either
   9       version 2 of the License, or (at your option) any later version.
  10
  11       This library is distributed in the hope that it will be useful,
  12       but WITHOUT ANY WARRANTY; without even the implied warranty of
  13       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14       Library General Public License for more details.
  15
  16       You should have received a copy of the GNU Library General Public
  17       License along with this library; if not, write to the Free
  18       Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19
  20       polyarea.h
  21       (C) 1997 Alexey Nikitin, Michael Leonov
  22       (C) 1997 Klamer Schutte (minor patches)
  23 */
  24
  25 #ifndef PCB_POLYAREA_H
  26 #define PCB_POLYAREA_H
  27
  28 #ifdef __cplusplus
  29 extern "C" {
  30 #endif
  31
  32 typedef int BOOLp;
  33
  34 #ifndef FALSE
  35 enum {
  36         FALSE = 0,
  37         TRUE  = 1
  38 };
  39 #endif
  40
  41 #define PLF_DIR 1
  42 #define PLF_INV 0
  43 #define PLF_MARK 1
  44
  45 #ifndef min
  46 #define min(x, y) ((x) < (y) ? (x) : (y))
  47 #endif
  48
  49 #ifndef max
  50 #define max(x, y) ((x) > (y) ? (x) : (y))
  51 #endif
  52
  53
  54 typedef Coord vertex[2];  /* longing point representation of
  55                              coordinates */
  56 typedef vertex Vector;
  57
  58 #define VertexEqu(a,b) (memcmp((a),(b),sizeof(Vector))==0)
  59 #define VertexCpy(a,b) memcpy((a),(b),sizeof(Vector))
  60
  61
  62 extern Vector vect_zero;
  63
  64 enum
  65 {
  66     err_no_memory = 2,
  67     err_bad_parm = 3,
  68     err_ok = 0
  69 };
  70
  71
  72 typedef struct CVCList CVCList;
  73 typedef struct VNODE VNODE;
  74 struct CVCList
  75 {
  76     double angle;
  77     VNODE *parent;
  78     CVCList *prev, *next, *head;
  79     char poly, side;
  80 };
  81 struct VNODE
  82 {
  83     VNODE *next, *prev, *shared;
  84     struct {
  85       unsigned int status:3;
  86       unsigned int mark:1;
  87     } Flags;
  88     CVCList *cvc_prev;
  89     CVCList *cvc_next;
  90     Vector point;
  91 };
  92
  93 typedef struct PLINE PLINE;
  94 struct PLINE
  95 {
  96     Coord xmin, ymin, xmax, ymax;
  97     PLINE *next;
  98     VNODE head;
  99     unsigned int Count;
 100     double area;
 101     rtree_t *tree;
 102     bool is_round;
 103     Coord cx, cy;
 104     Coord radius;
 105     struct {
 106       unsigned int status:3;
 107       unsigned int orient:1;
 108     } Flags;
 109 };
 110
 111 PLINE *poly_NewContour(Vector v);
 112
 113 void poly_IniContour(PLINE *  c);
 114 void poly_ClrContour(PLINE *  c);  /* clears list of vertices */
 115 void poly_DelContour(PLINE ** c);
 116
 117 BOOLp poly_CopyContour(PLINE ** dst, PLINE * src);
 118
 119 void poly_PreContour(PLINE * c, BOOLp optimize); /* prepare contour */
 120 void poly_InvContour(PLINE * c);  /* invert contour */
 121
 122 VNODE *poly_CreateNode(Vector v);
 123
 124 void poly_InclVertex(VNODE * after, VNODE * node);
 125 void poly_ExclVertex(VNODE * node);
 126
 127 /**********************************************************************/
 128
 129 typedef struct POLYAREA POLYAREA;
 130 struct POLYAREA
 131 {
 132     POLYAREA *f, *b;
 133     PLINE *contours;
 134     rtree_t *contour_tree;
 135 };
 136
 137 BOOLp poly_M_Copy0(POLYAREA ** dst, const POLYAREA * srcfst);
 138 void poly_M_Incl(POLYAREA **list, POLYAREA *a);
 139
 140 BOOLp poly_Copy0(POLYAREA **dst, const POLYAREA *src);
 141 BOOLp poly_Copy1(POLYAREA  *dst, const POLYAREA *src);
 142
 143 BOOLp poly_InclContour(POLYAREA * p, PLINE * c);
 144 BOOLp poly_ExclContour(POLYAREA * p, PLINE * c);
 145
 146
 147 BOOLp poly_ChkContour(PLINE * a);
 148
 149 BOOLp poly_CheckInside(POLYAREA * c, Vector v0);
 150 BOOLp Touching(POLYAREA *p1, POLYAREA *p2);
 151
 152 /**********************************************************************/
 153
 154 /* tools for clipping */
 155
 156 /* checks whether point lies within contour
 157 independently of its orientation */
 158
 159 int poly_InsideContour(PLINE *c, Vector v);
 160 int poly_ContourInContour(PLINE * poly, PLINE * inner);
 161 POLYAREA *poly_Create(void);
 162
 163 void poly_Free(POLYAREA **p);
 164 void poly_Init(POLYAREA  *p);
 165 void poly_FreeContours(PLINE **pl);
 166 BOOLp poly_Valid(POLYAREA *p);
 167
 168 enum PolygonBooleanOperation {
 169         PBO_UNITE,
 170         PBO_ISECT,
 171         PBO_SUB,
 172         PBO_XOR
 173 };
 174
 175 double vect_dist2 (Vector v1, Vector v2);
 176 double vect_det2 (Vector v1, Vector v2);
 177 double vect_len2 (Vector v1);
 178
 179 int vect_inters2 (Vector A, Vector B, Vector C, Vector D, Vector S1,
 180                   Vector S2);
 181
 182 int poly_Boolean(const POLYAREA * a, const POLYAREA * b, POLYAREA ** res, int action);
 183 int poly_Boolean_free(POLYAREA * a, POLYAREA * b, POLYAREA ** res, int action);
 184 int poly_AndSubtract_free(POLYAREA * a, POLYAREA * b, POLYAREA ** aandb, POLYAREA ** aminusb);
 185 int SavePOLYAREA( POLYAREA *PA, char * fname);
 186 #ifdef __cplusplus
 187 }
 188 #endif
 189
 190 #endif /* PCB_POLYAREA_H */