Parsing polygon lists

13 views
Skip to first unread message

Russell Towle

unread,
Oct 4, 1997, 3:00:00 AM10/4/97
to

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 = Map[ facent[#]&, a];(*no problem here*)

2. Find the positions in the list of face centers wherein one face center
equals another:
qaz = Table[ Position[ centfaces, x_ /; x==centfaces[[i]] ], {i, Length[ a
]} ];(*slow*)

3. Drop the duplicate pairs:
red = Flatten[ DeleteCases[ qaz, x_ /; Length[ x ]==2] ];(*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
2.2.2.

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: rust...@foothill.net
------------------------------


Xah

unread,
Oct 7, 1997, 3:00:00 AM10/7/97
to

In article <61713u$o...@smc.vnet.net>, Russell Towle <rust...@foothill.net>
wrote:

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

Hi Russell,

Assuming that your list of polygons is flat. Improving upon your solution,
the following one should be faster. Suppose PolygonCentroid[Polygon[...]]
returns the centroid of a polygon.

(*this attaches the centroid as head to each polygon*)
polygonList /. poly_Polygon:>(PolygonCentroid@poly)@poly

Then you can use several techniques that remove duplicates. Something like

Union[{5[7],2[m],a[4],5[6]},SameTest->(Head@#1===Head@#2&)]

Xah
x...@best.com
http://www.best.com/~xah/SpecialPlaneCurves_dir/specialPlaneCurves.html
Mountain View, CA, USA


Reply all
Reply to author
Forward
0 new messages