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
45typedef short SitePointer;
46typedef short TrianglePointer;
47
48class CDelaunay
49{
50private:
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
63private:
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
102public:
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