Graphviz: lib/ortho/trapezoid.c File Reference

Searching...

No Matches

trapezoidation More...

#include "config.h"
#include <string.h>
#include <assert.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

#define	INF 1<<30

#define	CROSS(v0, v1, v2)

Functions
static size_t	newnode (qnodes_t *qs)
	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

◆ CROSS

#define CROSS	(	v0,
		v1,
		v2
	)

Value:

(((v1).x - (v0).x)*((v2).y - (v0).y) - \

((v1).y - (v0).y)*((v2).x - (v0).x))

Definition at line 50 of file trapezoid.c.

◆ FIRSTPT

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

Definition at line 42 of file trapezoid.c.

◆ INF

#define INF 1<<30

Definition at line 48 of file trapezoid.c.

◆ LASTPT

#define LASTPT 2

Definition at line 43 of file trapezoid.c.

◆ S_LEFT

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

Definition at line 45 of file trapezoid.c.

◆ S_RIGHT

#define S_RIGHT 2

Definition at line 46 of file trapezoid.c.

◆ T_SINK

#define T_SINK 3

Definition at line 40 of file trapezoid.c.

◆ T_X

#define T_X 1

Definition at line 38 of file trapezoid.c.

◆ T_Y

#define T_Y 2

Definition at line 39 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 449 of file trapezoid.c.

References trap_t::d0, trap_t::d1, traps_t::data, equal_to(), FIRSTPT, fp_equal(), greater_than(), greater_than_equal_to(), trap_t::hi, inserted(), segment_t::is_inserted, is_left_of(), is_valid_trap(), LASTPT, less_than(), trap_t::lo, locate_endpoint(), trap_t::lseg, merge_trapezoids(), newnode(), newtrap(), segment_t::next, segment_t::prev, trap_t::rseg, S_LEFT, S_RIGHT, trap_t::sink, SIZE_MAX, ST_VALID, trap_t::state, SWAP, T_SINK, T_X, T_Y, trap_t::u0, trap_t::u1, update_trapezoid(), trap_t::usave, trap_t::uside, 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 874 of file trapezoid.c.

References add_segment(), find_new_roots(), gv_calloc(), init_query_structure(), traps_t::length, 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:

◆ find_new_roots()

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

static

Definition at line 838 of file trapezoid.c.

References traps_t::data, locate_endpoint(), and trap_t::sink.

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 102 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 123 of file trapezoid.c.

References trap_t::d0, trap_t::d1, traps_t::data, trap_t::hi, INF, trap_t::lo, trap_t::lseg, max_(), min_(), newnode(), newtrap(), trap_t::rseg, trap_t::sink, ST_VALID, trap_t::state, T_SINK, T_X, T_Y, trap_t::u0, trap_t::u1, 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:

◆ inserted()

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

static

Definition at line 259 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 214 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 106 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:

◆ locate_endpoint()

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

static

Definition at line 270 of file trapezoid.c.

References equal_to(), fp_equal(), greater_than(), is_left_of(), qnode_t::left, 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 851 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 862 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 79 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 317 of file trapezoid.c.

References trap_t::d0, trap_t::d1, traps_t::data, greater_than_equal_to(), is_valid_trap(), left, trap_t::lo, trap_t::lseg, trap_t::rseg, S_LEFT, trap_t::sink, ST_INVALID, trap_t::state, trap_t::u0, and trap_t::u1.

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 91 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:

◆ newnode()

static size_t newnode ( qnodes_t * qs )

static

Definition at line 66 of file trapezoid.c.

Referenced by add_segment(), and init_query_structure().

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 traps_t::data, gv_recalloc(), and traps_t::length.

Referenced by add_segment(), and init_query_structure().

Here is the call graph for this function:

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 377 of file trapezoid.c.

References trap_t::d0, trap_t::d1, traps_t::data, is_left_of(), is_valid_trap(), trap_t::rseg, S_LEFT, SIZE_MAX, trap_t::u0, trap_t::u1, trap_t::usave, and trap_t::uside.

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

◆ CROSS

◆ FIRSTPT

◆ INF

◆ LASTPT

◆ S_LEFT

◆ S_RIGHT

◆ T_SINK

◆ T_X

◆ T_Y

Function Documentation

◆ add_segment()

◆ construct_trapezoids()

◆ find_new_roots()

◆ greater_than_equal_to()

◆ init_query_structure()

◆ inserted()

◆ is_left_of()

◆ less_than()

◆ locate_endpoint()

◆ math_logstar_n()

◆ math_N()

◆ max_()

◆ merge_trapezoids()

◆ min_()

◆ newnode()

◆ newtrap()

◆ update_trapezoid()