trap.h File Reference

trapezoid elements and utilities for partition.c More...

#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <util/list.h>

Include dependency graph for trap.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	segment_t
struct	trap_t

Macros
#define	ST_VALID   1 /* for trapezium state */
	an array of trapezoids
#define	ST_INVALID   2
#define	C_EPS   1.0e-7 /* tolerance value: Used for making */

Functions
static bool	is_valid_trap (size_t index)
static bool	fp_equal (double s, double t)
static int	dfp_cmp (double f1, double f2)
	double floating point three-way comparison
static bool	equal_to (pointf v0, pointf v1)
static bool	greater_than (pointf v0, pointf v1)
traps_t	construct_trapezoids (int, segment_t *, int *)

Detailed Description

See Fast polygon triangulation based on Seidel's algorithm

Definition in file trap.h.

Macro Definition Documentation

C_EPS

#define C_EPS   1.0e-7 /* tolerance value: Used for making */

Definition at line 66 of file trap.h.

ST_INVALID

#define ST_INVALID   2

Definition at line 64 of file trap.h.

ST_VALID

#define ST_VALID   1 /* for trapezium state */

Definition at line 63 of file trap.h.

Function Documentation

construct_trapezoids()

traps_t construct_trapezoids ( int  nseg, segment_t *  seg, int *  permute  )

extern

Definition at line 872 of file trapezoid.c.

References add_segment(), find_new_roots(), init_query_structure(), math_logstar_n(), and math_N().

Referenced by partition().

Here is the call graph for this function:

Here is the caller graph for this function:

dfp_cmp()

static int dfp_cmp ( double  f1, double  f2  )

inlinestatic

Returns -1, 0, or 1 if f1 respectively, less than, almost equal with tolerance C_EPS, or greater than f2. The purpose of the function is workaround precision issues.

Definition at line 82 of file trap.h.

References C_EPS.

Referenced by hcmpid(), and vcmpid().

Here is the caller graph for this function:

equal_to()

static bool equal_to ( pointf  v0, pointf  v1  )

inlinestatic

Definition at line 91 of file trap.h.

References fp_equal(), pointf_s::x, and pointf_s::y.

Referenced by add_segment(), greater_than_equal_to(), locate_endpoint(), and traverse_polygon().

Here is the call graph for this function:

Here is the caller graph for this function:

fp_equal()

static bool fp_equal ( double  s, double  t  )

inlinestatic

Definition at line 72 of file trap.h.

References C_EPS.

Referenced by add_segment(), equal_to(), is_left_of(), locate_endpoint(), max_(), min_(), and traverse_polygon().

Here is the caller graph for this function:

greater_than()

static bool greater_than ( pointf  v0, pointf  v1  )

inlinestatic

Definition at line 95 of file trap.h.

References C_EPS, pointf_s::x, and pointf_s::y.

Referenced by add_segment(), greater_than_equal_to(), inside_polygon(), is_left_of(), and locate_endpoint().

Here is the caller graph for this function:

is_valid_trap()

static bool is_valid_trap ( size_t  index )

inlinestatic

is the given index a reference to an existing trapezoid?

The indices stored in trap_t.{u0|u1|d0|d1|usave} can contain sentinel values that represent an unset or invalid trapezoid. This function can be used to determine the validity of these fields.

Definition at line 56 of file trap.h.

References SIZE_MAX.

Referenced by add_segment(), inside_polygon(), merge_trapezoids(), monotonate_trapezoids(), traverse_polygon(), and update_trapezoid().

Here is the caller graph for this function: