1 /* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 // Delaunay.h 18 // $Id: Delaunay.h,v 1.9 2011/06/17 13:35:48 mbansal Exp $ 19 20 #ifndef DELAUNAY_H 21 #define DELAUNAY_H 22 #include <stdio.h> 23 #include <math.h> 24 #include "CSite.h" 25 #include "EdgePointerUtil.h" 26 27 #ifndef TRUE 28 #define TRUE 1==1 29 #define FALSE 0==1 30 #endif 31 32 //****************************************************************************** 33 // Reference for Quad-edge data structure: 34 // 35 // Leonidas Guibas and Jorge Stolfi, "Primitives for the manipulation of general 36 // subdivisions and the computations of Voronoi diagrams", 37 // ACM Transactions on Graphics 4, 74-123 (1985). 38 // 39 //****************************************************************************** 40 41 // 42 // Common data structures 43 // 44 45 typedef short SitePointer; 46 typedef short TrianglePointer; 47 48 class CDelaunay 49 { 50 private: 51 CSite *sa; 52 EdgePointer oneBndryEdge; 53 EdgePointer *next; 54 SitePointer *org; 55 struct EDGE_INFO *ei; 56 SitePointer *sp; 57 SEdgeVector *ev; 58 59 SitePointer sp1; 60 EdgePointer nextEdge; 61 EdgePointer availEdge; 62 63 private: 64 void build(int lo, int hi, EdgePointer *le, EdgePointer *re, int rows); 65 void buildTriangulation(int size); 66 67 EdgePointer allocEdge(); 68 void freeEdge(EdgePointer e); 69 70 EdgePointer makeEdge(SitePointer origin, SitePointer destination); 71 void deleteEdge(EdgePointer e); 72 73 void splice(EdgePointer, EdgePointer); 74 EdgePointer consolidateEdges(); 75 void deleteAllEdges(); 76 77 void spsortx(SitePointer *, int, int); 78 void spsorty(SitePointer *, int, int); 79 80 int cmpev(int i, int j); 81 int xcmpsp(int i, int j); 82 int ycmpsp(int i, int j); 83 84 void swapsp(int i, int j); 85 void swapev(int i, int j); 86 87 void copysp(int i, int j); 88 void copyev(int i, int j); 89 90 void rcssort(int lowelt, int highelt, int temp, 91 int (CDelaunay::*comparison)(int,int), 92 void (CDelaunay::*swap)(int,int), 93 void (CDelaunay::*copy)(int,int)); 94 95 void doMerge(EdgePointer *ldo, EdgePointer ldi, EdgePointer rdi, EdgePointer *rdo); 96 EdgePointer connectLeft(EdgePointer a, EdgePointer b); 97 EdgePointer connectRight(EdgePointer a, EdgePointer b); 98 int ccw(SitePointer a, SitePointer b, SitePointer c); 99 int incircle(SitePointer a, SitePointer b, SitePointer c, SitePointer d); 100 int constructList(EdgePointer e, int width, int height); 101 102 public: 103 CDelaunay(); 104 ~CDelaunay(); 105 106 CSite *allocMemory(int nsite); 107 void freeMemory(); 108 int triangulate(SEdgeVector **edge, int nsite, int width, int height); 109 void linkNeighbors(SEdgeVector *edge, int nedge, int nsite); 110 }; 111 112 #define onext(a) next[a] 113 #define oprev(a) rot(onext(rot(a))) 114 #define lnext(a) rot(onext(rotinv(a))) 115 #define lprev(a) sym(onext(a)) 116 #define rnext(a) rotinv(onext(rot(a))) 117 #define rprev(a) onext(sym(a)) 118 #define dnext(a) sym(onext(sym(a))) 119 #define dprev(a) rotinv(onext(rotinv(a))) 120 121 #define orig(a) org[a] 122 #define dest(a) orig(sym(a)) 123 #define left(a) orig(rotinv(a)) 124 #define right(a) orig(rot(a)) 125 126 #endif 127