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/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
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 (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)

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 monchain_t *	mchain

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

◆ newmon

#define newmon ( ) (++mon_idx)

Definition at line 89 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.

◆ srand48

#define srand48 srand

Definition at line 51 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 94 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 157 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 143 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 190 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 209 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 173 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	(	size_t	mcur,
		int	v0,
		int	v1
	)

static

Definition at line 260 of file partition.c.

References get_vertex_positions(), mchain, mon, new_chain_element, newmon, monchain_t::next, vertexchain_t::nextfree, 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:

◆ monotonate_trapezoids()

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

static

Definition at line 581 of file partition.c.

References bitarray_new(), bitarray_reset(), chain_idx, free(), gv_calloc(), inside_polygon(), is_valid_trap(), mchain, mon, mon_idx, 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 672 of file partition.c.

References construct_trapezoids(), DEBUG, free(), generateRandomOrdering(), genSegments(), gv_calloc(), 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 629 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 119 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
	)

static

Definition at line 318 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(), 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 71 of file partition.c.

Referenced by monotonate_trapezoids().

◆ mchain

monchain_t* mchain

static

Definition at line 76 of file partition.c.

Referenced by make_new_monotone_poly(), and monotonate_trapezoids().

◆ mon

int* mon

static

Definition at line 86 of file partition.c.

Referenced by make_new_monotone_poly(), and monotonate_trapezoids().

◆ mon_idx

size_t mon_idx

static

Definition at line 72 of file partition.c.

Referenced by monotonate_trapezoids().

◆ vert

vertexchain_t* vert

static

Definition at line 83 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()

◆ make_new_monotone_poly()

◆ monotonate_trapezoids()

◆ partition()

◆ rectIntersect()

◆ store()

◆ traverse_polygon()

Variable Documentation

◆ chain_idx

◆ mchain

◆ mon

◆ mon_idx

◆ vert