home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / graphics / 8320 < prev    next >
Encoding:
Text File  |  1992-07-31  |  4.0 KB  |  86 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!gatech!rpi!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!csn!news.den.mmc.com!iplmail!matisse!mwilson
  3. From: mwilson@orl.mmc.com (Mark Wilson)
  4. Subject: Delauney Triangulation Summary
  5. Message-ID: <1992Jul31.145510.3375@iplmail.orl.mmc.com>
  6. Sender: news@iplmail.orl.mmc.com (NetWork News Manager)
  7. Reply-To: mwilson@orl.mmc.com
  8. Organization: Martin Marietta Orlando
  9. Date: Fri, 31 Jul 1992 14:55:10 GMT
  10. Lines: 74
  11.  
  12. Some time back I asked for info on Delauney triangulation. A compiled list of 
  13. responses follows:
  14.  
  15. From: Martin Ameskamp <ma@informatik.uni-kiel.dbp.de>
  16. there are dozens of algorithms around for that kind of thing, loads of papers
  17. too. But there is also a program called voronoi in /netlib on
  18. research.att.com (192.20.225.2). That works just fine.
  19.  
  20. From: hughes@s1.msi.umn.edu (Matt Hughes)
  21. There is stuff on netlib (voronoi algorithm) and some
  22. people at NSCA wrote some stuff on some alpha algorithm
  23. that is similiar.
  24.  
  25. From: uselton@nas.nasa.gov (Samuel P. Uselton)
  26. I believe there is a Voronoi triangulation (the dual of the Delauney)
  27. in netlib.  I'd have to dig through things to find the exact instructions,
  28. but basically you can send a msg asking for the index, then anon ftp
  29. things that look interesting.
  30.  
  31. From: kenb@amc.com (Ken Birdwell)
  32. "Implementing Watson's Algorithm in three Dimensions".
  33. David A. Field
  34. ACM, 2nd Annual Sympos. on Computational Geometry, 1986, pg 246.
  35.  
  36. From: Sridhar Vajapeyam <kutty@bach.udel.edu>
  37. Are you looking for the implementation in 2 or 3 dimensions? If it's
  38. two dimensions, then it's available from netlib. If it's 3-D, then I have
  39. something I wrote in FORTRAN, but it's not properly documented and very
  40. messy. For the relevant theory, check "Computational Geometry" by Preparata
  41. and Shamos.
  42. The book is published by Springer-Verlag (1985). It is a fairly common book - 
  43. any decent univ/research library will have it. From what you said, I doubt 
  44. that just a Delaunay Triangulation is what yu are looking for - the Del. Tr.
  45. will just give you a bunch of non-intersecting tetrahedra that fill the convex
  46. hull of the set of points.
  47.     You are probably trying to construct a surface through a set of points
  48. in 3-D.  That is a much more difficult thing  - it's part of what I am working
  49. on for my PhD.  I have to run now, but will be glad to give you some references
  50. to papers and stuff if you told me a bit more about what you want. For example,
  51. are you trying to find the smoothest surface, or the minimum area surface, etc.
  52.  
  53. From: CHELLA@evax11.eng.fsu.edu
  54.     You can get the VORONOI programs from netlib. A good general 
  55. technical reference is the book " Computational Geometry" by Preparata 
  56. and Shamos. Also: Green and Sibson: Computing Dirichlet tessellations in 
  57. the plane. The Computer Journal, 21(2):168-173, 1978.
  58.     I am looking for a program to triangulate the interior of an 
  59. arbitrary planar region. If you come across one, I would appreciate the 
  60. information.
  61.  
  62. From: kenv%garcon@sun.com (Ken Vollmar)
  63. A detailed survey paper with references to Delauney triangulation is
  64.     "Voronoi Diagrams -- A Survey of a Fundamental Geometric Data Structure" 
  65.     Franz Aurenhammer, ACM Computing Surveys, Vol.23, No.3, Sept.1991, 
  66.     pp. 345-405.  
  67. In particular, see the section beginning on p. 357. This doesn't directly
  68. discuss any implementations.
  69.  
  70. An algorithm is described in 
  71.     "Computing Dirichlet tesselations in the plane." P.J.Green and R. Sibson,
  72.     Computer Journal.  Vol. 21, May 1978, p. 168-173.
  73.  
  74. Please post your results to news, especially implementations.
  75.  
  76. Per the above request, these are the compiled responses. Sorry this is slow
  77. in posting. 
  78.  
  79. ----------------------------------------------------------------------
  80. Mark Wilson                              Martin Marietta E,I & M Group
  81. mwilson@orl.mmc.com                      Mail Point 170
  82. Phone: (407)356-6386                     P.O. Box 555837
  83. Fax:   (407)436-5482                     Orlando, FL, 32855-5837
  84. My opinions are my opinions, Martin Marietta can speak for itself.
  85.  
  86.