Graphviz: lib/ortho/trapezoid.c File Reference

Searching...

No Matches

trapezoidation More...

#include "config.h"
#include <string.h>
#include <assert.h>
#include <float.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <math.h>
#include <common/geom.h>
#include <common/types.h>
#include <ortho/trap.h>
#include <util/alloc.h>
#include <util/gv_math.h>
#include <util/list.h>
#include <util/unreachable.h>

Include dependency graph for trapezoid.c:

Go to the source code of this file.

Data Structures
struct	qnode_t

Macros
#define	T_X 1

#define	T_Y 2

#define	T_SINK 3

#define	FIRSTPT 1 /* checking whether pt. is inserted */

#define	LASTPT 2

#define	S_LEFT 1 /* for merge-direction */

#define	S_RIGHT 2

Functions
static double	cross (pointf v0, pointf v1, pointf v2)

typedef	LIST (qnode_t)
	an array of qnodes

static size_t	newtrap (traps_t *tr)

static pointf	max_ (pointf v0, pointf v1)
	return the maximum of the two points

static pointf	min_ (pointf v0, pointf v1)
	return the minimum of the two points

static bool	greater_than_equal_to (pointf v0, pointf v1)

static bool	less_than (pointf v0, pointf v1)

static size_t	init_query_structure (int segnum, segment_t seg, traps_t tr, qnodes_t *qs)

static bool	is_left_of (int segnum, segment_t seg, pointf v)

static bool	inserted (int segnum, segment_t *seg, int whichpt)

static size_t	locate_endpoint (pointf v, pointf vo, size_t r, segment_t seg, qnodes_t qs)

static void	merge_trapezoids (int segnum, size_t tfirst, size_t tlast, int side, traps_t tr, qnodes_t qs)

static void	update_trapezoid (segment_t s, segment_t seg, traps_t *tr, size_t t, size_t tn)

static void	add_segment (int segnum, segment_t seg, traps_t tr, qnodes_t *qs)

static void	find_new_roots (int segnum, segment_t seg, traps_t tr, qnodes_t *qs)

static int	math_logstar_n (int n)

static int	math_N (int n, int h)

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

Detailed Description

See Fast polygon triangulation based on Seidel's algorithm

Definition in file trapezoid.c.

Macro Definition Documentation

◆ FIRSTPT

#define FIRSTPT 1 /* checking whether pt. is inserted */

Definition at line 43 of file trapezoid.c.

◆ LASTPT

#define LASTPT 2

Definition at line 44 of file trapezoid.c.

◆ S_LEFT

#define S_LEFT 1 /* for merge-direction */

Definition at line 46 of file trapezoid.c.

◆ S_RIGHT

#define S_RIGHT 2

Definition at line 47 of file trapezoid.c.

◆ T_SINK

#define T_SINK 3

Definition at line 41 of file trapezoid.c.

◆ T_X

#define T_X 1

Definition at line 39 of file trapezoid.c.

◆ T_Y

#define T_Y 2

Definition at line 40 of file trapezoid.c.

Function Documentation

◆ add_segment()

static void add_segment	(	int	segnum,
		segment_t *	seg,
		traps_t *	tr,
		qnodes_t *	qs
	)

static

Definition at line 448 of file trapezoid.c.

References equal_to(), FIRSTPT, fp_equal(), greater_than(), greater_than_equal_to(), inserted(), segment_t::is_inserted, is_left_of(), is_valid_trap(), LASTPT, less_than(), LIST_AT, LIST_GET, LIST_SET, locate_endpoint(), merge_trapezoids(), newnode(), newtrap(), segment_t::next, segment_t::prev, S_LEFT, S_RIGHT, SIZE_MAX, SWAP, T_SINK, T_X, T_Y, update_trapezoid(), pointf_s::x, and pointf_s::y.

Referenced by construct_trapezoids().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ construct_trapezoids()

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

Definition at line 862 of file trapezoid.c.

References add_segment(), find_new_roots(), init_query_structure(), LIST_APPEND, LIST_FREE, 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:

◆ cross()

static double cross	(	pointf	v0,
		pointf	v1,
		pointf	v2
	)

static

Definition at line 49 of file trapezoid.c.

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

Referenced by is_left_of().

Here is the caller graph for this function:

◆ find_new_roots()

static void find_new_roots	(	int	segnum,
		segment_t *	seg,
		traps_t *	tr,
		qnodes_t *	qs
	)

static

Definition at line 830 of file trapezoid.c.

References LIST_GET, and locate_endpoint().

Referenced by construct_trapezoids().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ greater_than_equal_to()

static bool greater_than_equal_to	(	pointf	v0,
		pointf	v1
	)

static

Definition at line 101 of file trapezoid.c.

References equal_to(), and greater_than().

Referenced by add_segment(), less_than(), and merge_trapezoids().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init_query_structure()

static size_t init_query_structure	(	int	segnum,
		segment_t *	seg,
		traps_t *	tr,
		qnodes_t *	qs
	)

static

Definition at line 122 of file trapezoid.c.

References LIST_AT, LIST_GET, max_(), min_(), newnode(), newtrap(), T_SINK, T_X, and T_Y.

Referenced by construct_trapezoids().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ inserted()

static bool inserted	(	int	segnum,
		segment_t *	seg,
		int	whichpt
	)

static

Definition at line 258 of file trapezoid.c.

References FIRSTPT, segment_t::is_inserted, segment_t::next, and segment_t::prev.

Referenced by add_segment().

Here is the caller graph for this function:

◆ is_left_of()

static bool is_left_of	(	int	segnum,
		segment_t *	seg,
		pointf *	v
	)

static

Definition at line 213 of file trapezoid.c.

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

Referenced by add_segment(), locate_endpoint(), and update_trapezoid().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ less_than()

static bool less_than	(	pointf	v0,
		pointf	v1
	)

static

Definition at line 105 of file trapezoid.c.

References greater_than_equal_to().

Referenced by add_segment().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LIST()

typedef LIST ( qnode_t )

Definition at line 63 of file trapezoid.c.

References LIST_APPEND, and LIST_SIZE.

◆ locate_endpoint()

static size_t locate_endpoint	(	pointf *	v,
		pointf *	vo,
		size_t	r,
		segment_t *	seg,
		qnodes_t *	qs
	)

static

Definition at line 269 of file trapezoid.c.

References equal_to(), fp_equal(), greater_than(), is_left_of(), qnode_t::left, LIST_AT, locate_endpoint(), qnode_t::nodetype, qnode_t::right, qnode_t::segnum, T_SINK, T_X, T_Y, qnode_t::trnum, UNREACHABLE, segment_t::v0, segment_t::v1, pointf_s::x, pointf_s::y, and qnode_t::yval.

Referenced by add_segment(), find_new_roots(), and locate_endpoint().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ math_logstar_n()

static int math_logstar_n ( int n )

static

Definition at line 843 of file trapezoid.c.

Referenced by construct_trapezoids().

Here is the caller graph for this function:

◆ math_N()

static int math_N	(	int	n,
		int	h
	)

static

Definition at line 852 of file trapezoid.c.

Referenced by construct_trapezoids().

Here is the caller graph for this function:

◆ max_()

static pointf max_	(	pointf	v0,
		pointf	v1
	)

static

Definition at line 78 of file trapezoid.c.

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

Referenced by init_query_structure().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ merge_trapezoids()

static void merge_trapezoids	(	int	segnum,
		size_t	tfirst,
		size_t	tlast,
		int	side,
		traps_t *	tr,
		qnodes_t *	qs
	)

static

Definition at line 316 of file trapezoid.c.

References greater_than_equal_to(), is_valid_trap(), left, LIST_AT, LIST_GET, and S_LEFT.

Referenced by add_segment().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ min_()

static pointf min_	(	pointf	v0,
		pointf	v1
	)

static

Definition at line 90 of file trapezoid.c.

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

Referenced by init_query_structure().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ newtrap()

static size_t newtrap ( traps_t * tr )

static

Definition at line 72 of file trapezoid.c.

References LIST_APPEND, and LIST_SIZE.

Referenced by add_segment(), and init_query_structure().

Here is the caller graph for this function:

◆ update_trapezoid()

static void update_trapezoid	(	segment_t *	s,
		segment_t *	seg,
		traps_t *	tr,
		size_t	t,
		size_t	tn
	)

static

Definition at line 376 of file trapezoid.c.

References is_left_of(), is_valid_trap(), LIST_AT, LIST_GET, S_LEFT, and SIZE_MAX.

Referenced by add_segment().

Here is the call graph for this function:

Here is the caller graph for this function:

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ FIRSTPT

◆ LASTPT

◆ S_LEFT

◆ S_RIGHT

◆ T_SINK

◆ T_X

◆ T_Y

Function Documentation

◆ add_segment()

◆ construct_trapezoids()

◆ cross()

◆ find_new_roots()

◆ greater_than_equal_to()

◆ init_query_structure()

◆ inserted()

◆ is_left_of()

◆ less_than()

◆ LIST()

◆ locate_endpoint()

◆ math_logstar_n()

◆ math_N()

◆ max_()

◆ merge_trapezoids()

◆ min_()

◆ newtrap()

◆ update_trapezoid()