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: