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