Graphviz: lib/ortho/partition.c File Reference

Searching...

No Matches

#include "config.h"
#include <common/boxes.h>
#include <common/geomprocs.h>
#include <math.h>
#include <ortho/partition.h>
#include <ortho/trap.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <util/alloc.h>
#include <util/bitarray.h>
#include <util/gv_math.h>
#include <util/list.h>
#include <util/prisize_t.h>
#include <util/random.h>

Include dependency graph for partition.c:

Go to the source code of this file.

Data Structures
struct	monchain_t

struct	vertex_t

struct	vertexchain_t

Macros
#define	DEBUG 0

#define	NPOINTS 4 /* only rectangles */

#define	TR_FROM_UP 1 /* for traverse-direction */

#define	TR_FROM_DN 2

#define	SP_SIMPLE_LRUP 1 /* for splitting trapezoids */

#define	SP_SIMPLE_LRDN 2

#define	SP_2UP_2DN 3

#define	SP_2UP_LEFT 4

#define	SP_2UP_RIGHT 5

#define	SP_2DN_LEFT 6

#define	SP_2DN_RIGHT 7

#define	SP_NOSPLIT -1

#define	DOT(v0, v1) ((v0).x * (v1).x + (v0).y * (v1).y)

#define	CROSS_SINE(v0, v1) ((v0).x * (v1).y - (v1).x * (v0).y)

#define	LENGTH(v0) hypot((v0).x, (v0).y)

#define	newmon() (++mon_idx)

#define	new_chain_element() (++chain_idx)

Functions
static void	convert (boxf bb, int flip, int ccw, pointf *pts)

static size_t	store (segment_t seg, size_t first, pointf pts)

static void	genSegments (cell cells, size_t ncells, boxf bb, segment_t seg, int flip)

static size_t *	generateRandomOrdering (size_t n)

static bool	inside_polygon (trap_t t, segment_t seg)

static double	get_angle (pointf vp0, pointf vpnext, pointf vp1)

static void	get_vertex_positions (const vertexchain_t vert, size_t v0, size_t v1, size_t ip, size_t *iq)

static size_t	make_new_monotone_poly (vertexchain_t vert, monchain_t chain, size_t mcur, size_t v0, size_t v1)

static void	traverse_polygon (vertexchain_t vert, bitarray_t visited, boxes_t decomp, segment_t seg, traps_t tr, size_t mcur, size_t trnum, size_t from, int flip, int dir, monchain_t chain)

static void	monotonate_trapezoids (size_t nsegs, segment_t seg, traps_t tr, int flip, boxes_t *decomp)

static bool	rectIntersect (boxf *d, const boxf r0, const boxf r1)

boxes_t	partition (cell *cells, size_t ncells, boxf bb)
	partitions space around cells (nodes) into rectangular tiles

Variables
static size_t	chain_idx

static size_t	mon_idx

static size_t *	mon

Macro Definition Documentation

◆ CROSS_SINE

#define CROSS_SINE	(	v0,
		v1
	)	((v0).x * (v1).y - (v1).x * (v0).y)

Definition at line 47 of file partition.c.

◆ DEBUG

#define DEBUG 0

Definition at line 29 of file partition.c.

◆ DOT

#define DOT	(	v0,
		v1
	)	((v0).x * (v1).x + (v0).y * (v1).y)

Definition at line 46 of file partition.c.

◆ LENGTH

#define LENGTH ( v0 ) hypot((v0).x, (v0).y)

Definition at line 48 of file partition.c.

◆ new_chain_element

#define new_chain_element ( ) (++chain_idx)

Definition at line 76 of file partition.c.

◆ newmon

#define newmon ( ) (++mon_idx)

Definition at line 74 of file partition.c.

◆ NPOINTS

#define NPOINTS 4 /* only rectangles */

Definition at line 32 of file partition.c.

◆ SP_2DN_LEFT

#define SP_2DN_LEFT 6

Definition at line 42 of file partition.c.

◆ SP_2DN_RIGHT

#define SP_2DN_RIGHT 7

Definition at line 43 of file partition.c.

◆ SP_2UP_2DN

#define SP_2UP_2DN 3

Definition at line 39 of file partition.c.

◆ SP_2UP_LEFT

#define SP_2UP_LEFT 4

Definition at line 40 of file partition.c.

◆ SP_2UP_RIGHT

#define SP_2UP_RIGHT 5

Definition at line 41 of file partition.c.

◆ SP_NOSPLIT

#define SP_NOSPLIT -1

Definition at line 44 of file partition.c.

◆ SP_SIMPLE_LRDN

#define SP_SIMPLE_LRDN 2

Definition at line 38 of file partition.c.

◆ SP_SIMPLE_LRUP

#define SP_SIMPLE_LRUP 1 /* for splitting trapezoids */

Definition at line 37 of file partition.c.

◆ TR_FROM_DN

#define TR_FROM_DN 2

Definition at line 35 of file partition.c.

◆ TR_FROM_UP

#define TR_FROM_UP 1 /* for traverse-direction */

Definition at line 34 of file partition.c.

Function Documentation

◆ convert()

static void convert	(	boxf	bb,
		int	flip,
		int	ccw,
		pointf *	pts
	)

static

Definition at line 78 of file partition.c.

References ccw(), boxf::LL, NPOINTS, perp(), boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by genSegments().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ generateRandomOrdering()

static size_t * generateRandomOrdering ( size_t n )

static

Definition at line 134 of file partition.c.

References gv_permutation().

Referenced by partition().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ genSegments()

static void genSegments	(	cell *	cells,
		size_t	ncells,
		boxf	bb,
		segment_t *	seg,
		int	flip
	)

static

Definition at line 120 of file partition.c.

References convert(), and store().

Referenced by partition().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_angle()

static double get_angle	(	pointf	vp0,
		pointf	vpnext,
		pointf	vp1
	)

static

Definition at line 162 of file partition.c.

References CROSS_SINE, DOT, LENGTH, and sub_pointf().

Referenced by get_vertex_positions().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_vertex_positions()

static void get_vertex_positions	(	const vertexchain_t *	vert,
		size_t	v0,
		size_t	v1,
		size_t *	ip,
		size_t *	iq
	)

static

(v0, v1) is the new diagonal to be added to the polygon. Find which chain to use and return the positions of v0 and v1 in p and q

Parameters

vert	Chain initial information

Definition at line 175 of file partition.c.

References get_angle(), LIST_GET, LIST_SIZE, and vertexchain_t::pt.

Referenced by make_new_monotone_poly().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ inside_polygon()

static bool inside_polygon	(	trap_t *	t,
		segment_t *	seg
	)

static

Definition at line 146 of file partition.c.

References trap_t::d0, trap_t::d1, greater_than(), trap_t::is_valid, is_valid_trap(), trap_t::lseg, trap_t::rseg, trap_t::u0, and trap_t::u1.

Referenced by monotonate_trapezoids().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ make_new_monotone_poly()

static size_t make_new_monotone_poly	(	vertexchain_t *	vert,
		monchain_t *	chain,
		size_t	mcur,
		size_t	v0,
		size_t	v1
	)

static

Definition at line 220 of file partition.c.

References get_vertex_positions(), LIST_APPEND, LIST_AT, LIST_GET, LIST_IS_EMPTY, mon, new_chain_element, newmon, monchain_t::next, monchain_t::prev, PRISIZE_T, and monchain_t::vnum.

Referenced by traverse_polygon().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ monotonate_trapezoids()

static void monotonate_trapezoids	(	size_t	nsegs,
		segment_t *	seg,
		traps_t *	tr,
		int	flip,
		boxes_t *	decomp
	)

static

Definition at line 587 of file partition.c.

References bitarray_new(), bitarray_reset(), chain_idx, free(), gv_calloc(), inside_polygon(), is_valid_trap(), LIST_APPEND, LIST_AT, LIST_FREE, LIST_GET, LIST_SIZE, mon, mon_idx, monchain_t::next, segment_t::next, monchain_t::prev, segment_t::prev, vertexchain_t::pt, TR_FROM_DN, TR_FROM_UP, traverse_polygon(), segment_t::v0, and monchain_t::vnum.

Referenced by partition().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ partition()

boxes_t partition	(	cell *	cells,
		size_t	ncells,
		boxf	bb
	)

Parameters

[in]	cells	rectangular borders of user's input graph's nodes
[in]	bb	range of the space to partition

Returns: array of the tiles

Definition at line 657 of file partition.c.

References construct_trapezoids(), DEBUG, free(), generateRandomOrdering(), genSegments(), gv_calloc(), LIST_APPEND, LIST_FREE, LIST_GET, LIST_SIZE, monotonate_trapezoids(), PRISIZE_T, rectIntersect(), segment_t::v0, and pointf_s::y.

Referenced by mkMaze().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rectIntersect()

static bool rectIntersect	(	boxf *	d,
		const boxf	r0,
		const boxf	r1
	)

static

Definition at line 645 of file partition.c.

References boxf::LL, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by partition().

Here is the caller graph for this function:

◆ store()

static size_t store	(	segment_t *	seg,
		size_t	first,
		pointf *	pts
	)

static

Definition at line 100 of file partition.c.

References segment_t::is_inserted, last, segment_t::next, NPOINTS, segment_t::prev, segment_t::v0, and segment_t::v1.

Referenced by genSegments(), update_tree(), and update_tree_store().

Here is the caller graph for this function:

◆ traverse_polygon()

static void traverse_polygon	(	vertexchain_t *	vert,
		bitarray_t *	visited,
		boxes_t *	decomp,
		segment_t *	seg,
		traps_t *	tr,
		size_t	mcur,
		size_t	trnum,
		size_t	from,
		int	flip,
		int	dir,
		monchain_t *	chain
	)

static

recursively visit all the trapezoids

Parameters

vert	Chain initial information
chain	Monotone polygon chain to operate on

Definition at line 285 of file partition.c.

References bitarray_get(), bitarray_set(), C_EPS, trap_t::d0, trap_t::d1, equal_to(), fp_equal(), trap_t::hi, is_valid_trap(), LIST_APPEND, LIST_AT, LIST_GET, boxf::LL, trap_t::lo, trap_t::lseg, make_new_monotone_poly(), segment_t::next, trap_t::rseg, TR_FROM_DN, TR_FROM_UP, traverse_polygon(), trap_t::u0, trap_t::u1, boxf::UR, segment_t::v0, segment_t::v1, pointf_s::x, and pointf_s::y.

Referenced by monotonate_trapezoids(), and traverse_polygon().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

◆ chain_idx

size_t chain_idx

static

Definition at line 67 of file partition.c.

Referenced by monotonate_trapezoids().

◆ mon

size_t* mon

static

Definition at line 71 of file partition.c.

Referenced by make_new_monotone_poly(), and monotonate_trapezoids().

◆ mon_idx

size_t mon_idx

static

Definition at line 68 of file partition.c.

Referenced by monotonate_trapezoids().

Data Structures

Macros

Functions

Variables

Macro Definition Documentation

◆ CROSS_SINE

◆ DEBUG

◆ DOT

◆ LENGTH

◆ new_chain_element

◆ newmon

◆ NPOINTS

◆ SP_2DN_LEFT

◆ SP_2DN_RIGHT

◆ SP_2UP_2DN

◆ SP_2UP_LEFT

◆ SP_2UP_RIGHT

◆ SP_NOSPLIT

◆ SP_SIMPLE_LRDN

◆ SP_SIMPLE_LRUP

◆ TR_FROM_DN

◆ TR_FROM_UP

Function Documentation

◆ convert()

◆ generateRandomOrdering()

◆ genSegments()

◆ get_angle()

◆ get_vertex_positions()

◆ inside_polygon()

◆ make_new_monotone_poly()

◆ monotonate_trapezoids()

◆ partition()

◆ rectIntersect()

◆ store()

◆ traverse_polygon()

Variable Documentation

◆ chain_idx

◆ mon

◆ mon_idx