Graphviz: lib/ortho/partition.c File Reference

Searching...

No Matches

#include "config.h"
#include <assert.h>
#include <common/boxes.h>
#include <common/geomprocs.h>
#include <limits.h>
#include <ortho/partition.h>
#include <ortho/trap.h>
#include <math.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 dependency graph for partition.c:

Go to the source code of this file.

Data Structures
struct	monchain_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	srand48 srand

#define	newmon() (++mon_idx)

#define	new_chain_element() (++chain_idx)

Functions
typedef	LIST (monchain_t)

static monchain_t *	monchains_at (monchains_t *chain, int index)

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

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

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

static void	generateRandomOrdering (size_t n, int *permute)

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 (int v0, int v1, int ip, int iq)

static size_t	make_new_monotone_poly (monchains_t *chain, size_t mcur, int v0, int v1)

static void	traverse_polygon (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, monchains_t *chain)

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

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

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

Variables
static int	chain_idx

static size_t	mon_idx

static vertexchain_t *	vert

static int *	mon

Macro Definition Documentation

◆ CROSS_SINE

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

Definition at line 48 of file partition.c.

◆ DEBUG

#define DEBUG 0

Definition at line 30 of file partition.c.

◆ DOT

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

Definition at line 47 of file partition.c.

◆ LENGTH

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

Definition at line 49 of file partition.c.

◆ new_chain_element

#define new_chain_element ( ) (++chain_idx)

Definition at line 129 of file partition.c.

◆ newmon

#define newmon ( ) (++mon_idx)

Definition at line 127 of file partition.c.

◆ NPOINTS

#define NPOINTS 4 /* only rectangles */

Definition at line 33 of file partition.c.

◆ SP_2DN_LEFT

#define SP_2DN_LEFT 6

Definition at line 43 of file partition.c.

◆ SP_2DN_RIGHT

#define SP_2DN_RIGHT 7

Definition at line 44 of file partition.c.

◆ SP_2UP_2DN

#define SP_2UP_2DN 3

Definition at line 40 of file partition.c.

◆ SP_2UP_LEFT

#define SP_2UP_LEFT 4

Definition at line 41 of file partition.c.

◆ SP_2UP_RIGHT

#define SP_2UP_RIGHT 5

Definition at line 42 of file partition.c.

◆ SP_NOSPLIT

#define SP_NOSPLIT -1

Definition at line 45 of file partition.c.

◆ SP_SIMPLE_LRDN

#define SP_SIMPLE_LRDN 2

Definition at line 39 of file partition.c.

◆ SP_SIMPLE_LRUP

#define SP_SIMPLE_LRUP 1 /* for splitting trapezoids */

Definition at line 38 of file partition.c.

◆ srand48

#define srand48 srand

Definition at line 52 of file partition.c.

◆ TR_FROM_DN

#define TR_FROM_DN 2

Definition at line 36 of file partition.c.

◆ TR_FROM_UP

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

Definition at line 35 of file partition.c.

Function Documentation

◆ convert()

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

static

Definition at line 132 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 void generateRandomOrdering	(	size_t	n,
		int *	permute
	)

static

Definition at line 195 of file partition.c.

References drand48(), and SWAP.

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 181 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 228 of file partition.c.

References CROSS_SINE, DOT, LENGTH, pointf_s::x, and pointf_s::y.

Referenced by get_vertex_positions().

Here is the caller graph for this function:

◆ get_vertex_positions()

static void get_vertex_positions	(	int	v0,
		int	v1,
		int *	ip,
		int *	iq
	)

static

Definition at line 247 of file partition.c.

References get_angle(), vertexchain_t::pt, vert, and vertexchain_t::vnext.

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

◆ LIST()

typedef LIST ( monchain_t )

Definition at line 65 of file partition.c.

References LIST_GET, LIST_SIZE, and NULL.

◆ make_new_monotone_poly()

static size_t make_new_monotone_poly	(	monchains_t *	chain,
		size_t	mcur,
		int	v0,
		int	v1
	)

static

Definition at line 300 of file partition.c.

References get_vertex_positions(), mon, monchains_at(), new_chain_element, newmon, monchain_t::next, vertexchain_t::nextfree, prev, monchain_t::prev, PRISIZE_T, vert, vertexchain_t::vnext, monchain_t::vnum, and vertexchain_t::vpos.

Referenced by traverse_polygon().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ monchains_at()

static monchain_t * monchains_at	(	monchains_t *	chain,
		int	index
	)

static

access the value of a chain entry for writing

This function treats the chain as symbolically infinite, allowing out of bounds accesses to read zeroed data.

Parameters

chain	Chain to operate on
index	Index to lookup

Returns: Pointer to chain value at the given index

Definition at line 94 of file partition.c.

References LIST_APPEND, LIST_AT, LIST_SIZE, and NULL.

Referenced by make_new_monotone_poly(), and monotonate_trapezoids().

Here is the caller graph for this function:

◆ monotonate_trapezoids()

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

static

Definition at line 625 of file partition.c.

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

Referenced by partition().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ partition()

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

Parameters

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

Returns: array of the tiles

Definition at line 719 of file partition.c.

References construct_trapezoids(), DEBUG, free(), generateRandomOrdering(), genSegments(), gv_calloc(), LIST_APPEND, LIST_DETACH, LIST_FREE, LIST_GET, LIST_SIZE, monotonate_trapezoids(), PRISIZE_T, rectIntersect(), srand48, 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 676 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 int store	(	segment_t *	seg,
		int	first,
		pointf *	pts
	)

static

Definition at line 157 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	(	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,
		monchains_t *	chain
	)

static

recursively visit all the trapezoids

Parameters

chain Monotone polygon chain to operate on

Definition at line 361 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

int chain_idx

static

Definition at line 113 of file partition.c.

Referenced by monotonate_trapezoids().

◆ mon

int* mon

static

Definition at line 124 of file partition.c.

Referenced by make_new_monotone_poly(), and monotonate_trapezoids().

◆ mon_idx

size_t mon_idx

static

Definition at line 114 of file partition.c.

Referenced by monotonate_trapezoids().

◆ vert

vertexchain_t* vert

static

Definition at line 121 of file partition.c.

Referenced by get_vertex_positions(), make_new_monotone_poly(), and 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

◆ srand48

◆ TR_FROM_DN

◆ TR_FROM_UP

Function Documentation

◆ convert()

◆ generateRandomOrdering()

◆ genSegments()

◆ get_angle()

◆ get_vertex_positions()

◆ inside_polygon()

◆ LIST()

◆ make_new_monotone_poly()

◆ monchains_at()

◆ monotonate_trapezoids()

◆ partition()

◆ rectIntersect()

◆ store()

◆ traverse_polygon()

Variable Documentation

◆ chain_idx

◆ mon

◆ mon_idx

◆ vert