18bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling/* 28bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * Copyright (C) 2011 The Android Open Source Project 38bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * 48bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * Licensed under the Apache License, Version 2.0 (the "License"); 58bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * you may not use this file except in compliance with the License. 68bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * You may obtain a copy of the License at 78bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * 88bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * http://www.apache.org/licenses/LICENSE-2.0 98bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * 108bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * Unless required by applicable law or agreed to in writing, software 118bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * distributed under the License is distributed on an "AS IS" BASIS, 128bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 138bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * See the License for the specific language governing permissions and 148bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling * limitations under the License. 158bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling */ 168bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 178bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// Delaunay.h 188bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// $Id: Delaunay.h,v 1.9 2011/06/17 13:35:48 mbansal Exp $ 198bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 208bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#ifndef DELAUNAY_H 218bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define DELAUNAY_H 228bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#include <stdio.h> 238bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#include <math.h> 248bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#include "CSite.h" 258bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#include "EdgePointerUtil.h" 268bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 278bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#ifndef TRUE 288bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define TRUE 1==1 298bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define FALSE 0==1 308bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#endif 318bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 328bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling//****************************************************************************** 338bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// Reference for Quad-edge data structure: 348bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// 358bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// Leonidas Guibas and Jorge Stolfi, "Primitives for the manipulation of general 368bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// subdivisions and the computations of Voronoi diagrams", 378bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// ACM Transactions on Graphics 4, 74-123 (1985). 388bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// 398bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling//****************************************************************************** 408bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 418bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// 428bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// Common data structures 438bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling// 448bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 458bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberlingtypedef short SitePointer; 468bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberlingtypedef short TrianglePointer; 478bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 488bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberlingclass CDelaunay 498bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling{ 508bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberlingprivate: 518bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling CSite *sa; 528bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling EdgePointer oneBndryEdge; 538bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling EdgePointer *next; 548bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling SitePointer *org; 558bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling struct EDGE_INFO *ei; 568bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling SitePointer *sp; 578bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling SEdgeVector *ev; 588bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 598bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling SitePointer sp1; 608bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling EdgePointer nextEdge; 618bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling EdgePointer availEdge; 628bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 638bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberlingprivate: 648bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void build(int lo, int hi, EdgePointer *le, EdgePointer *re, int rows); 658bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void buildTriangulation(int size); 668bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 678bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling EdgePointer allocEdge(); 688bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void freeEdge(EdgePointer e); 698bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 708bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling EdgePointer makeEdge(SitePointer origin, SitePointer destination); 718bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void deleteEdge(EdgePointer e); 728bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 738bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void splice(EdgePointer, EdgePointer); 748bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling EdgePointer consolidateEdges(); 758bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void deleteAllEdges(); 768bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 778bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void spsortx(SitePointer *, int, int); 788bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void spsorty(SitePointer *, int, int); 798bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 808bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling int cmpev(int i, int j); 818bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling int xcmpsp(int i, int j); 828bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling int ycmpsp(int i, int j); 838bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 848bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void swapsp(int i, int j); 858bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void swapev(int i, int j); 868bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 878bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void copysp(int i, int j); 888bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void copyev(int i, int j); 898bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 908bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void rcssort(int lowelt, int highelt, int temp, 918bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling int (CDelaunay::*comparison)(int,int), 928bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void (CDelaunay::*swap)(int,int), 938bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void (CDelaunay::*copy)(int,int)); 948bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 958bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void doMerge(EdgePointer *ldo, EdgePointer ldi, EdgePointer rdi, EdgePointer *rdo); 968bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling EdgePointer connectLeft(EdgePointer a, EdgePointer b); 978bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling EdgePointer connectRight(EdgePointer a, EdgePointer b); 988bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling int ccw(SitePointer a, SitePointer b, SitePointer c); 998bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling int incircle(SitePointer a, SitePointer b, SitePointer c, SitePointer d); 1008bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling int constructList(EdgePointer e, int width, int height); 1018bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 1028bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberlingpublic: 1038bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling CDelaunay(); 1048bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling ~CDelaunay(); 1058bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 1068bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling CSite *allocMemory(int nsite); 1078bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void freeMemory(); 1088bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling int triangulate(SEdgeVector **edge, int nsite, int width, int height); 1098bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling void linkNeighbors(SEdgeVector *edge, int nedge, int nsite); 1108bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling}; 1118bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 1128bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define onext(a) next[a] 1138bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define oprev(a) rot(onext(rot(a))) 1148bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define lnext(a) rot(onext(rotinv(a))) 1158bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define lprev(a) sym(onext(a)) 1168bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define rnext(a) rotinv(onext(rot(a))) 1178bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define rprev(a) onext(sym(a)) 1188bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define dnext(a) sym(onext(sym(a))) 1198bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define dprev(a) rotinv(onext(rotinv(a))) 1208bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 1218bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define orig(a) org[a] 1228bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define dest(a) orig(sym(a)) 1238bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define left(a) orig(rotinv(a)) 1248bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#define right(a) orig(rot(a)) 1258bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling 1268bddf8ce4f3dcbb56edb12cee7e93f3a9daa3f96Sascha Haeberling#endif 127