[r2]: trunk / dual.fs History

Child: [r3] (diff)

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95``` ```\ compute the dual of a graph \ \ Copyright (C) 2011 David K端hling \ \ 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] ```