delaunay.cpp File Reference

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <QtGlobal>
#include "../vmisc/diagnostic.h"
#include "delaunay.h"

Include dependency graph for delaunay.cpp:

Go to the source code of this file.

Classes
struct	point2d_s
struct	face_s
struct	halfedge_s
struct	delaunay_s

Macros
#define	ON_RIGHT   1
#define	ON_SEG   0
#define	ON_LEFT   -1
#define	OUTSIDE   -1
#define	ON_CIRCLE   0
#define	INSIDE   1
#define	REAL_ZERO   0.0
#define	REAL_ONE   1.0
#define	REAL_TWO   2.0
#define	REAL_FOUR   4.0
#define	TOLERANCE   (1024.0 * 1024.0)
#define	EPSILON   (REAL_ONE / TOLERANCE)

Typedefs
typedef struct point2d_s	point2d_t
typedef struct face_s	face_t
typedef struct halfedge_s	halfedge_t
typedef struct delaunay_s	delaunay_t
typedef real	mat3_t[3][3]

Functions
QT_WARNING_PUSH void	exactinit ()
real	incircle (real *pa, real *pb, real *pc, real *pd)
static point2d_t *	point_alloc ()
static void	point_free (point2d_t *p)
static halfedge_t *	halfedge_alloc ()
static void	halfedge_free (halfedge_t *d)
void	del_free_halfedges (delaunay_t *del)
static int	cmp_points (const void *_pt0, const void *_pt1)
static int	classify_point_seg (point2d_t *s, point2d_t *e, point2d_t *pt)
static int	del_classify_point (halfedge_t *d, point2d_t *pt)
static int	in_circle (point2d_t *pt0, point2d_t *pt1, point2d_t *pt2, point2d_t *p)
static int	del_init_seg (delaunay_t *del, int start)
static int	del_init_tri (delaunay_t *del, int start)
static void	del_remove_edge (halfedge_t *d)
static halfedge_t *	del_valid_left (halfedge_t *b)
static halfedge_t *	del_valid_right (halfedge_t *b)
static halfedge_t *	del_valid_link (halfedge_t *b)
static halfedge_t *	del_get_lower_tangent (delaunay_t *left, delaunay_t *right)
static void	del_link (delaunay_t *result, delaunay_t *left, delaunay_t *right)
void	del_divide_and_conquer (delaunay_t *del, int start, int end)
static void	build_halfedge_face (delaunay_t *del, halfedge_t *d)
void	del_build_faces (delaunay_t *del)
delaunay2d_t *	delaunay2d_from (del_point2d_t *points, quint32 num_points)
void	delaunay2d_release (delaunay2d_t *del)

Macro Definition Documentation

EPSILON

#define EPSILON   (REAL_ONE / TOLERANCE)

Definition at line 67 of file delaunay.cpp.

INSIDE

#define INSIDE   1

Definition at line 45 of file delaunay.cpp.

ON_CIRCLE

#define ON_CIRCLE   0

Definition at line 44 of file delaunay.cpp.

ON_LEFT

#define ON_LEFT   -1

Definition at line 41 of file delaunay.cpp.

ON_RIGHT

#define ON_RIGHT   1

Definition at line 39 of file delaunay.cpp.

ON_SEG

#define ON_SEG   0

Definition at line 40 of file delaunay.cpp.

OUTSIDE

#define OUTSIDE   -1

Definition at line 43 of file delaunay.cpp.

REAL_FOUR

#define REAL_FOUR   4.0

Definition at line 57 of file delaunay.cpp.

REAL_ONE

#define REAL_ONE   1.0

Definition at line 55 of file delaunay.cpp.

REAL_TWO

#define REAL_TWO   2.0

Definition at line 56 of file delaunay.cpp.

REAL_ZERO

#define REAL_ZERO   0.0

Definition at line 54 of file delaunay.cpp.

TOLERANCE

#define TOLERANCE   (1024.0 * 1024.0)

Definition at line 58 of file delaunay.cpp.

Typedef Documentation

delaunay_t

typedef struct delaunay_s delaunay_t

Definition at line 36 of file delaunay.cpp.

face_t

typedef struct face_s face_t

Definition at line 36 of file delaunay.cpp.

halfedge_t

typedef struct halfedge_s halfedge_t

Definition at line 36 of file delaunay.cpp.

mat3_t

typedef real mat3_t[3][3]

Definition at line 73 of file delaunay.cpp.

point2d_t

typedef struct point2d_s point2d_t

Definition at line 36 of file delaunay.cpp.

Function Documentation

build_halfedge_face()

static void build_halfedge_face ( delaunay_t *  del, halfedge_t *  d  )

static

Definition at line 944 of file delaunay.cpp.

References halfedge_s::face, delaunay_s::faces, face_s::he, delaunay_s::num_faces, face_s::num_verts, halfedge_s::pair, and halfedge_s::prev.

Referenced by del_build_faces().

classify_point_seg()

static int classify_point_seg ( point2d_t *  s, point2d_t *  e, point2d_t *  pt  )

static

Definition at line 249 of file delaunay.cpp.

References ON_LEFT, ON_RIGHT, ON_SEG, REAL_ZERO, point2d_s::x, and point2d_s::y.

Referenced by del_classify_point(), del_get_lower_tangent(), del_init_tri(), del_valid_left(), and del_valid_right().

cmp_points()

static int cmp_points ( const void *  _pt0, const void *  _pt1  )

static

Definition at line 227 of file delaunay.cpp.

References point2d_s::x, and point2d_s::y.

Referenced by delaunay2d_from().

del_build_faces()

void del_build_faces

(

delaunay_t *

del

)

Definition at line 984 of file delaunay.cpp.

References build_halfedge_face(), delaunay_s::faces, point2d_s::he, halfedge_s::next, delaunay_s::num_faces, halfedge_s::pair, delaunay_s::points, delaunay_s::rightmost_he, and delaunay_s::start_point.

Referenced by delaunay2d_from().

del_classify_point()

static int del_classify_point ( halfedge_t *  d, point2d_t *  pt  )

static

Definition at line 272 of file delaunay.cpp.

References classify_point_seg(), halfedge_s::pair, and halfedge_s::vertex.

Referenced by del_link().

del_divide_and_conquer()

void del_divide_and_conquer	(	delaunay_t *	del,
		int	start,
		int	end
	)

Definition at line 922 of file delaunay.cpp.

References del_init_seg(), del_init_tri(), del_link(), and delaunay_s::points.

Referenced by delaunay2d_from().

del_free_halfedges()

void del_free_halfedges

(

delaunay_t *

del

)

Definition at line 179 of file delaunay.cpp.

References delaunay_s::end_point, halfedge_free(), point2d_s::he, halfedge_s::next, delaunay_s::points, and delaunay_s::start_point.

Referenced by delaunay2d_from().

del_get_lower_tangent()

static halfedge_t* del_get_lower_tangent ( delaunay_t *  left, delaunay_t *  right  )

static

Definition at line 830 of file delaunay.cpp.

References classify_point_seg(), halfedge_alloc(), delaunay_s::leftmost_he, halfedge_s::next, ON_RIGHT, halfedge_s::pair, halfedge_s::prev, delaunay_s::rightmost_he, and halfedge_s::vertex.

Referenced by del_link().

del_init_seg()

static int del_init_seg ( delaunay_t *  del, int  start  )

static

Definition at line 451 of file delaunay.cpp.

References delaunay_s::end_point, halfedge_alloc(), point2d_s::he, delaunay_s::leftmost_he, halfedge_s::next, halfedge_s::pair, delaunay_s::points, halfedge_s::prev, delaunay_s::rightmost_he, delaunay_s::start_point, and halfedge_s::vertex.

Referenced by del_divide_and_conquer().

del_init_tri()

static int del_init_tri ( delaunay_t *  del, int  start  )

static

Definition at line 490 of file delaunay.cpp.

References classify_point_seg(), delaunay_s::end_point, halfedge_alloc(), point2d_s::he, delaunay_s::leftmost_he, halfedge_s::next, ON_LEFT, halfedge_s::pair, delaunay_s::points, halfedge_s::prev, delaunay_s::rightmost_he, delaunay_s::start_point, and halfedge_s::vertex.

Referenced by del_divide_and_conquer().

del_link()

static void del_link ( delaunay_t *  result, delaunay_t *  left, delaunay_t *  right  )

static

Definition at line 877 of file delaunay.cpp.

References del_classify_point(), del_get_lower_tangent(), del_valid_link(), delaunay_s::end_point, point2d_s::he, delaunay_s::leftmost_he, halfedge_s::next, ON_LEFT, ON_RIGHT, halfedge_s::pair, delaunay_s::points, halfedge_s::prev, delaunay_s::rightmost_he, delaunay_s::start_point, and halfedge_s::vertex.

Referenced by del_divide_and_conquer().

del_remove_edge()

static void del_remove_edge ( halfedge_t *  d )

static

Definition at line 615 of file delaunay.cpp.

References halfedge_free(), point2d_s::he, halfedge_s::next, halfedge_s::pair, halfedge_s::prev, and halfedge_s::vertex.

Referenced by del_valid_left(), and del_valid_right().

del_valid_left()

static halfedge_t* del_valid_left ( halfedge_t *  b )

static

Definition at line 678 of file delaunay.cpp.

References classify_point_seg(), del_remove_edge(), in_circle(), INSIDE, halfedge_s::next, ON_CIRCLE, ON_LEFT, halfedge_s::pair, halfedge_s::prev, and halfedge_s::vertex.

Referenced by del_valid_link().

del_valid_link()

static halfedge_t* del_valid_link ( halfedge_t *  b )

static

Definition at line 770 of file delaunay.cpp.

References del_valid_left(), del_valid_right(), halfedge_alloc(), in_circle(), INSIDE, halfedge_s::next, ON_CIRCLE, halfedge_s::pair, halfedge_s::prev, and halfedge_s::vertex.

Referenced by del_link().

del_valid_right()

static halfedge_t* del_valid_right ( halfedge_t *  b )

static

Definition at line 725 of file delaunay.cpp.

References classify_point_seg(), del_remove_edge(), in_circle(), INSIDE, halfedge_s::next, ON_CIRCLE, ON_LEFT, halfedge_s::pair, halfedge_s::prev, and halfedge_s::vertex.

Referenced by del_valid_link().

delaunay2d_from()

delaunay2d_t* delaunay2d_from	(	del_point2d_t *	points,
		quint32	num_points
	)

Definition at line 1008 of file delaunay.cpp.

References cmp_points(), del_build_faces(), del_divide_and_conquer(), del_free_halfedges(), exactinit(), delaunay_s::faces, delaunay2d_t::faces, face_s::he, point2d_s::idx, delaunay_s::num_faces, delaunay2d_t::num_faces, delaunay2d_t::num_points, face_s::num_verts, halfedge_s::pair, point_alloc(), point_free(), delaunay_s::points, delaunay2d_t::points, halfedge_s::prev, halfedge_s::vertex, point2d_s::x, del_point2d_t::x, point2d_s::y, and del_point2d_t::y.

Referenced by VObjEngine::drawPath().

delaunay2d_release()

void delaunay2d_release

(

delaunay2d_t *

del

)

Definition at line 1082 of file delaunay.cpp.

References delaunay2d_t::faces, and delaunay2d_t::points.

Referenced by VObjEngine::drawPath().

exactinit()

QT_WARNING_PUSH void exactinit

(

)

Definition at line 285 of file predicates.cpp.

References ccwerrboundA, ccwerrboundB, ccwerrboundC, epsilon, iccerrboundA, iccerrboundB, iccerrboundC, isperrboundA, isperrboundB, isperrboundC, o3derrboundA, o3derrboundB, o3derrboundC, resulterrbound, and splitter.

Referenced by delaunay2d_from().

halfedge_alloc()

static halfedge_t* halfedge_alloc ( )

static

Definition at line 154 of file delaunay.cpp.

Referenced by del_get_lower_tangent(), del_init_seg(), del_init_tri(), and del_valid_link().

halfedge_free()

static void halfedge_free ( halfedge_t *  d )

static

Definition at line 168 of file delaunay.cpp.

Referenced by del_free_halfedges(), and del_remove_edge().

in_circle()

static int in_circle ( point2d_t *  pt0, point2d_t *  pt1, point2d_t *  pt2, point2d_t *  p  )

static

Definition at line 360 of file delaunay.cpp.

References EPSILON, incircle(), INSIDE, ON_CIRCLE, OUTSIDE, REAL_ONE, REAL_ZERO, point2d_s::x, and point2d_s::y.

Referenced by del_valid_left(), del_valid_link(), and del_valid_right().

incircle()

real incircle	(	real *	pa,
		real *	pb,
		real *	pc,
		real *	pd
	)

Referenced by in_circle().

point_alloc()

static point2d_t* point_alloc ( )

static

Definition at line 130 of file delaunay.cpp.

Referenced by delaunay2d_from().

point_free()

static void point_free ( point2d_t *  p )

static

Definition at line 145 of file delaunay.cpp.

Referenced by delaunay2d_from().