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 ------------------------------