32char*
pre =
"%!PS-Adobe-2.0\n\
65 boxf absbb = {.
LL = {.
y = 10.0, .x = 10.0}};
70 fprintf(stderr,
"%%%%Page: 1 1\n%%%%PageBoundingBox: %.0f %.0f %.0f %.0f\n",
74 fprintf (stderr,
"%f %f translate\n", 10-BB.
LL.
x, 10-BB.
LL.
y);
75 fputs (
"0 0 1 setrgbcolor\n", stderr);
76 for (
size_t i = 0; i < n_gcells; i++) {
78 fprintf (stderr,
"%f %f %f %f node\n", bb.
LL.
x, bb.
LL.
y, bb.
UR.
x, bb.
UR.
y);
80 fputs (
"0 0 0 setrgbcolor\n", stderr);
81 for (
size_t i = 0; i < nrect; i++) {
83 fprintf (stderr,
"%f %f %f %f cell\n", bb.
LL.
x, bb.
LL.
y, bb.
UR.
x, bb.
UR.
y);
85 fputs (
"1 0 0 setrgbcolor\n", stderr);
86 fprintf (stderr,
"%f %f %f %f cell\n", BB.
LL.
x, BB.
LL.
y, BB.
UR.
x, BB.
UR.
y);
93static int vcmpid(
void *k1,
void *k2) {
139#define BEND(g,e) ((g->nodes + e->v1)->isVert != (g->nodes + e->v2)->isVert)
140#define HORZ(g,e) ((g->nodes + e->v1)->isVert)
142#define CHANSZ(w) (((w)-3)/2)
143#define IS_SMALL(v) (CHANSZ(v) < 2)
175 int isBend =
BEND(g,ep);
178 const double minsz = fmin(hsz, vsz);
181 for (i = 0; i < cp->
nedges; i++) {
183 if (!
BEND(g,e))
break;
187 for (; i < cp->
nedges; i++) {
205 for (
size_t i = 0; i < cp->
nsides; i++) {
207 if (!onp->
isVert)
continue;
208 if (onp->
cells[0] == cp) {
228 for (
size_t i = 0; i < cp->
nsides; i++) {
230 if (onp->
isVert)
continue;
231 if (onp->
cells[0] == cp) {
259 double wt = (hwt + vwt)/2.0 +
mu;
297 n = ditems + np->
index;
313 for (i = 0; i < g->
nnodes; i++) {
315 if (!np->
cells[0]) fprintf (stderr,
"failed at node %d[0]\n", i);
316 assert (np->
cells[0]);
317 if (!np->
cells[1]) fprintf (stderr,
"failed at node %d[1]\n", i);
318 assert (np->
cells[1]);
335 const size_t bound = 4 * mp->
ncells;
347 for (
size_t i = 0; i < mp->
ncells; i++) {
353 cp->
sides = sides + 4*i;
357 np =
findSVert(g, vdict, pt, ditems,
true);
364 np =
findSVert(g, hdict, pt, ditems,
false);
384 for (
size_t i = 0; i < mp->
ngcells; i++) {
389 snodes_t cp_sides = {0};
392 for (; np && np->
p.
x < cp->
bb.
UR.
x; np =
dtnext (hdict, np)) {
393 snodes_append(&cp_sides, np->
np);
397 for (; np && np->
p.
y < cp->
bb.
UR.
y; np =
dtnext (vdict, np)) {
398 snodes_append(&cp_sides, np->
np);
403 for (; np && np->
p.
x < cp->
bb.
UR.
x; np =
dtnext (hdict, np)) {
404 snodes_append(&cp_sides, np->
np);
410 for (; np && np->
p.
y < cp->
bb.
UR.
y; np =
dtnext (vdict, np)) {
411 snodes_append(&cp_sides, np->
np);
414 cp->
nsides = snodes_size(&cp_sides);
415 cp->
sides = snodes_detach(&cp_sides);
422 for (
size_t i = 0; i < mp->
ngcells; i++) {
437 for (
size_t i = 0; i < mp->
ncells; i++) {
467 boxf BB = {.
LL = {.
x = DBL_MAX, .y = DBL_MAX},
468 .UR = {.x = -DBL_MAX, .y = -DBL_MAX}};
498 for (
size_t i = 0; i < nrect; i++) {
511 for (
size_t i = 0; i < mp->
ngcells; ++i) {
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
CDT_API int dtclose(Dt_t *)
CDT_API Dtmethod_t * Dtoset
ordered set (self-adjusting tree)
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
int agnnodes(Agraph_t *g)
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Agnode_t * agfstnode(Agraph_t *g)
#define DEFINE_LIST(name, type)
static snode * findSVert(sgraph *g, Dt_t *cdt, pointf p, snodeitem *ditems, bool isVert)
finds a snode by point or creates it
static void createSEdges(cell *cp, sgraph *g)
fills cell::sides and sgraph::edges
static int vcmpid(void *k1, void *k2)
compares points by X and then by Y
static void psdump(cell *gcells, size_t n_gcells, boxf BB, boxf *rects, size_t nrect)
dumps maze::gcells and maze::cells via rects to PostScript
static sgraph * mkMazeGraph(maze *mp, boxf bb)
creates and fills sgraph for maze
maze * mkMaze(graph_t *g)
creates maze and fills maze::gcells and maze::cells. A subroutine of orthoEdges.
void updateWts(sgraph *g, cell *cp, sedge *ep)
updates sedge::weight of cell edges
static Dtdisc_t vdictDisc
static int hcmpid(void *k1, void *k2)
compares points by Y and then by X
static void chkSgraph(sgraph *g)
static void markSmall(cell *cp)
static void updateWt(sedge *ep, double sz)
updates single sedge::weight
static Dtdisc_t hdictDisc
makes maze with mkMaze for routing orthogonal edges
#define IsSmallH(cp)
cell has small width corresponding to a small width node
#define IsSmallV(cp)
cell has small height corresponding to a small height node
#define IsNode(cp)
cell corresponds to node
boxf * partition(cell *cells, size_t ncells, size_t *nrects, boxf bb)
partitions space around cells (nodes) into rectangular tiles
function partition, subroutine of mkMaze
void freeSGraph(sgraph *g)
sedge * createSEdge(sgraph *g, snode *v1, snode *v2, double wt)
snode * createSNode(sgraph *g)
sgraph * createSGraph(size_t nnodes)
void initSEdges(sgraph *g, size_t maxdeg)
result of partitioning available space, part of maze
sedge * edges[6]
up to six links (sedge) between four sides (snode) of the cell
snode ** sides
up to four sides: M_RIGHT, M_TOP, M_LEFT, M_BOTTOM
available channels for orthogonal edges around nodes of graph_t
cell * cells
cells not corresponding to graph nodes
cell * gcells
cells corresponding to graph nodes
Dt_t * vchans
set of vertical channels, created by extractVChans
Dt_t * hchans
set of horizontal channels, created by extractHChans.
a node of search graph sgraph, is created as a border segment between two adjusted cells of type cell...
struct cell * cells[2]
[0] - left or botom, [1] - top or right adjusted cell
trapezoid elements and utilities for partition.c
static int dfp_cmp(double f1, double f2)
double floating point three-way comparison