文件列表:

dct\dc.c (8275, 1993-12-17)
dct\dc.h (1102, 1993-12-17)
dct\decl.h (1401, 1993-12-17)
dct\defs.h (1407, 1993-12-17)
dct\edge.c (2964, 1993-12-17)
dct\edge.h (1268, 1993-12-17)
dct\error.c (929, 1993-12-17)
dct\extern.h (836, 1993-12-17)
dct\i_o.c (2504, 1993-12-17)
dct\main.c (2006, 1993-12-17)
dct\Makefile (544, 1993-12-16)
dct\memory.c (1777, 1993-12-17)
dct\sort.c (1479, 1993-12-17)
dct (0, 2009-07-29)

The program implements the worst-case optimal divide-and-conquer Delaunay triangulation algorithm as described in: Guibas, L. and Stolfi, J., "Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams, ", ACT TOG, 4(2), April, 1***5. The algorithm is O(nlogn) time and O(n) space. Some changes have been made (for speed). The InCircle test is different to the one described in the paper and the winged-edge structure is used instead of the quad-edge data structure. To triangulate 1 Megapoints takes about 6 minutes CPU time on a 50Mhz SPARC machine. About half of that time is i/o (binary i/o would reduce it). The input/output model is simple: "dct < file1 > file2". The first line of input must be the number of points in the file. Each point, one per line with x and y separated by a space, should follow. The default output is the edges of the triangulation. If the triangles of the triangulation are sought use "dct -t < file1 > file2". The program (still) suffers from numerical problems, and this area of the implementation needs further work. It will crash at times, guaranteed. Comments, advice, bug reports, etc. welcome. Geoff Leach Department of Computer Science RMIT. gl@cs.rmit.edu.au

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：