Parsing polygons: The Sequel
- To: mathgroup at smc.vnet.net
- Subject: [mg9003] Parsing polygons: The Sequel
- From: Russell Towle <rustybel at foothill.net>
- Date: Tue, 7 Oct 1997 03:35:51 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Hello again! With respect to my query about removing duplicate pairs from
lists of polygons, Wouter Meeussen wrote:
>would it do to make a list of distances to the "facent" d : d^2 =
>x^2+y^2+z^2 and only check and delete the polygons with distances equal to
>+/- some minimum size? The origin could be anywhere. Use pointers to
>polygons instead of the polygons themselves, check for advantages with Sort[
>] or Ordering[ ] (in DiscreteMath`Permutations`)
This is indeed one approach, as you say: find the magnitudes of the face
centers, taken as vectors from the origin. However, in practice, I may end
up with many different magnitudes, and I am back to square one, since I
don't know which is which.
In my actual situation, I am building up a close-packing of zonohedra of
many different types. The exterior surface is at first very non-convex, and
gradually convexifies. As the close-packing grows, thousands of polygons
are involved. At each "stage" of the procedure, a new set of zonohedra is
added to the close-packing. These new zonohedra meet the external surface
of the close-packing at various places, fitting perfectly against sets of
existing faces. At this point I wish to discard from the list of all
polygons, only those which are meeting in pairs; they are "internal," and
play no further role in building up the close-packing. So I must sort the
entire list into those which fall into coincidence in pairs, and those
which are "free." Having obtained the list of free polygons, which form the
new shell of exterior faces, I may again add zonohedra to this shell.
It is just as though, in a simpler example, I am building up a
close-packing of equal cubes. Certain of the square faces of the cubical
close-packing are interior, and cannot be seen from outside the
close-packing. It is these I wish to discard. And their distinguishing
characteristic is, that they fall into coincidence in pairs. As the
close-packing of cubes (suppose it to be in the form of a larger cube)
grows larger, the disparity between the in-radius of the close-packing, and
its circumradius, gets larger and larger; so finding the distances to the
centers of the squares from the origin is of little if any use.
Since I posted my query I have devised a new method which is about four
times faster than my old method. Here are both old and new methods, for
comparison.
1. Old Method:
(*240 faces, 60 faces in 30 pairs, 180 free: 57 seconds*)
a=Level[object,{-3}];
centfaces=Map[facent[#]&, a];
qaz=Table[Position[centfaces, x_ /; x==centfaces[[i]] ],{i,Length[a]}];
red=Flatten[DeleteCases[qaz, x_ /; Length[x]==2]];
Length[red]
2. New Method:
(*240 faces, 60 faces in 30 pairs, 180 free: 15.2 seconds*)
a=Level[object,{-3}];
centfaces=Map[facent[#]&, a];
h=Table[
g=centfaces[[i]];
Position[ Map[g==#&,centfaces], x_ /; x==True],
{i,Length[centfaces]}];
red=Flatten[ Select[h ,Length[#]==1&]];
Length[red]
In both these cases, the "object" is a close-packing of zonohedra with 240
polygons altogether and 180 polygons "free." I reduce the object to a list
of polygons without the Head, "Polygon," by writing a=Level[object, {-3}].
In both cases, I obtain a list of indices into "a," which is fine, since I
can get the list of free polygons by writing a[[red]].
If there was a way to reduce the 15 seconds of Method Two to 2 seconds or
less, that would be wonderful. In the simple example above, only 240 faces
are involved. I am now faced with cases where 4,000 polygons are involved.
And once I find a better method of parsing, there is reason to expect that
I will be working with over 10,000 polygons.
Russell Towle
Giant Gap Press: books on California history, digital topographic maps
P.O. Box 141
Dutch Flat, California 95714
------------------------------
Voice: (916) 389-2872
e-mail: rustybel at foothill.net
------------------------------