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.cpp 18e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// $Id: Delaunay.cpp,v 1.10 2011/06/17 13:35:48 mbansal Exp $ 19e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 20e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#include <stdio.h> 21e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#include <stdlib.h> 22e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#include <memory.h> 23e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#include "Delaunay.h" 24e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 25e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#define QQ 9 // Optimal value as determined by testing 26e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#define DM 38 // 2^(1+DM/2) element sort capability. DM=38 for >10^6 elements 27e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#define NYL -1 28e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#define valid(l) ccw(orig(basel), dest(l), dest(basel)) 29e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 30e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 31e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta ChenCDelaunay::CDelaunay() 32e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 33e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 34e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 35e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta ChenCDelaunay::~CDelaunay() 36e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 37e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 38e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 39e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Allocate storage, construct triangulation, compute voronoi corners 40e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenint CDelaunay::triangulate(SEdgeVector **edges, int n_sites, int width, int height) 41e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 42e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer cep; 43e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 44e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen deleteAllEdges(); 45e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen buildTriangulation(n_sites); 46e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen cep = consolidateEdges(); 47e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *edges = ev; 48e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 49e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Note: construction_list will change ev 50e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return constructList(cep, width, height); 51e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 52e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 53e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// builds delaunay triangulation 54e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::buildTriangulation(int size) 55e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 56e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int i, rows; 57e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer lefte, righte; 58e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 59e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rows = (int)( 0.5 + sqrt( (double) size / log( (double) size ))); 60e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 61e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Sort the pointers by x-coordinate of site 62e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen for ( i=0 ; i < size ; i++ ) { 63e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sp[i] = (SitePointer) i; 64e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 65e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 66e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen spsortx( sp, 0, size-1 ); 67e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen build( 0, size-1, &lefte, &righte, rows ); 68e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen oneBndryEdge = lefte; 69e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 70e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 71e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Recursive Delaunay Triangulation Procedure 72e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Contains modifications for axis-switching division. 73e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::build(int lo, int hi, EdgePointer *le, EdgePointer *re, int rows) 74e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 75e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer a, b, c, ldo, rdi, ldi, rdo, maxx, minx; 76e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int split, lowrows; 77e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int low, high; 78e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen SitePointer s1, s2, s3; 79e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen low = lo; 80e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen high = hi; 81e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 82e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( low < (high-2) ) { 83e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // more than three elements; do recursion 84e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen minx = sp[low]; 85e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen maxx = sp[high]; 86e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (rows == 1) { // time to switch axis of division 87e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen spsorty( sp, low, high); 88e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rows = 65536; 89e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 90e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen lowrows = rows/2; 91e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen split = low - 1 + (int) 92e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (0.5 + ((double)(high-low+1) * ((double)lowrows / (double)rows))); 93e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen build( low, split, &ldo, &ldi, lowrows ); 94e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen build( split+1, high, &rdi, &rdo, (rows-lowrows) ); 95e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen doMerge(&ldo, ldi, rdi, &rdo); 96e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen while (orig(ldo) != minx) { 97e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ldo = rprev(ldo); 98e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 99e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen while (orig(rdo) != maxx) { 100e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rdo = (SitePointer) lprev(rdo); 101e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 102e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *le = ldo; 103e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *re = rdo; 104e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 105e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else if (low >= (high - 1)) { // two or one points 106e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen a = makeEdge(sp[low], sp[high]); 107e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *le = a; 108e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *re = (EdgePointer) sym(a); 109e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { // three points 110e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // 3 cases: triangles of 2 orientations, and 3 points on a line 111e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen a = makeEdge((s1 = sp[low]), (s2 = sp[low+1])); 112e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen b = makeEdge(s2, (s3 = sp[high])); 113e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen splice((EdgePointer) sym(a), b); 114e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (ccw(s1, s3, s2)) { 115e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen c = connectLeft(b, a); 116e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *le = (EdgePointer) sym(c); 117e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *re = c; 118e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 119e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *le = a; 120e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *re = (EdgePointer) sym(b); 121e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (ccw(s1, s2, s3)) { 122e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // not colinear 123e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen c = connectLeft(b, a); 124e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 125e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 126e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 127e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 128e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 129e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Quad-edge manipulation primitives 130e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta ChenEdgePointer CDelaunay::makeEdge(SitePointer origin, SitePointer destination) 131e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 132e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer temp, ans; 133e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen temp = allocEdge(); 134e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ans = temp; 135e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 136e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(temp) = ans; 137e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen orig(temp) = origin; 138e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(++temp) = (EdgePointer) (ans + 3); 139e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(++temp) = (EdgePointer) (ans + 2); 140e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen orig(temp) = destination; 141e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(++temp) = (EdgePointer) (ans + 1); 142e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 143e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return(ans); 144e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 145e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 146e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::splice(EdgePointer a, EdgePointer b) 147e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 148e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer alpha, beta, temp; 149e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen alpha = (EdgePointer) rot(onext(a)); 150e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen beta = (EdgePointer) rot(onext(b)); 151e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen temp = onext(alpha); 152e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(alpha) = onext(beta); 153e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(beta) = temp; 154e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen temp = onext(a); 155e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(a) = onext(b); 156e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(b) = temp; 157e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 158e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 159e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta ChenEdgePointer CDelaunay::connectLeft(EdgePointer a, EdgePointer b) 160e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 161e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer ans; 162e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ans = makeEdge(dest(a), orig(b)); 163e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen splice(ans, (EdgePointer) lnext(a)); 164e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen splice((EdgePointer) sym(ans), b); 165e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return(ans); 166e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 167e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 168e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta ChenEdgePointer CDelaunay::connectRight(EdgePointer a, EdgePointer b) 169e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 170e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer ans; 171e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ans = makeEdge(dest(a), orig(b)); 172e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen splice(ans, (EdgePointer) sym(a)); 173e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen splice((EdgePointer) sym(ans), (EdgePointer) oprev(b)); 174e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return(ans); 175e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 176e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 177e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// disconnects e from the rest of the structure and destroys it 178e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::deleteEdge(EdgePointer e) 179e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 180e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen splice(e, (EdgePointer) oprev(e)); 181e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen splice((EdgePointer) sym(e), (EdgePointer) oprev(sym(e))); 182e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen freeEdge(e); 183e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 184e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 185e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// 186e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Overall storage allocation 187e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// 188e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 189e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Quad-edge storage allocation 190e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta ChenCSite *CDelaunay::allocMemory(int n) 191e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 192e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen unsigned int size; 193e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 194e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen size = ((sizeof(CSite) + sizeof(SitePointer)) * n + 195e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (sizeof(SitePointer) + sizeof(EdgePointer)) * 12 196e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ) * n; 197e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (!(sa = (CSite*) malloc(size))) { 198e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return NULL; 199e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 200e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sp = (SitePointer *) (sa + n); 201e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ev = (SEdgeVector *) (org = sp + n); 202e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen next = (EdgePointer *) (org + 12 * n); 203e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ei = (struct EDGE_INFO *) (next + 12 * n); 204e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return sa; 205e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 206e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 207e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::freeMemory() 208e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 209e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (sa) { 210e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen free(sa); 211e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sa = (CSite*)NULL; 212e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 213e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 214e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 215e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// 216e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Edge storage management 217e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// 218e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 219e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::deleteAllEdges() 220e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 221e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen nextEdge = 0; 222e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen availEdge = NYL; 223e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 224e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 225e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta ChenEdgePointer CDelaunay::allocEdge() 226e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 227e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer ans; 228e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 229e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (availEdge == NYL) { 230e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ans = nextEdge, nextEdge += 4; 231e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 232e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ans = availEdge, availEdge = onext(availEdge); 233e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 234e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return(ans); 235e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 236e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 237e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::freeEdge(EdgePointer e) 238e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 239e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen e ^= e & 3; 240e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(e) = availEdge; 241e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen availEdge = e; 242e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 243e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 244e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta ChenEdgePointer CDelaunay::consolidateEdges() 245e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 246e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer e; 247e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int i,j; 248e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 249e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen while (availEdge != NYL) { 250e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen nextEdge -= 4; e = availEdge; availEdge = onext(availEdge); 251e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 252e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (e==nextEdge) { 253e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen continue; // the one deleted was the last one anyway 254e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 255e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ((oneBndryEdge&~3) == nextEdge) { 256e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen oneBndryEdge = (EdgePointer) (e | (oneBndryEdge&3)); 257e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 258e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen for (i=0,j=3; i<4; i++,j=rot(j)) { 259e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(e+i) = onext(nextEdge+i); 260e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen onext(rot(onext(e+i))) = (EdgePointer) (e+j); 261e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 262e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 263e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return nextEdge; 264e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 265e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 266e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// 267e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Sorting Routines 268e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// 269e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 270e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenint CDelaunay::xcmpsp(int i, int j) 271e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 272e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double d = sa[(i>=0)?sp[i]:sp1].X() - sa[(j>=0)?sp[j]:sp1].X(); 273e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( d > 0. ) { 274e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return 1; 275e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 276e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( d < 0. ) { 277e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return -1; 278e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 279e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen d = sa[(i>=0)?sp[i]:sp1].Y() - sa[(j>=0)?sp[j]:sp1].Y(); 280e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( d > 0. ) { 281e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return 1; 282e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 283e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( d < 0. ) { 284e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return -1; 285e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 286e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return 0; 287e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 288e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 289e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenint CDelaunay::ycmpsp(int i, int j) 290e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 291e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double d = sa[(i>=0)?sp[i]:sp1].Y() - sa[(j>=0)?sp[j]:sp1].Y(); 292e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( d > 0. ) { 293e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return 1; 294e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 295e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( d < 0. ) { 296e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return -1; 297e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 298e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen d = sa[(i>=0)?sp[i]:sp1].X() - sa[(j>=0)?sp[j]:sp1].X(); 299e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( d > 0. ) { 300e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return 1; 301e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 302e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( d < 0. ) { 303e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return -1; 304e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 305e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return 0; 306e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 307e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 308e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenint CDelaunay::cmpev(int i, int j) 309e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 310e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return (ev[i].first - ev[j].first); 311e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 312e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 313e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::swapsp(int i, int j) 314e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 315e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int t; 316e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen t = (i>=0) ? sp[i] : sp1; 317e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 318e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (i>=0) { 319e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sp[i] = (j>=0)?sp[j]:sp1; 320e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 321e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sp1 = (j>=0)?sp[j]:sp1; 322e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 323e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 324e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (j>=0) { 325e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sp[j] = (SitePointer) t; 326e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 327e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sp1 = (SitePointer) t; 328e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 329e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 330e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 331e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::swapev(int i, int j) 332e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 333e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen SEdgeVector temp; 334e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 335e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen temp = ev[i]; 336e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ev[i] = ev[j]; 337e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ev[j] = temp; 338e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 339e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 340e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::copysp(int i, int j) 341e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 342e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (j>=0) { 343e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sp[j] = (i>=0)?sp[i]:sp1; 344e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 345e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sp1 = (i>=0)?sp[i]:sp1; 346e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 347e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 348e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 349e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::copyev(int i, int j) 350e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 351e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ev[j] = ev[i]; 352e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 353e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 354e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::spsortx(SitePointer *sp_in, int low, int high) 355e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 356e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sp = sp_in; 357e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rcssort(low,high,-1,&CDelaunay::xcmpsp,&CDelaunay::swapsp,&CDelaunay::copysp); 358e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 359e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 360e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::spsorty(SitePointer *sp_in, int low, int high ) 361e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 362e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sp = sp_in; 363e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rcssort(low,high,-1,&CDelaunay::ycmpsp,&CDelaunay::swapsp,&CDelaunay::copysp); 364e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 365e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 366e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::rcssort(int lowelt, int highelt, int temp, 367e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int (CDelaunay::*comparison)(int,int), 368e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen void (CDelaunay::*swap)(int,int), 369e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen void (CDelaunay::*copy)(int,int)) 370e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 371e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int m,sij,si,sj,sL,sk; 372e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int stack[DM]; 373e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 374e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (highelt-lowelt<=1) { 375e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return; 376e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 377e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (highelt-lowelt>QQ) { 378e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen m = 0; 379e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen si = lowelt; sj = highelt; 380e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen for (;;) { // partition [si,sj] about median-of-3. 381e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sij = (sj+si) >> 1; 382e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 383e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Now to sort elements si,sij,sj into order & set temp=their median 384e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( (this->*comparison)( si,sij ) > 0 ) { 385e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (this->*swap)( si,sij ); 386e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 387e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( (this->*comparison)( sij,sj ) > 0 ) { 388e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (this->*swap)( sj,sij ); 389e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( (this->*comparison)( si,sij ) > 0 ) { 390e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (this->*swap)( si,sij ); 391e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 392e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 393e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (this->*copy)( sij,temp ); 394e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 395e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Now to partition into elements <=temp, >=temp, and ==temp. 396e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sk = si; sL = sj; 397e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen do { 398e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen do { 399e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sL--; 400e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } while( (this->*comparison)( sL,temp ) > 0 ); 401e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen do { 402e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sk++; 403e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } while( (this->*comparison)( temp,sk ) > 0 ); 404e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( sk < sL ) { 405e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (this->*swap)( sL,sk ); 406e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 407e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } while(sk <= sL); 408e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 409e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Now to recurse on shorter partition, store longer partition on stack 410e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( sL-si > sj-sk ) { 411e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( sL-si < QQ ) { 412e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if( m==0 ) { 413e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen break; // empty stack && both partitions < QQ so break 414e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 415e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sj = stack[--m]; 416e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen si = stack[--m]; 417e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 418e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 419e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else { 420e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( sj-sk < QQ ) { 421e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sj = sL; 422e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 423e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen stack[m++] = si; 424e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen stack[m++] = sL; 425e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen si = sk; 426e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 427e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 428e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 429e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else { 430e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( sj-sk < QQ ) { 431e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( m==0 ) { 432e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen break; // empty stack && both partitions < QQ so break 433e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 434e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sj = stack[--m]; 435e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen si = stack[--m]; 436e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 437e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 438e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen else { 439e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( sL-si < QQ ) { 440e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen si = sk; 441e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 442e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen stack[m++] = sk; 443e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen stack[m++] = sj; 444e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sj = sL; 445e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 446e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 447e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 448e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 449e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 450e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 451e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Now for 0 or Data bounded "straight insertion" sort of [0,nels-1]; if it is 452e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // known that el[-1] = -INF, then can omit the "sk>=0" test and save time. 453e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen for (si=lowelt; si<highelt; si++) { 454e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( (this->*comparison)( si,si+1 ) > 0 ) { 455e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (this->*copy)( si+1,temp ); 456e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sj = sk = si; 457e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sj++; 458e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen do { 459e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (this->*copy)( sk,sj ); 460e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sj = sk; 461e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sk--; 462e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } while ( (this->*comparison)( sk,temp ) > 0 && sk>=lowelt ); 463e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (this->*copy)( temp,sj ); 464e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 465e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 466e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 467e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 468e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// 469e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Geometric primitives 470e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// 471e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 472e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// incircle, as in the Guibas-Stolfi paper. 473e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenint CDelaunay::incircle(SitePointer a, SitePointer b, SitePointer c, SitePointer d) 474e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 475e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double adx, ady, bdx, bdy, cdx, cdy, dx, dy, nad, nbd, ncd; 476e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen dx = sa[d].X(); 477e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen dy = sa[d].Y(); 478e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen adx = sa[a].X() - dx; 479e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ady = sa[a].Y() - dy; 480e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen bdx = sa[b].X() - dx; 481e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen bdy = sa[b].Y() - dy; 482e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen cdx = sa[c].X() - dx; 483e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen cdy = sa[c].Y() - dy; 484e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen nad = adx*adx+ady*ady; 485e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen nbd = bdx*bdx+bdy*bdy; 486e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ncd = cdx*cdx+cdy*cdy; 487e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return( (0.0 < (nad * (bdx * cdy - bdy * cdx) 488e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen + nbd * (cdx * ady - cdy * adx) 489e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen + ncd * (adx * bdy - ady * bdx))) ? TRUE : FALSE ); 490e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 491e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 492e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// TRUE iff A, B, C form a counterclockwise oriented triangle 493e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenint CDelaunay::ccw(SitePointer a, SitePointer b, SitePointer c) 494e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 495e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int result; 496e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 497e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double ax = sa[a].X(); 498e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double bx = sa[b].X(); 499e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double cx = sa[c].X(); 500e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double ay = sa[a].Y(); 501e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double by = sa[b].Y(); 502e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double cy = sa[c].Y(); 503e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 504e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen double val = (ax - cx)*(by - cy) - (bx - cx)*(ay - cy); 505e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ( val > 0.0) { 506e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return true; 507e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 508e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 509e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return false; 510e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 511e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 512e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// 513e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// The Merge Procedure. 514e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// 515e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 516e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::doMerge(EdgePointer *ldo, EdgePointer ldi, EdgePointer rdi, EdgePointer *rdo) 517e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 518e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int rvalid, lvalid; 519e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer basel,lcand,rcand,t; 520e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 521e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen for (;;) { 522e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen while (ccw(orig(ldi), dest(ldi), orig(rdi))) { 523e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen ldi = (EdgePointer) lnext(ldi); 524e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 525e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (ccw(dest(rdi), orig(rdi), orig(ldi))) { 526e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rdi = (EdgePointer)rprev(rdi); 527e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 528e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen break; 529e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 530e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 531e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 532e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen basel = connectLeft((EdgePointer) sym(rdi), ldi); 533e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen lcand = rprev(basel); 534e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rcand = (EdgePointer) oprev(basel); 535e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (orig(basel) == orig(*rdo)) { 536e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *rdo = basel; 537e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 538e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (dest(basel) == orig(*ldo)) { 539e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *ldo = (EdgePointer) sym(basel); 540e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 541e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 542e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen for (;;) { 543e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#if 1 544e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (valid(t=onext(lcand))) { 545e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#else 546e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen t = (EdgePointer)onext(lcand); 547e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (valid(basel, t)) { 548e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#endif 549e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen while (incircle(dest(lcand), dest(t), orig(lcand), orig(basel))) { 550e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen deleteEdge(lcand); 551e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen lcand = t; 552e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen t = onext(lcand); 553e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 554e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 555e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#if 1 556e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (valid(t=(EdgePointer)oprev(rcand))) { 557e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#else 558e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen t = (EdgePointer)oprev(rcand); 559e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (valid(basel, t)) { 560e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#endif 561e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen while (incircle(dest(t), dest(rcand), orig(rcand), dest(basel))) { 562e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen deleteEdge(rcand); 563e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rcand = t; 564e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen t = (EdgePointer)oprev(rcand); 565e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 566e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 567e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 568e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#if 1 569e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen lvalid = valid(lcand); 570e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rvalid = valid(rcand); 571e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#else 572e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen lvalid = valid(basel, lcand); 573e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rvalid = valid(basel, rcand); 574e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen#endif 575e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ((! lvalid) && (! rvalid)) { 576e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return; 577e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 578e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 579e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if (!lvalid || 580e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (rvalid && incircle(dest(lcand), orig(lcand), orig(rcand), dest(rcand)))) { 581e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen basel = connectLeft(rcand, (EdgePointer) sym(basel)); 582e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rcand = (EdgePointer) lnext(sym(basel)); 583e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 584e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen basel = (EdgePointer) sym(connectRight(lcand, basel)); 585e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen lcand = rprev(basel); 586e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 587e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 588e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 589e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 590e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenint CDelaunay::constructList(EdgePointer last, int width, int height) 591e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 592e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int c, i; 593e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen EdgePointer curr, src, nex; 594e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen SEdgeVector *currv, *prevv; 595e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 596e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen c = (int) ((curr = (EdgePointer) ((last & ~3))) >> 1); 597e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 598e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen for (last -= 4; last >= 0; last -= 4) { 599e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen src = orig(last); 600e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen nex = dest(last); 601e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen orig(--curr) = src; 602e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen orig(--curr) = nex; 603e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen orig(--curr) = nex; 604e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen orig(--curr) = src; 605e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 606e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen rcssort(0, c - 1, -1, &CDelaunay::cmpev, &CDelaunay::swapev, &CDelaunay::copyev); 607e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 608e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen // Throw out any edges that are too far apart 609e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen currv = prevv = ev; 610e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen for (i = c; i--; currv++) { 611e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen if ((int) fabs(sa[currv->first].getVCenter().x - sa[currv->second].getVCenter().x) <= width && 612e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen (int) fabs(sa[currv->first].getVCenter().y - sa[currv->second].getVCenter().y) <= height) { 613e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen *(prevv++) = *currv; 614e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } else { 615e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen c--; 616e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 617e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 618e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen return c; 619e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 620e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 621e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen// Fill in site neighbor information 622e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chenvoid CDelaunay::linkNeighbors(SEdgeVector *edge, int nedge, int nsite) 623e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen{ 624e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen int i; 625e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen 626e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen for (i = 0; i < nsite; i++) { 627e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sa[i].setNeighbor(edge); 628e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sa[i].setNumNeighbors(0); 629e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen for (; edge->first == i && nedge; edge++, nedge--) { 630e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen sa[i].incrNumNeighbors(); 631e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 632e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen } 633e295e32b68cf04f0d99138bf4a6d25555f3aef99Wei-Ta Chen} 634