ip-leda-homepage.dvi

Size: px

Start display at page:

Download "ip-leda-homepage.dvi"

みいかはらしない
7 years ago
Views:

1 LEDA:,,,, Kurt Mehlhorn LEDA LEDA 1 [2] LEDA Library for Efficient Data types and Algorithms LEDA LEDA C++ 1

2 LEDA LEDA Dijkstra( ) LEDA 2 : LEDA LEDA VORONOI() 1, LEDA voronoi demo.c LEDA 2

3 1: LEDA LEDA 1997 Mehlhorn Mehlhorn LEDA Nina Amenta [1] Nina S VD(S) V S L = S [ V L L L L S LEDA Mehlhorn

4 #include <LEDA/graph.h> #include <LEDA/map.h> #include <LEDA/float kernel.h> #include <LEDA/geo alg.h> #include <LEDA/window.h> void CRUST(const list<point>& S, GRAPH<point, int>& G) f list<point> L=S; GRAPH<circle, point> VD; VORONOI(L, VD); // add Voronoi vertices and mark them map<point, bool> voronoi vertex(false); node v; forall nodes(v, VD) f if (VD.outdeg(v) < 2)continue; point p = VD[v].center(); voronoi vertex[p] = true; L.append(p); g DELAUNAY TRIANG(L, G); forall nodes(v, G) if (voronoi vertex[g[v]]) G.del node(v); g int main() f list<point> S; window W; W.display(); point p; while(w>>p) //input points in the window S.append(p); GRAPH<point, int> G; CRUST(S, G); node v; edge e; W.clear(); forall nodes(v, G)W.draw node(g[v]); forall edges(e, G) W.draw segment(g[source(e)], G[target(e)]); W.screenshot("crust.ps"); 4

5 g //output the screen image to a ps file. leda wait(2.0); //wait 2 seconds return 0; 2 2: CRUST 4 LEDA 5

6 : : 1 n n n i j (i; j) (j; i)

7 : Hopcroft Tarjan 1974 LEDA gw plan demo 6 LEDA ps, 6 7 Layout Simple Layout circular layout?? Kuratowski K ; LEDA Kuratowski 7

8 : 5 5 LEDA LEDA, C++ LEDA Unix Sparc-Solaris, Mips-Irix, i86-linux Windows Visual C++, Borland C++ /usr/local/lib /usr/local/include (make) 6 LEDA LEDA LEDA LEDA 8

9 : Kuratowski LEDA 7 LEDA LEDA MCI(USA), Comptel(Finnland), France Telecom, ATR(Japan), Siemens(Germany), Sun Microsystems(USA), Daimler Benz(Germany), Ford(USA), Silicon Graphics(USA), DEC(USA), Minolta(USA) 8 LEDA Dijkstra LEDA Dijkstra G =(V;E), s 2 V, 9

10 cost: E! N, begin dist(s) =0; dist(v) =1; for v 6= s; ; end while do u dist ; od u for u e =(u; v) do dist(v)= min(dist(v), dist(u)+ cost(e)); od Dijkstra dist LEDA LEDA void DIJKSTRA(const graph &G, node s, const edge array<double>& cost, node array<double>& dist) f node pq <double> PQ(G); node v; edge e; forall nodes(v, G) f if (v == s)dist[v] = 0; else dist[v] = MAXDOUBLE; PQ.insert(v, dist[v]); g while(!pq.empty()) f node u = PQ.del min(); forall out edges(e, u) f v = target(e); double c = dist[u] + cost[e];

11 g g g if(c < dist[v]) f PQ.decrease p(v, c); dist[v] = c; g 9 LEDA LEDA list<int> L; CGAL LEDA LEDA short, int, long, float, double integer, bigfloat rational bigfloat bigfloat::set precision(2λm); LEDA real real x = (sqrt(17) 2) Λ (sqrt(17)+ 2); real =1 LEDA real LEDA Book[] LEDA Manual[4] 11 LEDA : 11

12 . : 4. : 5. : 6. : 7. : 7.1 : Dijkstra Bellman-Ford. 7.2 :. 8. : preflow-push Goldberg-Tarjan. 9. : capacity-scaling.. :. 11. :. : 1. : 14. : Kuratowski. 15. : 16. : 17. : (

13 . : 11. (CRUST) LEDA LEDA /algo-eng/db/index.html [1] N. Amenta, M. Bern, and D. Eppstein: "The crust and the fi-skeleton: Combinatorial curve reconstruction," Graphics Models and Image Processing, pp.5-15 (1998). [2] (1979). [] K. Mehlhorn and S. Näher: "LEDA: A platform for combinatorial and geometric computing," Cmbridge Univ. Press (1999). [4] K. Mehlhorn et al.: "The LEDA User Manual Version 4.0," Max Planck Institute für Informatik, Germenay (1999). 1

P05.ppt

P05.ppt 2 1 list0415.c forfor #include int i, j; for (i = 1; i