multispline.c File Reference

#include <assert.h>
#include <float.h>
#include <limits.h>
#include <neatogen/multispline.h>
#include <neatogen/delaunay.h>
#include <neatogen/neatoprocs.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <util/alloc.h>
#include <util/gv_math.h>
#include <neatogen/fPQ.h>

Include dependency graph for multispline.c:

Go to the source code of this file.

Data Structures
struct	ipair
struct	_tri
struct	tripoly_t
struct	item
struct	Ipair
struct	tnode
struct	tedge
struct	tgraph
struct	router_s
struct	side_t
struct	PPQ

Macros
#define	SEP   15
#define	MARGIN   32
#define	EQPT(p, q)   (((p).x==(q).x)&&((p).y==(q).y))
#define	NSMALL   -0.0000000001
#define	PQTYPE   int
#define	PQVTYPE   double
#define	PQ_TYPES
#define	N_VAL(pq, n)   ((PPQ*)pq)->vals[n]
#define	N_IDX(pq, n)   ((PPQ*)pq)->idxs[n]
#define	PQ_CODE
#define	N_DAD(n)   dad[n]
#define	E_WT(e)   (e->dist)
#define	UNSEEN   (-FLT_MAX)

Typedefs
typedef struct _tri	tri

Functions
static bool	spline_merge (node_t *n)
static bool	swap_ends_p (edge_t *e)
static int	cmpItem (void *item1, void *item2)
static void *	newItem (void *p, Dtdisc_t *disc)
static void	addMap (Dt_t *map, int a, int b, int t)
static Dt_t *	mapSegToTri (surface_t *sf)
static int	findMap (Dt_t *map, int a, int b)
static int	cmpIpair (void *pair1, void *pair2)
static void *	newIpair (void *p, Dtdisc_t *disc)
static void	vmapAdd (Dt_t *map, int i, int j)
static int	vMap (Dt_t *map, int i)
static void	mapTri (Dt_t *map, tri *tp)
	map vertex indices from router_t to tripoly_t coordinates
static tri *	addTri (int i, int j, tri *oldp)
static double	bisect (pointf pp, pointf cp, pointf np)
	return the angle bisecting the angle pp–cp–np
static int	raySeg (pointf v, pointf w, pointf a, pointf b)
	check if ray v->w intersects segment a–b
static int	raySegIntersect (pointf v, pointf w, pointf a, pointf b, pointf *p)
static int	triPoint (tripoly_t *trip, int vx, pointf v, pointf w, pointf *ip)
static int	ctrlPtIdx (pointf v, Ppoly_t *polys)
static pointf *	mkCtrlPts (int s, int mult, pointf prev, pointf v, pointf nxt, tripoly_t *trip)
static pointf	triCenter (pointf *pts, int *idxs)
static boxf	bbox (Ppoly_t **obsp, int npoly, int *np)
static int *	mkTriIndices (surface_t *sf)
static ipair	sharedEdge (int *p, int *q)
static void	addTriEdge (tgraph *g, int t, int h, ipair seg)
static void	freeTriGraph (tgraph *tg)
static tgraph	mkTriGraph (surface_t *sf, pointf *pts)
void	freeRouter (router_t *rtr)
router_t *	mkRouter (Ppoly_t **obsp, int npoly)
static void	finishEdge (edge_t *e, Ppoly_t spl, int flip)
static Ppoint_t	tweakEnd (Ppoly_t poly, size_t s, Ppoint_t q)
static void	tweakPath (Ppoly_t poly, size_t t, Ppolyline_t pl)
static int	genroute (tripoly_t *trip, int t, edge_t *e, int doPolyline)
static int	inCone (pointf a, pointf b, pointf c, pointf q)
	returns true iff q is in the convex cone a-b-c
static void	addEndpoint (router_t *rtr, pointf p, node_t *v, int v_id, int sides)
static ipair	edgeToSeg (tgraph tg, int i, int j)
static void	freeTripoly (tripoly_t *trip)
static tripoly_t *	mkPoly (router_t *rtr, int *dad, int s, int t, pointf p_s, pointf p_t, int *sx)
static void	resetGraph (tgraph g, int ncnt, int ecnt, size_t *original_edge_count)
	remove edges and nodes added for current edge routing
static int *	triPath (tgraph g, int n, int v0, int v1, PQ *pq)
int	makeMultiSpline (edge_t *e, router_t *rtr, int doPolyline)

Variables
static splineInfo	sinfo
static Dtdisc_t	itemdisc
static Dtdisc_t	ipairdisc
static pointf	north = {0, 1}
static pointf	northeast = {1, 1}
static pointf	east = {1, 0}
static pointf	southeast = {1, -1}
static pointf	south = {0, -1}
static pointf	southwest = {-1, -1}
static pointf	west = {-1, 0}
static pointf	northwest = {-1, 1}

Macro Definition Documentation

E_WT

#define E_WT

(

e

)

(e->dist)

Definition at line 1094 of file multispline.c.

EQPT

#define EQPT	(		p,
			q
	)		(((p).x==(q).x)&&((p).y==(q).y))

Definition at line 641 of file multispline.c.

MARGIN

#define MARGIN   32

Definition at line 400 of file multispline.c.

N_DAD

#define N_DAD

(

n

)

dad[n]

Definition at line 1093 of file multispline.c.

N_IDX

#define N_IDX	(		pq,
			n
	)		((PPQ*)pq)->idxs[n]

Definition at line 1087 of file multispline.c.

N_VAL

#define N_VAL	(		pq,
			n
	)		((PPQ*)pq)->vals[n]

Definition at line 1086 of file multispline.c.

NSMALL

#define NSMALL   -0.0000000001

Definition at line 797 of file multispline.c.

PQ_CODE

#define PQ_CODE

Definition at line 1089 of file multispline.c.

PQ_TYPES

#define PQ_TYPES

Definition at line 1076 of file multispline.c.

PQTYPE

#define PQTYPE   int

Definition at line 1073 of file multispline.c.

PQVTYPE

#define PQVTYPE   double

Definition at line 1074 of file multispline.c.

SEP

#define SEP   15

Definition at line 287 of file multispline.c.

UNSEEN

#define UNSEEN   (-FLT_MAX)

Definition at line 1095 of file multispline.c.

Typedef Documentation

tri

typedef struct _tri tri

Function Documentation

addEndpoint()

static void addEndpoint ( router_t *  rtr, pointf  p, node_t *  v, int  v_id, int  sides  )

static

Definition at line 821 of file multispline.c.

References add_pointf(), addTriEdge(), BOTTOM, tnode::ctr, east, findMap(), ipair::i, inCone(), ipair::j, LEFT, ND_lim, tnode::ne, tgraph::nodes, north, northeast, northwest, router_s::obs, router_s::ps, raySeg(), RIGHT, south, southeast, southwest, router_s::tg, TOP, router_s::trimap, and west.

Referenced by makeMultiSpline().

Here is the call graph for this function:

Here is the caller graph for this function:

addMap()

static void addMap ( Dt_t *  map, int  a, int  b, int  t  )

static

Definition at line 94 of file multispline.c.

References item::a, dtinsert, SWAP, and item::t.

Referenced by mapSegToTri().

Here is the caller graph for this function:

addTri()

static tri * addTri ( int  i, int  j, tri *  oldp  )

static

Definition at line 207 of file multispline.c.

References gv_alloc(), ipair::i, ipair::j, _tri::nxttri, and _tri::v.

Referenced by mkPoly().

Here is the call graph for this function:

Here is the caller graph for this function:

addTriEdge()

static void addTriEdge ( tgraph *  g, int  t, int  h, ipair  seg  )

static

Definition at line 481 of file multispline.c.

References tnode::ctr, DIST, tedge::dist, tnode::edges, tgraph::edges, gv_recalloc(), tedge::h, tnode::ne, tgraph::nedges, tgraph::nodes, tedge::seg, and tedge::t.

Referenced by addEndpoint(), and mkTriGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

bbox()

static boxf bbox ( Ppoly_t **  obsp, int  npoly, int *  np  )

static

Definition at line 406 of file multispline.c.

References cnt(), boxf::LL, MARGIN, Ppoly_t::pn, Ppoly_t::ps, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by emitGraph(), get_boundingbox(), make_map_from_rectangle_groups(), mkRouter(), poly_inside(), record_inside(), and star_inside().

Here is the call graph for this function:

Here is the caller graph for this function:

bisect()

static double bisect ( pointf  pp, pointf  cp, pointf  np  )

static

Definition at line 217 of file multispline.c.

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

Referenced by mkCtrlPts().

Here is the caller graph for this function:

cmpIpair()

static int cmpIpair ( void *  pair1, void *  pair2  )

static

Definition at line 150 of file multispline.c.

cmpItem()

static int cmpItem ( void *  item1, void *  item2  )

static

Definition at line 63 of file multispline.c.

ctrlPtIdx()

static int ctrlPtIdx ( pointf  v, Ppoly_t *  polys  )

static

Definition at line 274 of file multispline.c.

References Ppoly_t::pn, Ppoly_t::ps, pointf_s::x, and pointf_s::y.

Referenced by mkCtrlPts().

Here is the caller graph for this function:

edgeToSeg()

static ipair edgeToSeg ( tgraph  tg, int  i, int  j  )

static

Definition at line 902 of file multispline.c.

References tnode::edges, tgraph::edges, tedge::h, tnode::ne, tgraph::nodes, tedge::seg, and tedge::t.

Referenced by mkPoly().

Here is the caller graph for this function:

findMap()

static int findMap ( Dt_t *  map, int  a, int  b  )

static

Definition at line 126 of file multispline.c.

References item::a, dtsearch, SWAP, and item::t.

Referenced by addEndpoint().

Here is the caller graph for this function:

finishEdge()

static void finishEdge ( edge_t *  e, Ppoly_t  spl, int  flip  )

static

Definition at line 628 of file multispline.c.

References addEdgeLabels(), aghead, agnameof(), agtail, clip_and_install(), Ppoly_t::pn, Ppoly_t::ps, sinfo, SWAP, and Verbose.

Referenced by genroute().

Here is the call graph for this function:

Here is the caller graph for this function:

freeRouter()

void freeRouter

(

router_t *

rtr

)

Definition at line 544 of file multispline.c.

References dtclose(), free(), freeTriGraph(), router_s::obs, router_s::ps, router_s::tg, router_s::trimap, and router_s::tris.

Referenced by spline_edges_().

Here is the call graph for this function:

Here is the caller graph for this function:

freeTriGraph()

static void freeTriGraph ( tgraph *  tg )

static

Definition at line 503 of file multispline.c.

References tnode::edges, tgraph::edges, free(), tgraph::nnodes, and tgraph::nodes.

Referenced by freeRouter().

Here is the call graph for this function:

Here is the caller graph for this function:

freeTripoly()

static void freeTripoly ( tripoly_t *  trip )

static

Definition at line 918 of file multispline.c.

References free(), _tri::nxttri, Ppoly_t::pn, tripoly_t::poly, Ppoly_t::ps, and tripoly_t::triMap.

Referenced by makeMultiSpline().

Here is the call graph for this function:

Here is the caller graph for this function:

genroute()

static int genroute ( tripoly_t *  trip, int  t, edge_t *  e, int  doPolyline  )

static

Definition at line 686 of file multispline.c.

References Pedge_t::a, aghead, agnameof(), agraphof(), agtail, agwarningf(), Pedge_t::b, Concentrate, ED_count, ED_to_virt, finishEdge(), free(), gv_calloc(), head, make_polyline(), makeStraightEdge(), mkCtrlPts(), NULL, Ppoly_t::pn, tripoly_t::poly, Proutespline(), Ppoly_t::ps, Pshortestpath(), sinfo, tweakPath(), pointf_s::x, Pxy_t::x, pointf_s::y, and Pxy_t::y.

Referenced by makeMultiSpline().

Here is the call graph for this function:

Here is the caller graph for this function:

inCone()

static int inCone ( pointf  a, pointf  b, pointf  c, pointf  q  )

static

Definition at line 801 of file multispline.c.

References area2(), and NSMALL.

Referenced by addEndpoint().

Here is the call graph for this function:

Here is the caller graph for this function:

makeMultiSpline()

int makeMultiSpline	(	edge_t *	e,
		router_t *	rtr,
		int	doPolyline
	)

Definition at line 1152 of file multispline.c.

References addEndpoint(), aghead, agtail, ED_head_port, ED_path, ED_tail_port, free(), freeTripoly(), genroute(), gv_calloc(), mkPoly(), tnode::ne, tgraph::nedges, tgraph::nnodes, tgraph::nodes, Ppoly_t::pn, PQfree(), PQgen(), PQTYPE, PQVTYPE, Ppoly_t::ps, resetGraph(), router_s::tg, router_s::tn, and triPath().

Referenced by spline_edges_().

Here is the call graph for this function:

Here is the caller graph for this function:

mapSegToTri()

static Dt_t * mapSegToTri ( surface_t *  sf )

static

Definition at line 110 of file multispline.c.

References addMap(), dtopen(), Dtoset, surface_t::faces, itemdisc, surface_t::nfaces, and ps.

Referenced by mkRouter().

Here is the call graph for this function:

Here is the caller graph for this function:

mapTri()

static void mapTri ( Dt_t *  map, tri *  tp  )

static

Definition at line 198 of file multispline.c.

References ipair::i, ipair::j, _tri::nxttri, _tri::v, and vMap().

Referenced by mkPoly().

Here is the call graph for this function:

Here is the caller graph for this function:

mkCtrlPts()

static pointf * mkCtrlPts ( int  s, int  mult, pointf  prev, pointf  v, pointf  nxt, tripoly_t *  trip  )

static

Definition at line 298 of file multispline.c.

References bisect(), ctrlPtIdx(), DIST, free(), gv_calloc(), NULL, tripoly_t::poly, prev, ps, SEP, triPoint(), wind(), pointf_s::x, and pointf_s::y.

Referenced by genroute().

Here is the call graph for this function:

Here is the caller graph for this function:

mkPoly()

static tripoly_t * mkPoly ( router_t *  rtr, int *  dad, int  s, int  t, pointf  p_s, pointf  p_t, int *  sx  )

static

Definition at line 951 of file multispline.c.

References addTri(), dtclose(), dtopen(), Dtoset, edgeToSeg(), free(), gv_alloc(), gv_calloc(), ipair::i, ipairdisc, ipair::j, mapTri(), NULL, ps, router_s::ps, router_s::tg, side_t::ts, side_t::v, and vmapAdd().

Referenced by makeMultiSpline().

Here is the call graph for this function:

Here is the caller graph for this function:

mkRouter()

router_t * mkRouter	(	Ppoly_t **	obsp,
		int	npoly
	)

Definition at line 554 of file multispline.c.

References bbox(), free(), freeSurface(), gv_alloc(), gv_calloc(), boxf::LL, mapSegToTri(), mkSurface(), mkTriGraph(), mkTriIndices(), surface_t::nfaces, router_s::obs, router_s::pn, Ppoly_t::pn, router_s::ps, Ppoly_t::ps, router_s::tg, router_s::tn, router_s::trimap, router_s::tris, boxf::UR, pointf_s::x, and pointf_s::y.

Referenced by spline_edges_().

Here is the call graph for this function:

Here is the caller graph for this function:

mkTriGraph()

static tgraph mkTriGraph ( surface_t *  sf, pointf *  pts  )

static

Definition at line 516 of file multispline.c.

References addTriEdge(), tnode::ctr, surface_t::faces, gv_calloc(), surface_t::neigh, surface_t::nfaces, tgraph::nnodes, tgraph::nodes, sharedEdge(), and triCenter().

Referenced by mkRouter().

Here is the call graph for this function:

Here is the caller graph for this function:

mkTriIndices()

static int * mkTriIndices ( surface_t *  sf )

static

Definition at line 438 of file multispline.c.

References surface_t::faces, gv_calloc(), and surface_t::nfaces.

Referenced by mkRouter().

Here is the call graph for this function:

Here is the caller graph for this function:

newIpair()

static void * newIpair ( void *  p, Dtdisc_t *  disc  )

static

Definition at line 162 of file multispline.c.

References disc, gv_alloc(), Ipair::i, and Ipair::j.

Here is the call graph for this function:

newItem()

static void * newItem ( void *  p, Dtdisc_t *  disc  )

static

Definition at line 73 of file multispline.c.

References item::a, disc, gv_alloc(), and item::t.

Here is the call graph for this function:

raySeg()

static int raySeg ( pointf  v, pointf  w, pointf  a, pointf  b  )

static

Definition at line 226 of file multispline.c.

References wind().

Referenced by addEndpoint(), and raySegIntersect().

Here is the call graph for this function:

Here is the caller graph for this function:

raySegIntersect()

static int raySegIntersect ( pointf  v, pointf  w, pointf  a, pointf  b, pointf *  p  )

static

Definition at line 243 of file multispline.c.

References line_intersect(), and raySeg().

Referenced by triPoint().

Here is the call graph for this function:

Here is the caller graph for this function:

resetGraph()

static void resetGraph ( tgraph  g, int  ncnt, int  ecnt, size_t *  original_edge_count  )

static

Definition at line 1062 of file multispline.c.

References tnode::ne, tgraph::nedges, and tgraph::nodes.

Referenced by makeMultiSpline().

Here is the caller graph for this function:

sharedEdge()

static ipair sharedEdge ( int *  p, int *  q  )

static

Definition at line 448 of file multispline.c.

References ipair::i, ipair::j, and SWAP.

Referenced by mkTriGraph().

Here is the caller graph for this function:

spline_merge()

static bool spline_merge ( node_t *  n )

static

Definition at line 23 of file multispline.c.

swap_ends_p()

static bool swap_ends_p ( edge_t *  e )

static

Definition at line 29 of file multispline.c.

triCenter()

static pointf triCenter ( pointf *  pts, int *  idxs  )

static

Definition at line 389 of file multispline.c.

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

Referenced by mkTriGraph().

Here is the caller graph for this function:

triPath()

static int * triPath ( tgraph  g, int  n, int  v0, int  v1, PQ *  pq  )

static

Definition at line 1102 of file multispline.c.

References E_WT, tnode::edges, tgraph::edges, free(), gv_calloc(), tedge::h, is_exactly_equal(), N_DAD, N_VAL, tnode::ne, tgraph::nodes, NULL, PQinit(), PQinsert(), PQremove(), PQupdate(), tedge::t, and UNSEEN.

Referenced by makeMultiSpline().

Here is the call graph for this function:

Here is the caller graph for this function:

triPoint()

static int triPoint ( tripoly_t *  trip, int  vx, pointf  v, pointf  w, pointf *  ip  )

static

Definition at line 258 of file multispline.c.

References ipair::i, ipair::j, _tri::nxttri, tripoly_t::poly, Ppoly_t::ps, raySegIntersect(), tripoly_t::triMap, and _tri::v.

Referenced by mkCtrlPts().

Here is the call graph for this function:

Here is the caller graph for this function:

tweakEnd()

static Ppoint_t tweakEnd ( Ppoly_t  poly, size_t  s, Ppoint_t  q  )

static

Definition at line 656 of file multispline.c.

References EQPT, Pxy_t::x, and Pxy_t::y.

Referenced by tweakPath().

Here is the caller graph for this function:

tweakPath()

static void tweakPath ( Ppoly_t  poly, size_t  t, Ppolyline_t  pl  )

static

Definition at line 676 of file multispline.c.

References Ppoly_t::pn, Ppoly_t::ps, and tweakEnd().

Referenced by genroute().

Here is the call graph for this function:

Here is the caller graph for this function:

vMap()

static int vMap ( Dt_t *  map, int  i  )

static

Definition at line 190 of file multispline.c.

References dtmatch, and Ipair::j.

Referenced by mapTri().

Here is the caller graph for this function:

vmapAdd()

static void vmapAdd ( Dt_t *  map, int  i, int  j  )

static

Definition at line 182 of file multispline.c.

References dtinsert, Ipair::i, and Ipair::j.

Referenced by mkPoly().

Here is the caller graph for this function:

Variable Documentation

east

pointf east = {1, 0}

static

Definition at line 808 of file multispline.c.

Referenced by addEndpoint().

ipairdisc

Dtdisc_t ipairdisc

static

Initial value:

= {
    .key = offsetof(Ipair, i),
    .size = sizeof(int),
    .link = offsetof(Ipair, link),
    .makef = newIpair,
    .freef = free,
    .comparf = cmpIpair,
}

Definition at line 173 of file multispline.c.

Referenced by mkPoly().

itemdisc

Dtdisc_t itemdisc

static

Initial value:

= {
    .key = offsetof(item, a),
    .size = 2 * sizeof(int),
    .link = offsetof(item, link),
    .makef = newItem,
    .freef = free,
    .comparf = cmpItem,
}

Definition at line 85 of file multispline.c.

Referenced by mapSegToTri().

north

pointf north = {0, 1}

static

Definition at line 806 of file multispline.c.

Referenced by addEndpoint().

northeast

pointf northeast = {1, 1}

static

Definition at line 807 of file multispline.c.

Referenced by addEndpoint().

northwest

pointf northwest = {-1, 1}

static

Definition at line 813 of file multispline.c.

Referenced by addEndpoint().

sinfo

splineInfo sinfo

static

Initial value:

= {.swapEnds = swap_ends_p,
                           .splineMerge = spline_merge}

Definition at line 35 of file multispline.c.

Referenced by finishEdge(), and genroute().

south

pointf south = {0, -1}

static

Definition at line 810 of file multispline.c.

Referenced by addEndpoint().

southeast

pointf southeast = {1, -1}

static

Definition at line 809 of file multispline.c.

Referenced by addEndpoint().

southwest

pointf southwest = {-1, -1}

static

Definition at line 811 of file multispline.c.

Referenced by addEndpoint().

west

pointf west = {-1, 0}

static

Definition at line 812 of file multispline.c.

Referenced by addEndpoint().