Graphviz: lib/common/routespl.c File Reference

Searching...

No Matches

#include "config.h"
#include <assert.h>
#include <common/geomprocs.h>
#include <common/render.h>
#include <float.h>
#include <limits.h>
#include <math.h>
#include <pathplan/pathplan.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/debug.h>
#include <util/gv_math.h>
#include <util/list.h>
#include <util/prisize_t.h>

Include dependency graph for routespl.c:

Go to the source code of this file.

Macros
#define	FUDGE .0001

#define	INIT_DELTA 10

#define	LOOP_TRIES

Functions
static int	checkpath (size_t, boxf , path )

static void	printpath (path *pp)

pointf *	simpleSplineRoute (pointf tp, pointf hp, Ppoly_t poly, size_t *n_spl_pts, int polyline)
	Given a simple (ccw) polygon, route an edge from tp to hp.

int	routesplinesinit (void)

void	routesplinesterm (void)

static void	limitBoxes (boxf boxes, size_t boxn, const pointf pps, size_t pn, double delta)

static pointf *	routesplines_ (path pp, size_t npoints, int polyline)

pointf *	routesplines (path pp, size_t npoints)

pointf *	routepolylines (path pp, size_t npoints)

static double	overlap (double i0, double i1, double j0, double j1)

static pointf	get_centroid (Agraph_t *g)

typedef	LIST (node_t *)

typedef	LIST (nodes_t *)

static bool	is_cycle_unique (cycles_t cycles, nodes_t cycle)

static void	dfs (graph_t g, node_t search, nodes_t visited, node_t end, cycles_t *cycles)

static cycles_t	find_all_cycles (graph_t *g)

static nodes_t *	find_shortest_cycle_with_edge (cycles_t cycles, edge_t edge, size_t min_size)

static pointf	get_cycle_centroid (graph_t g, edge_t edge)

static void	bend (pointf spl[4], pointf centroid)

void	makeStraightEdge (graph_t g, edge_t e, int et, splineInfo *sinfo)

void	makeStraightEdges (graph_t g, edge_t edge_list, size_t e_cnt, int et, splineInfo sinfo)

Variables
static int	nedges
	total no. of edges used in routing

static size_t	nboxes
	total no. of boxes used in routing

static int	routeinit

Macro Definition Documentation

◆ FUDGE

#define FUDGE .0001

◆ INIT_DELTA

#define INIT_DELTA 10

Definition at line 270 of file routespl.c.

◆ LOOP_TRIES

#define LOOP_TRIES

Value:

15 /* number of times to try to limiting boxes to regain space, using \

smaller divisions */

Definition at line 271 of file routespl.c.

Function Documentation

◆ bend()

static void bend	(	pointf	spl[4],
		pointf	centroid
	)

static

Definition at line 935 of file routespl.c.

References dist(), DIST, is_exactly_equal(), is_exactly_zero(), mid_pointf(), pointf_s::x, and pointf_s::y.

Here is the call graph for this function:

◆ checkpath()

static int checkpath	(	size_t	boxn,
		boxf *	boxes,
		path *	thepath
	)

static

Definition at line 630 of file routespl.c.

References agerrorf(), path::end, boxf::LL, overlap(), port::p, printpath(), PRISIZE_T, path::start, boxf::UR, Verbose, pointf_s::x, and pointf_s::y.

Here is the call graph for this function:

◆ dfs()

static void dfs	(	graph_t *	g,
		node_t *	search,
		nodes_t *	visited,
		node_t *	end,
		cycles_t *	cycles
	)

static

Definition at line 839 of file routespl.c.

References agfstout(), aghead, agnxtout(), dfs(), gv_alloc(), is_cycle_unique(), LIST_APPEND, LIST_CONTAINS, LIST_COPY, LIST_DROP_BACK, and LIST_IS_EMPTY.

Referenced by dfs(), and find_all_cycles().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_all_cycles()

static cycles_t find_all_cycles ( graph_t * g )

static

Definition at line 865 of file routespl.c.

References agfstnode(), agnxtnode(), dfs(), gv_alloc(), LIST_APPEND, and LIST_FREE.

Referenced by get_cycle_centroid().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_shortest_cycle_with_edge()

static nodes_t * find_shortest_cycle_with_edge	(	cycles_t *	cycles,
		edge_t *	edge,
		size_t	min_size
	)

static

Definition at line 887 of file routespl.c.

References edge, LIST_GET, LIST_SIZE, and NULL.

Referenced by get_cycle_centroid().

Here is the caller graph for this function:

◆ get_centroid()

static pointf get_centroid ( Agraph_t * g )

static

Definition at line 775 of file routespl.c.

References GD_bb, pointf_s::x, and pointf_s::y.

Referenced by get_cycle_centroid().

Here is the caller graph for this function:

◆ get_cycle_centroid()

static pointf get_cycle_centroid	(	graph_t *	g,
		edge_t *	edge
	)

static

Definition at line 907 of file routespl.c.

References cnt(), edge, find_all_cycles(), find_shortest_cycle_with_edge(), get_centroid(), LIST_FREE, LIST_GET, LIST_SIZE, ND_coord, NULL, pointf_s::x, and pointf_s::y.

Referenced by makeStraightEdges().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ is_cycle_unique()

static bool is_cycle_unique	(	cycles_t *	cycles,
		nodes_t *	cycle
	)

static

Definition at line 811 of file routespl.c.

References LIST_CONTAINS, LIST_GET, and LIST_SIZE.

Referenced by dfs().

Here is the caller graph for this function:

◆ limitBoxes()

static void limitBoxes	(	boxf *	boxes,
		size_t	boxn,
		const pointf *	pps,
		size_t	pn,
		double	delta
	)

static

Definition at line 231 of file routespl.c.

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

◆ LIST() [1/2]

typedef LIST ( node_t * )

Definition at line 783 of file routespl.c.

References free(), LIST_FREE, and NULL.

Here is the call graph for this function:

◆ LIST() [2/2]

typedef LIST ( nodes_t * )

Definition at line 792 of file routespl.c.

References aghead, agtail, edge, LIST_GET, and LIST_SIZE.

◆ makeStraightEdge()

void makeStraightEdge	(	graph_t *	g,
		edge_t *	e,
		int	et,
		splineInfo *	sinfo
	)

Definition at line 953 of file routespl.c.

References ED_to_virt, free(), gv_calloc(), makeStraightEdges(), and sinfo.

Referenced by genroute(), and spline_edges_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ makeStraightEdges()

void makeStraightEdges	(	graph_t *	g,
		edge_t **	edge_list,
		size_t	e_cnt,
		int	et,
		splineInfo *	sinfo
	)

Definition at line 972 of file routespl.c.

References add_pointf(), addEdgeLabels(), aghead, agtail, APPROXEQPT, clip_and_install(), Concentrate, del(), dx, ED_head_port, ED_tail_port, EDGETYPE_CURVED, EDGETYPE_PLINE, GD_nodesep, get_cycle_centroid(), head, make_polyline(), MILLIPOINT, ND_coord, perp(), Ppoly_t::pn, Ppoly_t::ps, Agraph_s::root, sinfo, pointf_s::x, and pointf_s::y.

Referenced by dot_splines_(), and makeStraightEdge().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ overlap()

static double overlap	(	double	i0,
		double	i1,
		double	j0,
		double	j1
	)

static

Definition at line 602 of file routespl.c.

Referenced by arrow_length_crow(), arrow_length_diamond(), arrow_length_normal(), and checkpath().

Here is the caller graph for this function:

◆ printpath()

static void printpath ( path * pp )

static

Definition at line 761 of file routespl.c.

References path::boxes, port::constrained, path::end, boxf::LL, path::nbox, port::p, PRISIZE_T, path::start, port::theta, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by checkpath().

Here is the caller graph for this function:

◆ routepolylines()

pointf * routepolylines	(	path *	pp,
		size_t *	npoints
	)

Definition at line 598 of file routespl.c.

References routesplines_().

Referenced by make_flat_bottom_edges(), make_flat_edge(), make_flat_labeled_edge(), and make_regular_edge().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ routesplines()

pointf * routesplines	(	path *	pp,
		size_t *	npoints
	)

Definition at line 594 of file routespl.c.

References routesplines_().

Referenced by make_flat_bottom_edges(), make_flat_edge(), make_flat_labeled_edge(), and make_regular_edge().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ routesplines_()

static pointf * routesplines_	(	path *	pp,
		size_t *	npoints,
		int	polyline
	)

static

Route a path using the path info in pp. This includes start and end points plus a collection of contiguous boxes containing the terminal points. The boxes are converted into a containing polygon. A shortest path is constructed within the polygon from between the terminal points. If polyline is true, this path is converted to a spline representation. Otherwise, we call the path planner to convert the polyline into a smooth spline staying within the polygon. In both cases, the function returns an array of the computed control points. The number of these points is given in npoints.

During cleanup, the function determines the x-extent of the spline in the box, so the box can be shrunk to the minimum width. The extra space can then be used by other edges.

If a catastrophic error, return NULL and npoints is 0.

Definition at line 289 of file routespl.c.

Referenced by routepolylines(), and routesplines().

Here is the caller graph for this function:

◆ routesplinesinit()

int routesplinesinit ( void )

Data initialized once until matching call to routeplineterm Allows recursive calls to dot

Definition at line 211 of file routespl.c.

References LIST_FREE, nboxes, nedges, routeinit, Show_boxes, start_timer(), and Verbose.

Referenced by dot_splines_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ routesplinesterm()

void routesplinesterm ( void )

Definition at line 224 of file routespl.c.

References elapsed_sec(), GV_DEBUG, nboxes, nedges, PRISIZE_T, and routeinit.

Referenced by dot_splines_().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ simpleSplineRoute()

pointf * simpleSplineRoute	(	pointf	tp,
		pointf	hp,
		Ppoly_t	poly,
		size_t *	n_spl_pts,
		int	polyline
	)

Definition at line 168 of file routespl.c.

References Pedge_t::a, agerrorf(), Pedge_t::b, free(), gv_calloc(), make_polyline(), NULL, Ppoly_t::pn, Proutespline(), Ppoly_t::ps, Pshortestpath(), pointf_s::x, Pxy_t::x, pointf_s::y, and Pxy_t::y.

Referenced by makeSimpleFlatLabels().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

◆ nboxes

size_t nboxes

static

Definition at line 33 of file routespl.c.

Referenced by routesplinesinit(), and routesplinesterm().

◆ nedges

◆ routeinit

int routeinit

static

Definition at line 35 of file routespl.c.

Referenced by routesplinesinit(), and routesplinesterm().

Macros

Functions

Variables

Macro Definition Documentation

◆ FUDGE

◆ INIT_DELTA

◆ LOOP_TRIES

Function Documentation

◆ bend()

◆ checkpath()

◆ dfs()

◆ find_all_cycles()

◆ find_shortest_cycle_with_edge()

◆ get_centroid()

◆ get_cycle_centroid()

◆ is_cycle_unique()

◆ limitBoxes()

◆ LIST() [1/2]

◆ LIST() [2/2]

◆ makeStraightEdge()

◆ makeStraightEdges()

◆ overlap()

◆ printpath()

◆ routepolylines()

◆ routesplines()

◆ routesplines_()

◆ routesplinesinit()

◆ routesplinesterm()

◆ simpleSplineRoute()

Variable Documentation

◆ nboxes

◆ nedges

◆ routeinit