Warning, /include/Geant4/tools/zb/polygon is written in an unsupported language. File is not indexed.
0001 // Copyright (C) 2010, Guy Barrand. All rights reserved.
0002 // See the file tools.license for terms.
0003
0004 #ifndef tools_zb_polygon
0005 #define tools_zb_polygon
0006
0007 #include "edge_table"
0008 #include "../mnmx"
0009
0010 namespace tools {
0011 namespace zb {
0012
0013 class polygon {
0014
0015 static const int NUMPTSTOBUFFER = 200;
0016
0017 typedef struct _POINTBLOCK {
0018 point pts[NUMPTSTOBUFFER];
0019 struct _POINTBLOCK* next;
0020 } POINTBLOCK;
0021
0022 int m_pETEn;
0023 EdgeTableEntry* m_pETEs;
0024 int m_numAllocPtBlocks;
0025 POINTBLOCK m_FirstPtBlock;
0026 public:
0027 polygon():m_pETEn(0),m_pETEs(NULL),m_numAllocPtBlocks(0){}
0028 virtual ~polygon(){clear();}
0029 protected:
0030 polygon(const polygon&){}
0031 polygon& operator=(const polygon&){return *this;}
0032 public:
0033 void clear(){
0034 POINTBLOCK* curPtBlock;
0035 cmem_free(m_pETEs);
0036 m_pETEn = 0;
0037 for(curPtBlock = m_FirstPtBlock.next; --m_numAllocPtBlocks >= 0;){
0038 POINTBLOCK* tmpPtBlock;
0039 tmpPtBlock = curPtBlock->next;
0040 cmem_free(curPtBlock);
0041 curPtBlock = tmpPtBlock;
0042 }
0043 m_numAllocPtBlocks = 0;
0044 }
0045
0046 typedef void (*scan_func)(void*,int,int,int);
0047
0048 void scan(int Count, /* number of pts */
0049 const point* Pts, /* the pts */
0050 int rule, /* winding rule */
0051 scan_func a_proc,void* a_tag,
0052 unsigned int a_width,unsigned int a_height){
0053 // polytoregion
0054 // Scan converts a polygon by returning a run-length
0055 // encoding of the resultant bitmap -- the run-length
0056 // encoding is in the form of an array of rectangles.
0057
0058 EdgeTableEntry* pAET; /* Active Edge Table */
0059 int y; /* current scanline */
0060 int iPts = 0; /* number of pts in buffer */
0061 EdgeTableEntry* pWETE; /* Winding Edge Table Entry*/
0062 ScanLineList* pSLL; /* current scanLineList */
0063
0064 EdgeTableEntry* pPrevAET; /* ptr to previous AET */
0065 EdgeTable ET; /* header node for ET */
0066 EdgeTableEntry AET; /* header node for AET */
0067 ScanLineListBlock SLLBlock; /* header for scanlinelist */
0068 int fixWAET = 0;
0069 POINTBLOCK* curPtBlock;
0070 int numFullPtBlocks = 0;
0071
0072 if(a_proc==NULL) return;
0073 if(Count==0) return;
0074
0075 if(Count==3) {
0076 point pts[3];
0077 pts[0] = Pts[0];
0078 pts[1] = Pts[1];
0079 pts[2] = Pts[2];
0080
0081 point vp_down[3];
0082 vp_down[0] = point(0,0,0);
0083 vp_down[1] = point(a_width,0,0);
0084 vp_down[2] = point(a_width,a_height,0);
0085 if(triangles_overlap(pts,vp_down)) {
0086 } else {
0087 point vp_up[3];
0088 vp_up[0] = point(0,0,0);
0089 vp_up[1] = point(a_width,a_height,0);
0090 vp_up[2] = point(0,a_height,0);
0091 if(!triangles_overlap(pts,vp_up)) return;
0092 }
0093 }
0094
0095 int pts_xmin = Pts[0].x;
0096 int pts_xmax = pts_xmin;
0097 int pts_ymin = Pts[0].y;
0098 int pts_ymax = pts_ymin;
0099 {for(int count=1;count<Count;count++) {
0100 if(Pts[count].x<pts_xmin) pts_xmin = Pts[count].x;
0101 if(Pts[count].x>pts_xmax) pts_xmax = Pts[count].x;
0102 if(Pts[count].y<pts_ymin) pts_ymin = Pts[count].y;
0103 if(Pts[count].y>pts_ymax) pts_ymax = Pts[count].y;
0104 }}
0105
0106 /* special case a rectangle */
0107 point* pts = (point*)Pts;
0108 if (((Count == 4) ||
0109 ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
0110 (((pts[0].y == pts[1].y) &&
0111 (pts[1].x == pts[2].x) &&
0112 (pts[2].y == pts[3].y) &&
0113 (pts[3].x == pts[0].x)) ||
0114 ((pts[0].x == pts[1].x) &&
0115 (pts[1].y == pts[2].y) &&
0116 (pts[2].x == pts[3].x) &&
0117 (pts[3].y == pts[0].y))))
0118 {
0119 int xmin,xmax,ymin,ymax;
0120 xmin = (int)min_of(pts[0].x, pts[2].x);
0121 ymin = (int)min_of(pts[0].y, pts[2].y);
0122 xmax = (int)max_of(pts[0].x, pts[2].x);
0123 ymax = (int)max_of(pts[0].y, pts[2].y);
0124 if ((xmin != xmax) && (ymin != ymax))
0125 {
0126 for(y=ymin;y<=ymax;y++) a_proc(a_tag,xmin ,xmax ,y);
0127 }
0128 return;
0129 }
0130
0131 if(Count>m_pETEn)
0132 {
0133 cmem_free(m_pETEs);
0134 m_pETEn = Count;
0135 m_pETEs = cmem_alloc<EdgeTableEntry>(m_pETEn);
0136 if(m_pETEs==NULL)
0137 {
0138 m_pETEn = 0;
0139 return;
0140 }
0141 }
0142
0143 ET.scanlines.next = (ScanLineList*)NULL;
0144 ET.ymax = pts_ymin;
0145 ET.ymin = pts_ymax;
0146
0147 AET.next = (EdgeTableEntry*)NULL;
0148 AET.back = (EdgeTableEntry*)NULL;
0149 AET.nextWETE = (EdgeTableEntry*)NULL;
0150 AET.bres.minor_axis = pts_xmin;
0151
0152 SLLBlock.next = (ScanLineListBlock*)NULL;
0153
0154 CreateETandAET (Count,(point*)Pts, &ET, &AET, m_pETEs, &SLLBlock,pts_xmin,pts_ymin,pts_ymax);
0155
0156 pSLL = ET.scanlines.next;
0157
0158 curPtBlock = &m_FirstPtBlock;
0159 pts = m_FirstPtBlock.pts;
0160
0161
0162 if (rule==0)
0163 {
0164 /*
0165 * for each scanline
0166 */
0167 for (y = ET.ymin; y < ET.ymax; y++) {
0168 /*
0169 * Add a new edge to the active edge table when we
0170 * get to the next edge.
0171 */
0172 if (pSLL != NULL && y == pSLL->scanline)
0173 {
0174 LoadAET(&AET, pSLL->edgelist);
0175 pSLL = pSLL->next;
0176 }
0177 pPrevAET = &AET;
0178 pAET = AET.next;
0179
0180 /*
0181 * for each active edge
0182 */
0183 while (pAET) {
0184 pts->x = pAET->bres.minor_axis;
0185 pts->y = y;
0186 pts++;
0187 iPts++;
0188
0189 /*
0190 * send out the buffer
0191 */
0192 if (iPts == NUMPTSTOBUFFER)
0193 {
0194 if(numFullPtBlocks < m_numAllocPtBlocks)
0195 {
0196 curPtBlock = curPtBlock->next;
0197 }
0198 else
0199 {
0200 POINTBLOCK* tmpPtBlock = cmem_alloc<POINTBLOCK>(1);
0201 if(tmpPtBlock==NULL)
0202 {
0203 FreeStorage(SLLBlock.next);
0204 return;
0205 }
0206 tmpPtBlock->next = NULL; /*Barrand*/
0207 curPtBlock->next = tmpPtBlock;
0208 curPtBlock = tmpPtBlock;
0209 m_numAllocPtBlocks++;
0210 }
0211 numFullPtBlocks++;
0212 pts = curPtBlock->pts;
0213 iPts = 0;
0214 }
0215
0216 EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
0217 }
0218 (void) InsertAndSort(&AET);
0219 }
0220 }
0221 else
0222 {
0223 /*
0224 * for each scanline
0225 */
0226 for (y = ET.ymin; y < ET.ymax; y++) {
0227 /*
0228 * Add a new edge to the active edge table when we
0229 * get to the next edge.
0230 */
0231 if (pSLL != NULL && y == pSLL->scanline)
0232 {
0233 LoadAET(&AET, pSLL->edgelist);
0234 ComputeWAET(&AET);
0235 pSLL = pSLL->next;
0236 }
0237 pPrevAET = &AET;
0238 pAET = AET.next;
0239 pWETE = pAET;
0240
0241 /*
0242 * for each active edge
0243 */
0244 while (pAET) {
0245 /*
0246 * add to the buffer only those edges that
0247 * are in the Winding active edge table.
0248 */
0249 if (pWETE == pAET) {
0250 pts->x = pAET->bres.minor_axis;
0251 pts->y = y;
0252 pts++;
0253 iPts++;
0254
0255 /*
0256 * send out the buffer
0257 */
0258 if (iPts == NUMPTSTOBUFFER)
0259 {
0260 if(numFullPtBlocks < m_numAllocPtBlocks)
0261 {
0262 curPtBlock = curPtBlock->next;
0263 }
0264 else
0265 {
0266 POINTBLOCK* tmpPtBlock = cmem_alloc<POINTBLOCK>(1);
0267 if(tmpPtBlock==NULL)
0268 {
0269 FreeStorage(SLLBlock.next);
0270 return;
0271 }
0272 tmpPtBlock->next = NULL; /*Barrand*/
0273 curPtBlock->next = tmpPtBlock;
0274 curPtBlock = tmpPtBlock;
0275 m_numAllocPtBlocks++;
0276 }
0277 numFullPtBlocks++;
0278 pts = curPtBlock->pts;
0279 iPts = 0;
0280 }
0281 pWETE = pWETE->nextWETE;
0282 }
0283 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
0284 }
0285
0286 /*
0287 * recompute the winding active edge table if
0288 * we just resorted or have exited an edge.
0289 */
0290 if ( (InsertAndSort(&AET)!=0) || (fixWAET!=0) )
0291 {
0292 ComputeWAET(&AET);
0293 fixWAET = 0;
0294 }
0295 }
0296 }
0297 FreeStorage (SLLBlock.next);
0298
0299 ScanPoints (numFullPtBlocks, iPts, &m_FirstPtBlock,a_proc,a_tag);
0300
0301 }
0302 protected:
0303 void ScanPoints (int numFullPtBlocks,
0304 int iCurPtBlock,
0305 POINTBLOCK* FirstPtBlock,
0306 scan_func a_proc,void* a_tag) {
0307 point* pts;
0308 POINTBLOCK* CurPtBlock;
0309 int i;
0310 CurPtBlock = FirstPtBlock;
0311 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--)
0312 {
0313 /* the loop uses 2 points per iteration */
0314 i = numFullPtBlocks!=0 ? NUMPTSTOBUFFER >> 1 : iCurPtBlock >> 1 ;
0315 for (pts = CurPtBlock->pts; i--; pts += 2)
0316 {
0317 a_proc (a_tag,(int)(pts->x),(int)pts[1].x,(int)pts->y);
0318 }
0319 CurPtBlock = CurPtBlock->next;
0320 }
0321 }
0322
0323 // from: https://rosettacode.org/wiki/Determine_if_two_triangles_overlap#C++
0324 static double det_2D(const point& a_p1,const point& a_p2,const point& a_p3) {
0325 return a_p1.x*(a_p2.y-a_p3.y)+a_p2.x*(a_p3.y-a_p1.y)+a_p3.x*(a_p1.y-a_p2.y);
0326 }
0327
0328 static void check_winding(point& a_p1,point& a_p2,point& a_p3) {
0329 double detTri = det_2D(a_p1, a_p2, a_p3);
0330 if(detTri < 0.0) { //swap p2 and p3:
0331 point a = a_p3;
0332 a_p3 = a_p2;
0333 a_p2 = a;
0334 }
0335 }
0336
0337 static bool check_boundary_overlap(point& a_p1,point& a_p2,point& a_p3) {return det_2D(a_p1, a_p2, a_p3) < 0.0;}
0338
0339 static bool triangles_overlap(point* a_t1,point* a_t2) {
0340 //Trangles must be expressed anti-clockwise
0341 check_winding(a_t1[0], a_t1[1], a_t1[2]);
0342 check_winding(a_t2[0], a_t2[1], a_t2[2]);
0343
0344 //For edge E of trangle 1,
0345 for(int i=0; i<3; i++) {
0346 int j=(i+1)%3;
0347
0348 //Check all points of trangle 2 lay on the external side of the edge E. If
0349 //they do, the triangles do not overlap.
0350 if (check_boundary_overlap(a_t1[i], a_t1[j], a_t2[0]) &&
0351 check_boundary_overlap(a_t1[i], a_t1[j], a_t2[1]) &&
0352 check_boundary_overlap(a_t1[i], a_t1[j], a_t2[2])) return false;
0353 }
0354
0355 //For edge E of trangle 2,
0356 for(int i=0; i<3; i++) {
0357 int j=(i+1)%3;
0358
0359 //Check all points of trangle 1 lay on the external side of the edge E. If
0360 //they do, the triangles do not overlap.
0361 if (check_boundary_overlap(a_t2[i], a_t2[j], a_t1[0]) &&
0362 check_boundary_overlap(a_t2[i], a_t2[j], a_t1[1]) &&
0363 check_boundary_overlap(a_t2[i], a_t2[j], a_t1[2])) return false;
0364 }
0365
0366 return true; //the triangles overlap.
0367 }
0368
0369 };
0370
0371 }}
0372
0373 #endif
