Select Git revision
DivideAndConquer.cpp
Forked from
gmsh / gmsh
Source project has a limited visibility.
DivideAndConquer.cpp 23.21 KiB
// Gmsh - Copyright (C) 1997-2010 C. Geuzaine, J.-F. Remacle
//
// See the LICENSE.txt file for license information. Please report all
// bugs and problems to <gmsh@geuz.org>.
// Triangulation using a divide and conquer algorithm
//
// The main idea is to be able to merge two Delaunay triangulations
// into a single one (see the 'Merge' function). Points are then
// separated into two groups, then each group into two, ... until
// having 1, 2 or 3 points (the triangulation is then trivial).
//
// This is used to contruct the initial mesh.
//
// Warning: point positions must be PERTURBED by a small random
// value to avoid 3 aligned points or 4 cocyclical points!
#include "GmshMessage.h"
#include "DivideAndConquer.h"
#include "Numeric.h"
#include "robustPredicates.h"
// FIXME: should not introduce dependencies to Geo/ code in Numeric
#include "GPoint.h"
#include "GFace.h"
#include "MLine.h"
#define Pred(x) ((x)->prev)
#define Succ(x) ((x)->next)
PointNumero DocRecord::Predecessor(PointNumero a, PointNumero b)
{
DListPeek p = points[a].adjacent;
if(p == NULL)
return -1;
do {
if(p->point_num == b)
return Pred(p)->point_num;
p = Pred(p);
} while(p != points[a].adjacent);
return -1;
}
PointNumero DocRecord::Successor(PointNumero a, PointNumero b)
{
DListPeek p = points[a].adjacent;
if(p == NULL)
return -1;
do {
if(p->point_num == b)
return Succ(p)->point_num;
p = Succ(p);
} while(p != points[a].adjacent);
return -1;
}
int DocRecord::FixFirst(PointNumero x, PointNumero f)
{
DListPeek p = points[x].adjacent;
if(p == NULL)
return 0;
int out = 0;
DListPeek copy = p;
do {
if(p->point_num == f) {