partition.c File Reference

#include "config.h"
#include <assert.h>
#include <common/boxes.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 46 of file partition.c.

DEBUG

#define DEBUG   0

Definition at line 28 of file partition.c.

DOT

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

Definition at line 45 of file partition.c.

LENGTH

#define LENGTH

(

v0

)

hypot((v0).x, (v0).y)

Definition at line 47 of file partition.c.

new_chain_element

#define new_chain_element

(

)

(++chain_idx)

Definition at line 90 of file partition.c.

newmon

#define newmon

(

)

(++mon_idx)

Definition at line 88 of file partition.c.

NPOINTS

#define NPOINTS   4 /* only rectangles */

Definition at line 31 of file partition.c.

SP_2DN_LEFT

#define SP_2DN_LEFT   6

Definition at line 41 of file partition.c.

SP_2DN_RIGHT

#define SP_2DN_RIGHT   7

Definition at line 42 of file partition.c.

SP_2UP_2DN

#define SP_2UP_2DN   3

Definition at line 38 of file partition.c.

SP_2UP_LEFT

#define SP_2UP_LEFT   4

Definition at line 39 of file partition.c.

SP_2UP_RIGHT

#define SP_2UP_RIGHT   5

Definition at line 40 of file partition.c.

SP_NOSPLIT

#define SP_NOSPLIT   -1

Definition at line 43 of file partition.c.

SP_SIMPLE_LRDN

#define SP_SIMPLE_LRDN   2

Definition at line 37 of file partition.c.

SP_SIMPLE_LRUP

#define SP_SIMPLE_LRUP   1 /* for splitting trapezoids */

Definition at line 36 of file partition.c.

srand48

#define srand48   srand

Definition at line 50 of file partition.c.

TR_FROM_DN

#define TR_FROM_DN   2

Definition at line 34 of file partition.c.

TR_FROM_UP

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

Definition at line 33 of file partition.c.

Function Documentation

convert()

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

static

Definition at line 93 of file partition.c.

References ccw(), boxf::LL, NPOINTS, 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 158 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 144 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 191 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 210 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 174 of file partition.c.

References trap_t::d0, trap_t::d1, greater_than(), is_valid_trap(), trap_t::lseg, trap_t::rseg, ST_INVALID, trap_t::state, 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 261 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 583 of file partition.c.

References bitarray_new(), bitarray_reset(), chain_idx, trap_t::d0, traps_t::data, free(), gv_calloc(), inside_polygon(), is_valid_trap(), traps_t::length, 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(), trap_t::u0, 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 674 of file partition.c.

References construct_trapezoids(), traps_t::data, DEBUG, free(), generateRandomOrdering(), genSegments(), gv_calloc(), traps_t::length, 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 631 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 120 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 319 of file partition.c.

References bitarray_get(), bitarray_set(), C_EPS, trap_t::d0, trap_t::d1, traps_t::data, 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 70 of file partition.c.

Referenced by monotonate_trapezoids().

mchain

monchain_t* mchain

static

Definition at line 75 of file partition.c.

Referenced by make_new_monotone_poly(), and monotonate_trapezoids().

mon

int* mon

static

Definition at line 85 of file partition.c.

Referenced by make_new_monotone_poly(), and monotonate_trapezoids().

mon_idx

size_t mon_idx

static

Definition at line 71 of file partition.c.

Referenced by monotonate_trapezoids().

vert

vertexchain_t* vert

static

Definition at line 82 of file partition.c.

Referenced by get_vertex_positions(), make_new_monotone_poly(), and monotonate_trapezoids().