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 <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   float
#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)
static tri *	addTri (int i, int j, tri *oldp)
static double	bisect (pointf pp, pointf cp, pointf np)
static int	raySeg (pointf v, pointf w, pointf a, pointf 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)
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)
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 1145 of file multispline.c.

EQPT

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

Definition at line 679 of file multispline.c.

MARGIN

#define MARGIN   32

Definition at line 419 of file multispline.c.

N_DAD

#define N_DAD

(

n

)

dad[n]

Definition at line 1144 of file multispline.c.

N_IDX

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

Definition at line 1138 of file multispline.c.

N_VAL

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

Definition at line 1137 of file multispline.c.

NSMALL

#define NSMALL   -0.0000000001

Definition at line 840 of file multispline.c.

PQ_CODE

#define PQ_CODE

Definition at line 1140 of file multispline.c.

PQ_TYPES

#define PQ_TYPES

Definition at line 1127 of file multispline.c.

PQTYPE

#define PQTYPE   int

Definition at line 1124 of file multispline.c.

PQVTYPE

#define PQVTYPE   float

Definition at line 1125 of file multispline.c.

SEP

#define SEP   15

Definition at line 305 of file multispline.c.

UNSEEN

#define UNSEEN   (-FLT_MAX)

Definition at line 1146 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 867 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 95 of file multispline.c.

References item::a, dtinsert, 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 218 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 505 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 426 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 230 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 157 of file multispline.c.

cmpItem()

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

static

Definition at line 62 of file multispline.c.

ctrlPtIdx()

static int ctrlPtIdx ( pointf  v, Ppoly_t *  polys  )

static

Definition at line 292 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 949 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 131 of file multispline.c.

References item::a, dtsearch, 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 664 of file multispline.c.

References addEdgeLabels(), aghead, agnameof(), agtail, clip_and_install(), Ppoly_t::pn, Ppoly_t::ps, sinfo, 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 579 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 527 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 966 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 726 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 846 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 1207 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 115 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 207 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 317 of file multispline.c.

References bisect(), ctrlPtIdx(), DIST, 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 1000 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 589 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 541 of file multispline.c.

References addTriEdge(), tnode::ctr, surface_t::faces, gv_alloc(), 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 458 of file multispline.c.

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

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 169 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 74 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 241 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 259 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 1113 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 469 of file multispline.c.

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

Referenced by mkTriGraph().

Here is the caller graph for this function:

spline_merge()

static bool spline_merge ( node_t *  n )

static

Definition at line 22 of file multispline.c.

swap_ends_p()

static bool swap_ends_p ( edge_t *  e )

static

Definition at line 28 of file multispline.c.

triCenter()

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

static

Definition at line 408 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 1155 of file multispline.c.

References E_WT, tnode::edges, tgraph::edges, free(), gv_calloc(), tedge::h, 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 275 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 695 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 715 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 197 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 189 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 853 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 180 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 86 of file multispline.c.

Referenced by mapSegToTri().

north

pointf north = {0, 1}

static

Definition at line 851 of file multispline.c.

Referenced by addEndpoint().

northeast

pointf northeast = {1, 1}

static

Definition at line 852 of file multispline.c.

Referenced by addEndpoint().

northwest

pointf northwest = {-1, 1}

static

Definition at line 858 of file multispline.c.

Referenced by addEndpoint().

sinfo

splineInfo sinfo

static

Initial value:

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

Definition at line 34 of file multispline.c.

Referenced by finishEdge(), and genroute().

south

pointf south = {0, -1}

static

Definition at line 855 of file multispline.c.

Referenced by addEndpoint().

southeast

pointf southeast = {1, -1}

static

Definition at line 854 of file multispline.c.

Referenced by addEndpoint().

southwest

pointf southwest = {-1, -1}

static

Definition at line 856 of file multispline.c.

Referenced by addEndpoint().

west

pointf west = {-1, 0}

static

Definition at line 857 of file multispline.c.

Referenced by addEndpoint().