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