From: pdx4d@teleport.com (Kirby Urner) Newsgroups: sci.math Subject: Polyhedron-from-points algorithm sought Date: Thu, 16 Feb 1995 13:47:52 LOCAL Request for Algorithm Ideas: I have a dispersion of points about the origin. In this case they're all equidistant from (0,0,0) and lots of symmetries. What I'm looking for is a computer algorithm, or the rough idea of one, that will draw chords between these points giving a polyhedron. The best I've come up with so far is something like: omnitriangulate the surface. Start with triangle A and check an adjacent triangle B. If B slants the same way in space, then it is part of the same facet, so merge it with A by removing the separating chord. Continue, merging all similarly oriented, adjacent facets into single facets. That sounds a lot easier than it is. All I have to start are the (x,y,z) coordinates of my dispersion. Omnitriangulating, figuring out what's adjacent, and computing "slant in space" are all problematic for me. I'm willing to forge ahead, but if there's a much more elegant algorithm that'd save me from barking up the wrong tree, I'd love to hear about it. Email replies preferred: pdx4d@teleport.com Kirby Urner Portland, Oregon USA ------------------------------------------------ Kirby Urner & Dawn Wicca "All realities are virtual" -- KU Portland (PDX), Oregon pdx4d@teleport.com Web: >Intriguing. This would give an omnitriangulated polyhedron, >>no? Then I'd need to eliminate triangles that are internal >>to the same facet. > >I thought "omnitriangulated" meant you were going to start with >all (n choose 3) trangles joining all triples of points and >then discard the ones which were not exterior. > >I'm not sure of the meaning of your last sentence. >If instead your last sentence is meant to imply that you have to remove >line segments separating two triangles which share a common edge and >lie on one plane, you're right, if you want these edges not to show. That's what I meant. I guess the simple determinant condition is what's got me stumped. I'll hit the books when I get the time. It looks like a big job, but doable. Thanks for your help. Kirby ------------------------------------------------ Kirby Urner & Dawn Wicca "All realities are virtual" -- KU Portland (PDX), Oregon pdx4d@teleport.com Web: