\ compute the dual of a graph
\
\ Copyright (C) 2011 David K端hling <dvdkhlng TA gmx TOD de>
\
\ License: GPL3 or later, NO WARRANTY
\
\ Created: Aug 2011
require ./graph.fs
require ./equiv.fs
: edge>frontface ( eidx -- face )
\ given edge-idx with sign-bit encoding orientation of edge, return
\ corresponding initial face-id (assuming that each edge has 1 corresponding
\ face at front/back side each
DUP 0< IF 1negate 2* EXIT THEN
2* 1+ ;
: edge>backface ( eidx -- face )
\ given edge-idx with sign-bit encoding orientation of edge, return
\ corresponding initial face-id (assuming that each edge has 1 corresponding
\ face at front/back side each
1negate edge>frontface ;
: }dual-graph { #nodes xy{ #edges edges{ edgemap{{ faces{ -- #faces }
\ Compute the dual graph
\
\ Input: xy{} : array, indexed by node-id, giving a planar coordinate for
\ nodes in the graph
\ edges{}: array of pairs of node-ids, describing the edges.
\ edgemap{{: edgemap, SORTED(!) via }}sort-edgemap.
\
\ Output: faces{}: array of pairs, fulfilling two roles: (a) each entry is
\ a pair of node-ids describing the edges of the dual graph. note that
\ edges may be listed multiple times. (b) Every entry corresponds to the
\ same index' entry in the edge{} array, giving the 2 face-ids of back
\ and front side of the edge (front side is counter-clockwise side of edge).
\ #faces: number of faces of input, number of nodes of graph faces{}
\ TODO: need a compacted dual graph edge array, listing edges only once,
\ (ordered lower-face,higher-face)?
\ equivalence relation for faces generated here has exactly 2*edges entries
DOUBLE , HERE #edges 2* DOUBLE * ALLOT DUP { equivs{ 'equivs }
\ iterate over all nodes of the graph, collecting equivalence relation of
\ face-ids assigned above
#nodes 0 ?DO
\ list face equivalent relations: front face of edge is equivalent
\ to backside of next edge in counter-clockwise order
edgemap{{ I } 2@ { eidxs{ #neighbours }
#neighbours 0 DO
\ front side of edge I...
eidxs{ I } @ edge>frontface
\ ... and back side of edge I+1
eidxs{ I 1+ #neighbours MOD } @ edge>backface
\ ... belong to same face
'equivs 2!
'equivs CELL+ CELL+ TO 'equivs
LOOP
LOOP
\ apply equivalence classes to faces{}. note that for reduction we treat
\ faces{} as array of face-ids, _not_ array of pairs of faces
\ note that this leads to the ordering backface,frontface on 2@, as
\ 2@ loads lowest address to TOS.
faces{ }eltsize ( s: was-eltsize )
INTEGER faces{ }patch-eltsize
#edges 2* equivs{ #edges 2* faces{ }equivs>idmap ( s: was-eltsize #faces)
SWAP faces{ }patch-eltsize
equivs{ }unallot ;
: }next-boundary-edge { eidx face edges{ edgemap{{ faces{ -- eidx2 }
\ Given one edge on the boundary of face, return next counter-clockwise
\ edge on the face boundary. Note that for the outside face, this is going
\ to look clockwise, though (when viewed from inside the not-outside face).
\ Edge sign ignored on input. Return edge with sign, as stored in
\ edgemap{{ entry of the node we cross. I.e. negative for edges oriented
\ along the counter-clockwise path.
\
\ Explanation: have faces{} maps edges to their backside/frontside face.
\ depending on which side of edge EIDX the face is, counter-clockwise node
\ is either start- or end-node. Then we merely take the next clockwise
\ edge from that node.
eidx 1abs TO eidx
edges{ eidx } 2@ ( s: startnode endnode )
face faces{ eidx } 2@ start-node? ( s: startnode endnode on-backside? }
( on-backside?) IF DROP ( startnode)
ELSE NIP ( endnode) THEN ( s:nextnode )
eidx edgemap{{ ( nextnode)ROT } 2@ }prev-edge ;
\ Customize Emacs
0 [IF]
Local Variables:
compile-command: "gforth dual-test.fs -e bye"
End:
[THEN]