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 _POLYBOOL_H
  26 #define _POLYBOOL_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 int 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     int xmin, ymin, xmax, ymax;
  97     PLINE *next;
  98     VNODE head;
  99     unsigned int Count;
 100     double area;
 101     rtree_t *tree;
 102     struct {
 103       unsigned int status:3;
 104       unsigned int orient:1;
 105     } Flags;
 106 };
 107
 108 PLINE *poly_NewContour(Vector v);
 109
 110 void poly_IniContour(PLINE *  c);
 111 void poly_ClrContour(PLINE *  c);  /* clears list of vertices */
 112 void poly_DelContour(PLINE ** c);
 113
 114 BOOLp poly_CopyContour(PLINE ** dst, PLINE * src);
 115
 116 void poly_PreContour(PLINE * c, BOOLp optimize); /* prepare contour */
 117 void poly_InvContour(PLINE * c);  /* invert contour */
 118
 119 VNODE *poly_CreateNode(Vector v);
 120
 121 void poly_InclVertex(VNODE * after, VNODE * node);
 122 void poly_ExclVertex(VNODE * node);
 123
 124 /**********************************************************************/
 125
 126 typedef struct POLYAREA POLYAREA;
 127 struct POLYAREA
 128 {
 129     POLYAREA *f, *b;
 130     PLINE *contours;
 131 };
 132
 133 BOOLp poly_M_Copy0(POLYAREA ** dst, const POLYAREA * srcfst);
 134 void poly_M_Incl(POLYAREA **list, POLYAREA *a);
 135
 136 BOOLp poly_Copy0(POLYAREA **dst, const POLYAREA *src);
 137 BOOLp poly_Copy1(POLYAREA  *dst, const POLYAREA *src);
 138
 139 BOOLp poly_InclContour(POLYAREA * p, PLINE * c);
 140 BOOLp poly_ExclContour(POLYAREA * p, PLINE * c);
 141
 142
 143 BOOLp poly_ChkContour(PLINE * a);
 144
 145 BOOLp poly_CheckInside(POLYAREA * c, Vector v0);
 146 BOOLp Touching(POLYAREA *p1, POLYAREA *p2);
 147
 148 /**********************************************************************/
 149
 150 /* tools for clipping */
 151
 152 /* checks whether point lies within contour
 153 independently of its orientation */
 154
 155 int poly_InsideContour(PLINE *c, Vector v);
 156 int poly_ContourInContour(PLINE * poly, PLINE * inner);
 157 POLYAREA *poly_Create(void);
 158
 159 void poly_Free(POLYAREA **p);
 160 void poly_Init(POLYAREA  *p);
 161 void poly_FreeContours(PLINE **pl);
 162 BOOLp poly_Valid(POLYAREA *p);
 163
 164 enum PolygonBooleanOperation {
 165         PBO_UNITE,
 166         PBO_ISECT,
 167         PBO_SUB,
 168         PBO_XOR
 169 };
 170
 171 double vect_dist2 (Vector v1, Vector v2);
 172 double vect_det2 (Vector v1, Vector v2);
 173 double vect_len2 (Vector v1);
 174
 175 int vect_inters2 (Vector A, Vector B, Vector C, Vector D, Vector S1,
 176                   Vector S2);
 177
 178 int poly_Boolean(const POLYAREA * a, const POLYAREA * b, POLYAREA ** res, int action);
 179 int poly_Boolean_free(POLYAREA * a, POLYAREA * b, POLYAREA ** res, int action);
 180 int poly_AndSubtract_free(POLYAREA * a, POLYAREA * b, POLYAREA ** aandb, POLYAREA ** aminusb);
 181 int SavePOLYAREA( POLYAREA *PA, char * fname);
 182 #ifdef __cplusplus
 183 }
 184 #endif
 185
 186 #endif /* POLY_H */