MathGroup Archive 1997

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Parsing polygon lists

  • To: mathgroup at
  • Subject: [mg8993] Re: [mg8963] Parsing polygon lists
  • From: Fabian Haas <b5hafa at>
  • Date: Tue, 7 Oct 1997 03:35:40 -0400
  • Sender: owner-wri-mathgroup at

Russell Towle <rustybel at> wrote:

>Hi all,
>I wish to optimize the task of, given a large list of polygons in 3-space,
>some of which may fall into coincidence in pairs, to delete any such pairs
>from the list. The polygons are lists of vertices, and each vertex is a
>list of three real numbers.
>My current method is as follows, using a function "facent" which finds the
>centers of polygons:
>1. Find the centers of each polygon in the list 'a':
>centfaces =3D Map[ facent[#]&,  a];(*no problem here*)
>2. Find the positions in the list of face centers wherein one face center
>equals another:
>qaz =3D Table[ Position[ centfaces, x_ /; x=3D=3Dcentfaces[[i]] ], {i,=
 Length[ a
>]} ];(*slow*)
>3. Drop the duplicate pairs:
>red =3D Flatten[ DeleteCases[ qaz, x_ /; Length[ x ]=3D=3D2] ];(*OK as is*)
>After step (3), I can construct a new list of polygons by writing a[[red]].
>The main problem is step (2), which is terribly slow. At times the number
>of polygons may exceed three or four thousand or more. I am using version
>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

Well, I am not sure but you might also try the  Complement function, see=
 details in the reference manual.
You might need to remove the Polygon by a replacement rule Polygon[a_] -> a=
 (rules are generally slower than function) of by a Map[ #[[1]]&,=
 Polygonlist ]
The point is that Complement does not realize that {{a,b,c}, {d,e,f}} is=
 equal to {{d,e,f}, {a,b,c}} in our sense here, so I added a line that sorts=
list/.If[ a < d, {{a,b,c}, {d,e,f}}, {{d,e,f}, {a,b,c}}].
That works fine for my purposes but I dont know how efficient it works with=
 3 to 4000 polygons. You might check that with Timing function.


Dipl.Biol. Fabian Haas, MPhil
Institut f=FCr Spezielle Zoologie und Evolutionsbiologie
Erbertstr. 1
D-07743 Jena
b5hafa at
Deutschland / Germany
TEL  ++ 49 3641 630 424
=46AX  ++ 49 3641 630 392
                               :-)  (-:

  • Prev by Date: Re: Help! Sin[n Pi] (n Integer)
  • Next by Date: strange messsages when starting MMa
  • Previous by thread: Parsing polygon lists
  • Next by thread: Re: Parsing polygon lists