From katsu@po.yb.cc.yamaguchi-u.ac.jp Mon Apr 22 05:48:15 1996 Received: from apl2.sv.cc.yamaguchi-u.ac.jp for katsu@po.yb.cc.yamaguchi-u.ac.jp by www.ccl.net (8.7.1/950822.1) id FAA10177; Mon, 22 Apr 1996 05:16:32 -0400 (EDT) Received: (from katsu@localhost) by apl2.sv.cc.yamaguchi-u.ac.jp (8.6.12+2.4W/3.3W) id SAA18670 for chemistry@www.ccl.net; Mon, 22 Apr 1996 18:16:15 +0900 Date: Mon, 22 Apr 1996 18:16:15 +0900 From: tsuyoshi-katsuragi Message-Id: <199604220916.SAA18670@apl2.sv.cc.yamaguchi-u.ac.jp> To: chemistry@www.ccl.net Subject: AMBER41-LEap Dir Netters: I'm trying to install LEaP in HP-UX, EWS4800(NEC). But I could not install it. and I got the following messages in "mkerr" when "make World >& mkerr &" was done . Please tell me how to install the LEaP in these machines. contents of "mkerr" (HP-UX) ---------------------------------------------------------------------------- lding LEaP for the X Window System Release 5 Tue Apr 16 15:26:39 JST 1996 make Makefile + rm -f Makefile.bak + mv -f Makefile Makefile.bak imake -DUseInstalled -I/usr/local/lib/imake -DDoNormalLib=1 -DDoProfileLib=0 -DDoDebugLib=0 -DDo SharedLib=0 -DLEAP_CONFIG=0x0000 -DTOPDIR=. -DCURDIR=. make Makefiles making Makefiles in ./src/Wc... mv -f Makefile Makefile.bak making Makefiles in ./src/Xpm... mv -f Makefile Makefile.bak making Makefiles in ./src/Xaw3dR4... mv -f Makefile Makefile.bak . . . . cc -g -DMEMORY_DEBUG=0 -I.. -I/usr/include/X11R5 -I/MIT/X11R5/include -DSYSV -Dhpux -c xaI mproperParmTable.c cc -g -DMEMORY_DEBUG=0 -I.. -I/usr/include/X11R5 -I/MIT/X11R5/include -DSYSV -Dhpux -c xaH BondParmTable.c if [ -f xaLeap ]; then rm -f xaLeap~; mv -f xaLeap xaLeap~; fi \: ; cc -o xaLeap basics.o sysdepend.o stringExtra.o varArray.o getline.o pdb_format.o pdb_read.o p db_sprntf.o pdb_sscanf.o pdb_write.o vector.o zMatrix.o sort.o bag.o hash.o dictionary.o database.o nVec tor.o ring.o matrix.o fortran.o displayer.o assoc.o atom.o byteArray.o collection.o container.o internal .o list.o loop.o molecule.o oDouble.o oInteger.o oString.o objekt.o parmSet.o residue.o unit.o unitio.o graphUtil.o select.o amber.o build.o elements.o library.o chirality.o minimizer.o model.o parmLib.o pdbF ile.o tools.o variables.o parser.o help.o helptext.o octree.o commands.o mathop.o block.o restraint.o hy brid.o xTank.o xAction.o x3d.o xBasics.o xaLeap.o xaUnitEditor.o xaTable.o xaAtomTable.o Xaw3dRegistr.o xaCommand.o xaTools.o rgb2hls.o xaAtomParmTable.o xaBondParmTable.o xaAngleParmTable.o xaParmEditor.o x aTorsionParmTable.o xaImproperParmTable.o xaHBondParmTable.o -g -DMEMORY_DEBUG=0 -I.. -L../Wc -lWcLea p -L../Xpm -lXpmLeap -L../Xaw3dR4 -lXaw3dLeap -L/MIT/X11R5/lib -lXmu -lXt -lXext -lX11 -lm /bin/ld: Can't find library for -lXmu *** Error code 1 Stop. *** Error code 1 Stop. *** Error code 1 Stop. (EWS4800(NEC))---------------------------------------------------------------------- Building LEaP for the X Window System Release 6 Mon Apr 15 10:57:41 JST 1996 make Makefile + rm -f Makefile.bak + mv Makefile Makefile.bak imake -DUseInstalled -I/usr/lib/X11/config -DDoNormalLib=1 -DDoProfileLi b=0 -DDoDebugLib=0 -DDoSharedLib=0 -DLEAP_CONFIG=0x0000 -DTOPDIR=. -DCURDIR=. make Makefiles making Makefiles in src/Wc... mv Makefile Makefile.bak . . . . cc -g -DMEMORY_DEBUG=0 -I.. -w -ZXNd=8000 -ZXNp=8000 -KOlimit=1000 -I../.. -I.. /../X11 -I. -Dnec_ews -Dnec_ews_svr4 -Dnec_ews_svr4_2 -DSVR4 -DSVR4_2 -DX11R5_SGS -DNEC_A DDON -DANSICPP -c stringExtra.c cc -g -DMEMORY_DEBUG=0 -I.. -w -ZXNd=8000 -ZXNp=8000 -KOlimit=1000 -I../.. -I.. /../X11 -I. -Dnec_ews -Dnec_ews_svr4 -Dnec_ews_svr4_2 -DSVR4 -DSVR4_2 -DX11R5_SGS -DNEC_A DDON -DANSICPP -c varArray.c cc -g -DMEMORY_DEBUG=0 -I.. -w -ZXNd=8000 -ZXNp=8000 -KOlimit=1000 -I../.. -I.. /../X11 -I. -Dnec_ews -Dnec_ews_svr4 -Dnec_ews_svr4_2 -DSVR4 -DSVR4_2 -DX11R5_SGS -DNEC_A DDON -DANSICPP -c getline.c cfe: Error: getline.c, line 184: 'tch' undefined; reoccurrences will not be reported. ioctl(0, ( ('t'<<8) |18) , &tch); ---------------------------------^ cfe: Error: getline.c, line 185: 'ltch' undefined; reoccurrences will not be reported. ioctl(0, ( ('t'<<8) |116) , <ch); ----------------------------------^ cfe: Error: getline.c, line 190: 'old_tty' undefined; reoccurrences will not be reported. ioctl(0, ( ('t'<<8) |8) , &old_tty); --------------------------------^ cfe: Error: getline.c, line 191: 'new_tty' undefined; reoccurrences will not be reported. new_tty = old_tty; ----^ cfe: Error: getline.c, line 230: 'old_tty' undefined; reoccurrences will not be reported. ioctl(0, ( ('t'<<8) |10) , &old_tty); ---------------------------------^ *** Error code 1 (bu21) make: fatal error. *** Error code 1 (bu21) make: fatal error. *** Error code 1 (bu21) make: fatal error. Tsuyoshi Katsuragi /////////////////////////////// ------------------ Laboratory of Biological Chemistry, Department of Biological Science, Faculty of Agriculture, Yamaguchi University 1677-1, Yoshida, Yamaguchi, 753, Japan E-mail: katsu@po.yb.cc.yamaguchi-u.ac.jp Tel. 81-0839-33-5855 (Prof ide) ////////////////////////////////////////////////// From marc@tome.cbs.univ-montp1.fr Mon Apr 22 09:48:15 1996 Received: from tome.cbs.univ-montp1.fr for marc@tome.cbs.univ-montp1.fr by www.ccl.net (8.7.1/950822.1) id JAA13857; Mon, 22 Apr 1996 09:13:57 -0400 (EDT) Message-Id: <199604221313.JAA13857@www.ccl.net> Received: by tome.cbs.univ-montp1.fr (1.37.109.4/16.2) id AA17396; Mon, 22 Apr 96 15:26:57 +0200 Date: Mon, 22 Apr 96 15:26:57 +0200 From: Marc Adenot To: chemistry@www.ccl.net Subject: tensor components Dear netters, Does anybody knows how to obtain quadrupole or octupole moment values >from their tensor components ??? Cheers, Marc From alex@nov.theochem.uni-hannover.de Mon Apr 22 10:48:18 1996 Received: from mgate.uni-hannover.de for alex@nov.theochem.uni-hannover.de by www.ccl.net (8.7.1/950822.1) id KAA14385; Mon, 22 Apr 1996 10:32:55 -0400 (EDT) Received: from nov.theochem.uni-hannover.de by mgate with SMTP (PP); Mon, 22 Apr 1996 16:31:37 +0200 Received: from THEOCHEM/SpoolDir by nov.theochem.uni-hannover.de (Mercury 1.21); 22 Apr 96 16:29:07 +0200 (MESZ) Received: from SpoolDir by THEOCHEM (Mercury 1.21); 22 Apr 96 16:28:46 +0200 (MESZ) From: "Alexander V. Soudackov" Organization: Theoretische Chemie Uni Hannover To: CHEMISTRY@www.ccl.net Date: Mon, 22 Apr 1996 16:28:38 UTC+0100 Subject: M: Summary (MNDO/d & PM3(tm)) Reply-to: alex@nov.theochem.uni-hannover.de Priority: normal X-mailer: Pegasus Mail for Windows (v2.30) Message-ID: Thanks to all who responced. I think, it's worthwhile to put here the answers I have received. the question was: > I would greately appreciate receiving any references concerning the > recent extensions of MNDO and PM3 methods for calculations of > transition metal (Sc-Zn) containing compounds. As far as I know there > were announced MNDO-d and PM3(tm) methods, but I can not find > references to published papers. ============== Answer 1 ============================================= From: voityuk@theochem.tu-muenchen.de (Alexander Voityuk) Subject: MNDO/d REF W.Thiel and A.Voityuk J.Phys.Chem. 1996,v.100, N2, 616-626 and references therein AV ============== Answer 2 ============================================= From: "Stanislav K. Ignatov" Subject: Re: MNDO/PM3(tm) ? Dear Alexander, There are some references concerning an extension of the PM3 method to the s,p,d-basis: 1. Ignatov S.K., Razuvaev A.G., Kokorev V.N., Alexandrov Yu.A. Extension of the PM3 method to the s,p,d-basis. Test calculations on organochromium compounds. J.Phys.Chem., 1996, Vol.100, P.6354. (Russ.Ed.: Zhurn.Strukt.Khimii(russ.), 1995, Vol.36, N4, S.593). 2. Razuvaev A.G., Ignatov S.K., Kokorev V.N. Bipolar expansion of the Ohno potential and assessment of the two-electron molecular integrals in quantum-chemical methods of the MNDO type. Chem.Phys.Reports, 1995, Vol.14(8), P.1276. (Russ.Ed.: Khim.Fizika, 1995, Vol.14, N8, S.177). 3. Ignatov S.K., Razuvaev A.G., Kokorev V.N. Zhurn.Strukt.Khimii(russ.), 1994, Vol.35, N4, S.24. (Usage of the bipolar expansion method for the calculation of the two-electron two-center integrals). These works were directed mainly to the development of the new sufficient method for calculation of the two-electron bicenter integrals arising in the NDDO-methods. The PM3 atom parameters have been optimized for the chromium atom only. Now we are working on the optimization of first transition row but the results are preliminary yet. As far as I know the MNDO/d by Walter Thiel and Alexander Voityuk may work with some atoms of first transition row but I have failed to find any references on these results and parameters. Some references on MNDO/d (non-transition atoms): 1. Thiel W., Voityuk A.A. Theor.Chim.Acta, 1992, V.81, N6, P.391. (Integral approximations in MNDO/d) 2. Thiel W., Voityuk A.A. Int.J.Quant.Chem., 1992, V.44, P.807. (Parameters and results for halogen atoms) 3. Thiel W., Voityuk A.A. THEOCHEM, 1994, 119(1), P.141. (Parameters and results for silicon) Sincerely, Stanislav Ignatov. ============== Answer 3 ============================================= From: "Ernest Chamot" Subject: Re: CCL:MNDO/PM3(tm) ? Hi Dr. Soudackov, You asked about: > references concerning the recent extensions of MNDO and PM3 methods > for calculations of transition metal (Sc-Zn) containing compounds. > As far as I know there were announced MNDO-d and PM3(tm) methods, > but I can not find references to published papers. I've been following the extension of semiempirical methods to transition metals with much interest, myself. There have been some good symposia at the last couple National ACS meetings, for keeping up with the current state of parameterization. Walter Theile has been developing MNDO/d parameters, but seems to be concentrating on main group elements, rather than transition metals. Warren Hehre is cranking out PM3(tm) parameters at a prodigious rate, but is focusing almost exclusively on reproducing experimental geometries, rather than accurate energies. You should also consider the SAM1 parameters Andy Holder is developing. His work is going agonizingly slowly, but he is taking great pains to generate the best (ie. most accurate as well as most theoretically consistent) parameterization. A couple references on MNDO/d are: W. Theile, Theo.Chem.Acta., 81, 391- (1992). W. Thiel & A. A. Voityuk, Int. J. Quant. Chem., 44(5), 807-29 (1992). Most of the SAM1 and PM3(tm) info that I am aware of has only been "published" in the Ampac and Spartan software literature, and reported in papers given at ACS meetings: Dewar, Ruiz, Yu, Jie, & Holder in the Ampac 4, 4.5, and 5 literature as Ampac testing data to be published. I have been keeping a running tally of the metals parameterized with a rough estimate of the accuracy to expect (a running average deviation from experimental values reported on some test set, not typically the same for the three different methods). Although this continues to change as the parameterizations are refined, here is the current info I have: Heat of Formation Dipole Moment Bond Length Angle MNDO/d +- 4 kcal +- 0.4 D +- 0.04 A +- 2 deg Na - Cl Ti, Fe, Cu, Zn, Ge - Br Zr, Cd, Sn - I Hg SAM1 +- 5 +- 0.3 H C-F Si - Cl Fe, Cu, Br I PM3(tm) Ti, Cr, Mn, Fe, Co, Ni, Cu Zr, Mo, Rh, Pd Hf - W Gd To keep track of developments, I update a general "Modeling Reference" guide for myself as I come across new info. I am making this available at Chamot Labs web site, if you're interested at: http://www.xnet.com/~chamotlb I hope this helps. EC --- Ernest Chamot Consultant in Computational Chemistry Applications Chamot Laboratories, Inc. 530 E. Hillside Rd. Naperville, Illinois 60540 (708) 637-1559 (Voice & Fax) echamot@xnet.com http://www.xnet.com/~chamotlb =================== End of Summary =========================== Thanks to all again. ========================================================================== Dr. Alexander V. Soudackov Tel: (0511) 762-5277 Theoretische Chemie Fax: (0511) 762-5939 Universitaet Hannover E-mail: alex@nov.theochem.uni-hannover.de Am Kleinen Felde 30 30167 Hannover Deutschland -------------------------------------------------------------------------- Thought for the day: A penny saved is ridiculous. ========================================================================== From marianna@treebeard.ciam.unibo.it Mon Apr 22 11:48:23 1996 Received: from treebeard.ciam.unibo.it for marianna@treebeard.ciam.unibo.it by www.ccl.net (8.7.1/950822.1) id LAA15208; Mon, 22 Apr 1996 11:38:06 -0400 (EDT) Received: by treebeard.ciam.unibo.it (AIX 3.2/UCB 5.64/4.03) id AA08261; Mon, 22 Apr 1996 17:37:40 +0100 Date: Mon, 22 Apr 1996 17:37:40 +0100 From: marianna@treebeard.ciam.unibo.it (Marianna Fanti) Message-Id: <9604221637.AA08261@treebeard.ciam.unibo.it> To: CHEMISTRY@www.ccl.net Subject: non commercial ZINDO Dear netters, I have an old old version of Zerner's program ZINDO. It handles only up to 60 atoms and 210 molecular orbitals. I'm aware of more recent non-commercial versions of this program that can handle bigger molecular systems. Does anyone know where I can find those versions or who I have to contact to get them? If the topic is of some interest, I will summarize to the net. Thanks in advance, Marianna =========================================================================== = - Dr. Marianna Fanti = = (__) ____ - Chemistry Department "G. Ciamician" = = (oo)/ \/~` - University of Bologna = = U (__)_____|| - via F. Selmi n. 2, 40100 Bologna U U U = = \|/ || W|| - marianna@treebeard.ciam.unibo.it \|/ \|/ \|/ = =========================================================================== From robert@tocsy.utmb.edu Mon Apr 22 12:48:17 1996 Received: from tocsy.utmb.edu for robert@tocsy.utmb.edu by www.ccl.net (8.7.1/950822.1) id MAA15495; Mon, 22 Apr 1996 12:23:46 -0400 (EDT) Received: by tocsy.utmb.edu (940816.SGI.8.6.9/930416.SGI.AUTO) id LAA03304; Mon, 22 Apr 1996 11:23:20 -0500 Date: Mon, 22 Apr 1996 11:23:15 +0059 (CDT) From: Robert Fraczkiewicz Subject: Summary: Points inside/outside of a polyhedron To: CHEMISTRY@www.ccl.net Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Dear Netters, Thank you all who replied to my posting. In a few days I have received more great ideas than I would have generated in months! Once again, it confirms how important for us is to keep the CCL alive. Cheers, Robert Fraczkiewicz ========================================================================= -------------------------Original posting-------------------------------- Suppose you have given N arbitrary points (in 3D space) that are vertices of a polyhedron: (x1,y1,z1),.....,(xN,yN,zN). What is the fastest algorithm for determining if a given point (x,y,z) is inside or outside of this polyhedron? (Calculating distances to every vertex is not a good idea). I will post summary to the net. Best regards, Robert Fraczkiewicz UT Medical Branch -------------------------------------------------------------------------- ================================Summary=================================== -------------------------------------------------------------------------- Dear Dr. Fraczkiewicz, I guess the first thing I'd do is see whether the point lay within a sphere just barely inerior to the polyhedron, by calculating the square radius of the point (rsq=x^2+y^2+z^2) and seeing whether it is less than R^2, where R is the radius of the sphere. All other points may be inside or outside, but at the least this will decrease the number of points to be tested substantially. You could also construct a sphere which is just barely exterior with radius rho to see whether rsq > rho^2 . All remaining points will lie within a thin layer. These remaining points can be subjected to some (more numerically intensive) clever test, which you may come up with or which someone else from the CCL may suggest. Note that I did not calculate r, in order to avoid the sqrt function. Hope this is helpful, rqt ************************************************************************ Check out the Molecular Monte Carlo home page! http://www.cooper/edu/engineering/chemechem/monte.html ************************************************************************ Robert Q. Topper email: topper@cooper.edu Department of Chemistry phone: (212) 353-4378 The Cooper Union FAX: (212) 353-4341 51 Astor Place subway: take the 6 to Astor Place New York, NY 10003 USA or the N/R to 8th St/NYU http://www.cooper/edu/engineering/chemechem/depts_info/topper.html ************************************************************************ -------------------------------------------------------------------------- Robert, A method I have used is to pass a line through the test point that is parallel to one of the coordinate axes (say X), and then count the number of those intersections of the line with polyhedron faces that have greater X- coordinate than the test point. If the number of such intersections is odd, than the test point is in the interior, if even it is in the exterior. If you save the min. and max. y and z coordinates of every vertex in an array, you can quickly eliminate most faces from consideration for a given test point - for those faces that can intersect the line, you apply a test (appropriate for the number of sides of the face) to determine if the line through the test point intersects the interior of the face. Randy All opinions expressed here are mine, not my employer's ///////////////////////////////////////////////////////////////////////// \\ Randy J. Zauhar, PhD | E-mail: zauhar@tripos.com // \\ Tripos, Inc. | : zauhar@crl.com // \\ 1699 S. Hanley Rd., Suite 303 | Phone: (314) 647-1099 Ext. 3382 // \\ St. Louis, MO 63144 | // ///////////////////////////////////////////////////////////////////////// ** ** ** "If you have conceptions of things that you can have no conception ** ** of, then the conception and the thing appear to co-incide." ** ** --- C.G. Jung ** ************************************************************************* -------------------------------------------------------------------------- Hi Robert, There's a really nice convex hull algorithm that runs in ~nlog(n) time from the Univ. of Minn. Geometry Center. You can get it over the WWW via: http://www.geom.umn.edu/software/download/ --Mike Colvin Sandia National Labs. --------------------------------------------------------------------------- Dear Robert, The algorithm I would employ would do the following, starting with the set of points Pi(x,y,z) (x = 1 to n) and O(x,y) is the point we wnt to test. 1 - define average A(x,z,y) of set of points Pi(x,z,y). 2 - define vector AO from A through O. 3 - find three closest points to this vector that are on the positive end (test with dot product of vectors). Let's call them Pa, Pb, and Pc. 4 - calculate point of intersection of the plane defined by Pa,Pb&Pc and the vector AO. Lets call it P. 5 - now compare distances: if |AO| < |AP| then O is within the polyhedron. Perhaps there are better ways, but this is the easiest I can think of without resorting to pen and paper. Cheers, Craig "Imagine if every Thursday your shoes exploded if you tied them the usual way. This happens to us all the time with computers, and nobody thinks of complaining." -- Jeff Raskin, interviewed in Doctor Dobb's Journal Craig Taverner Structural Chemistry, University of the Witwatersrand, South Africa tel: +27-11-716-2290 fax: +27-11-716-3826 email: craig@hobbes.gh.wits.ac.za www: http://www.gh.wits.ac.za/craig ------------------------------------------------------------------------------ I would be tempted to recommend that you calculate the following: say X-x1,..., X-xN but not sqrt ( (X-x1) **2 + (Y-y1) **2 + (Z-z1)**2) which would allow you to quickly select which points are inside as opposed to outside. Should any of these preliminary calculations have a hint that they may indeed be inside, then you would do a full distance calculation. In other words, testing differences are much faster than calculating the full distance I hope this helps Carlos ********************************************** * Dr. Carlos H. Faerman * * Biochemistry, Molecular and Cell Biology * * Cornell University * * 221 Biotechnology Building * * Ithaca, NY 14853 * * USA * * ........................................ * * carlos@penelope.bio.cornell.edu * * Phone: (607)255-8432 * ********************************************** ------------------------------------------------------------------------------- Dear Robert, Use the Gauss theorem: 1) find all faces and normals 2) calculate an integral of dS/R^2 for each face (R is a radius-vector from your point to an surface element of the face. This integral can be calculated for any point and an oriented triangle. 3) sum contributions for all the faces 4) if the sum is 0 it is outside, otherwise should be 4PI which means that it is inside. Ruben Abagyan ------------------------------------------------------------------------------- I am sure that the graphics people have long found a solution to this problem, but just for fun let's try to make up something: I'll assume that "fast" refers to repeating the operation for many different test points and a fixed polyhedron. If not, forget this idea. First, make a list of all the sides of the polyhedron. Generate the normal form of the planes they are in with the normal vectors pointing inward. Once this is done, all you have to do for testing a specific point is to insert the coordinates of your test point into all the equations (three multiplications and three additions per side) and check if all the results are positive. If so, you are inside the polyhedron, otherwise outside. If that's not fast enough, there are two ways to reduce the number of sides to be checked: 1) Find a sphere that encloses the polyhedron. All test points that are outside this sphere don't have to be checked in detail. 2) Divide the polyhedron into two halves by a suitable dividing plane. Check first in which half you are, and then check onyl the sides in this half. ------------------------------------------------------------------------------- Konrad Hinsen | E-Mail: hinsenk@ere.umontreal.ca Departement de chimie | Tel.: +1-514-343-6111 ext. 3953 Universite de Montreal | Fax: +1-514-343-7586 C.P. 6128, succ. Centre-Ville | Deutsch/Esperanto/English/Nederlands/ Montreal (QC) H3C 3J7 | Francais (phase experimentale) ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- This is a common problem in computer graphics so you may want to check some of the standard texts, such as Hearn and Baker. If your test points might be anywhere you can quickly eliminate some by checking if they are outside a bounding sphere. Depending on the shape of the polyhedron some other space partitioning may be useful. Dave Heisterberg ------------------------------------------------------------------------------- Just an idea. It's very efficient, but not sure it's right. First transform the current coordinate system to one with the given point (x,y,z) as the origin. I.e. subtrate (xi,yi,zi), where i=1,...,N, by (x,y,z). This can be done very fast. Second look at the sign of the transformed coordinates of all vertices. If all xi's, where i=1,...,N, have the same sign, the point is outside of the polyhedron. The statement holds for all yi's or all zi's. So if any one of the three conditions holds, the point will be outside. Otherwise if none of the conditions hold, it's inside. Good Luck! Rui Luo CARB, UMBI 04/15 ------------------------------------------------------------------------------ From: DOUGH@mdli.com Subject: Computational Geometry in C To: robert This is a good book by Joseph O'Rourke - provides algorithms for 2D and 3D geometry calculations - ftp site is provided. Id suggest contacting O'Rourke at orourke@sophia.smith.edu if you cant find the book (Cambridge Univ. Press, 1994, isbn 0-521-445922 paper, 346 pages). ------------------------------------------------------------------------------ > Just an idea. It's very efficient, but not sure it's right. > > First transform the current coordinate system to one with the given point > (x,y,z) as the origin. I.e. subtrate (xi,yi,zi), where i=1,...,N, by > (x,y,z). This can be done very fast. > > Second look at the sign of the transformed coordinates of all vertices. > If all xi's, where i=1,...,N, have the same sign, the point is outside > of the polyhedron. The statement holds for all yi's or all zi's. So if any > one of the three conditions holds, the point will be outside. Otherwise if > none of the conditions hold, it's inside. What you are effectively checking is whether the point is inside or outside a box enclosing the polyhedron. But there are points inside that box which are outside the polyhedron itself. ------------------------------------------------------------------------------- Konrad Hinsen | E-Mail: hinsenk@ere.umontreal.ca Departement de chimie | Tel.: +1-514-343-6111 ext. 3953 Universite de Montreal | Fax: +1-514-343-7586 C.P. 6128, succ. Centre-Ville | Deutsch/Esperanto/English/Nederlands/ Montreal (QC) H3C 3J7 | Francais (phase experimentale) ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- >>>>> "Rui" == Rui Luo writes: Rui> Second look at the sign of the transformed coordinates of all Rui> vertices. If all xi's, where i=1,...,N, have the same sign, Rui> the point is outside of the polyhedron. The statement holds Rui> for all yi's or all zi's. So if any one of the three Rui> conditions holds, the point will be outside. Otherwise if Rui> none of the conditions hold, it's inside. Your last statement is incorrect. Consider the 2D case: ---- / / +/ / / / / / --- If the point '+' is the origin, then all of the Xi's do not have the same sign, nor do all of the Yi's, so none of the above conditions hold, yet the point is still outside the polygon. Your method is another implementation of a bounding box. Usually, however, it is done by simply finding the maximum and minimum value of each coordinate, x, y, and z, and checking to see whether the point's coordinates lie within the extrema of the polyhedrons coordinates. If most of the points of interest likely lie outside the polyhedron this is a quick initial screening method. -Harry ______________________________________________________________________ Avant! Harry C. Johnson IV harry@avanticorp.com 1101 Slater Rd Software Engineer Phone: (919)941-6726 RTP, NC 27703 FAX: (919)941-6700 ______________________________________________________________________ ------------------------------------------------------------------------ On Mon, 15 Apr 1996, Rui Luo wrote: > > Just an idea. It's very efficient, but not sure it's right. > > First transform the current coordinate system to one with the given point > (x,y,z) as the origin. I.e. subtrate (xi,yi,zi), where i=1,...,N, by > (x,y,z). This can be done very fast. > > Second look at the sign of the transformed coordinates of all vertices. > If all xi's, where i=1,...,N, have the same sign, the point is outside > of the polyhedron. The statement holds for all yi's or all zi's. So if any > one of the three conditions holds, the point will be outside. Otherwise if > none of the conditions hold, it's inside. > > It seems to me that this test will be reliable if the polyhedron is known to be convex, but other wise might be easily fooled: ___ \ \ \ \ \ \ *| | / / / / / / ---- Steve Williams Chemistry, ASU Boone, NC USA snip ---------------------------------------------------------------------------- > Just an idea. It's very efficient, but not sure it's right. > > First transform the current coordinate system to one with the given point > (x,y,z) as the origin. I.e. subtrate (xi,yi,zi), where i=1,...,N, by > (x,y,z). This can be done very fast. > > Second look at the sign of the transformed coordinates of all vertices. > If all xi's, where i=1,...,N, have the same sign, the point is outside > of the polyhedron. The statement holds for all yi's or all zi's. So if any > one of the three conditions holds, the point will be outside. Otherwise if > none of the conditions hold, it's inside. > > > Good Luck! > > Rui Luo > While this is a necessary condition for the point to be inside the polyhedron, it isn't sufficient. A polyhedron that has a concave portion may span both side of the point without actually enclosing it. ============================================================================= Carlos L. Simmerling, Ph.D. Department of Pharmaceutical Chemistry Phone: (415) 476-7985 Box 0446, Room S-926 Fax: (415) 476-0688 University of California San Francisco, CA 94143 E-mail: carlos@cgl.ucsf.edu ============================================================================= ----------------------------------------------------------------------------- Dear Dr. Fraczkiewicz : I will suppose that your polyhedron is convex, and made of points (Ai),i=1,n. You can first determine each face of the polyhedron. Any given triad (Ai,Aj,Ak) of points defines a plane for which a normal vector is the vectorial product Nijk=AiAj^AiAk. If for any other point Al the scalar product Nijk.AiAl has always the same sign, this means that all other points Al (l<>i,j,k) are on the same side of the plane defined by (Ai,Aj,Ak), and thus these three points define a facet of the convex polyhedron. Knowing the sign of Nijk.AiAl, you can easily define a normal vector N'ijk=Nijk or -Nijk pointing out of the polyhedron. Then, if you want to determine if a point B is in or out of the polyhedron, simply compute the scalar product AiB.N'ijk for all faces (Ai,Aj,Ak). If this product is negative for any given face (Ai,Aj,Ak), B is inside. Otherwise you can stop the algorithm whenever this product becomes positive : B is outside. If your polyhedron is not convex, the solution is likely to be more complex... Best regards, Nicolas Froloff. ------------------------------------------------------------------------------ Take any ray beginning at the given point. Count the number of points of intersection of this ray with polyhedron surface. If it is even, then the point is outside the polyhedron, if it is odd, then inside. One precaution: the ray may slide on some edges of the polyhedron. Best regards, Alexander Golbraikh ------------------------------------------------------------------------ Dr. Alexander Golbraikh e-mail: golb@osi.lanet.lv Latvian Institute of Organic Synthesis Aizkraukles st. 21 Phone: +(371)-7-552-354 Riga, LV-1006 FAX: +(371)-7-821-038 LATVIA ------------------------------------------------------------------------ ------------------------------------------------------------------------------ Alexander Golbraikh wrote: : : : : Take any ray beginning at the given point. Count the number of : points of intersection of this ray with polyhedron surface. If it is : even, then the point is outside the polyhedron, if it is odd, then inside. : One precaution: the ray may slide on some edges of the polyhedron. : : Best regards, : Alexander Golbraikh : : ^ / |/ < As you say, the ray may slide. The "o" point at the left is |\ outside the "polyhedron" yet passes through the polyhedron | \ surface only once if you send the ray only through the vertices o \ defined by... say the Calphas of a protein. -Brian -- ============================================================================= | .---------.| Brian W. Beck | E-mail Addresses: | |/\ | || Biochem/Biophysics | brian@bert.chem.wsu.edu | || \\ WSU || Washington St. Univ| brian_beck@wsu.edu | |\ - *|| 206 Fulmer | URL http://elmo.chem.wsu.edu/~brian | | | || Pullman, WA, USA | VOICE (509) 335-4083 | | \___________|| 99164-4660 | FAX (509) 335-9688 | ============================================================================= ------------------------------------------------------------------------------ There are a few quick checks: If the x coords of all vertices are all less than or all greater than the x coord of the pt, then the point must be outside. Similarly for y and z. Find the center of an enclosing sphere for the polyhedron. If the point is outside the enclosing sphere, then it is outside the polyhedron. Find the center of a maximal enclosed sphere for the polyhedron. If the point is inside the enclosed sphere, then it must be inside the polyhedron. There is also the scheme of shooting out a ray from the point. If it crosses the polyhedron surface an odd number of times, then it is inside, if an even number of times, then it is outside. -Todd Wipke Molecular Engineering Laboratory University of California Santa Cruz, CA wipke@chemistry.ucsc.edu ------------------------------------------------------------------------------ You can find a long answer in the comp.graphics.algorithm FAQ archived at: http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/algorithms-faq/faq.html In any case: 1) If your polyhedron is convex, it is very efficient to have determined the Ax+By+Cz+D=0 plane equation for each face with the sign convention, for instance, that all points lying in the 'inside' hemi-space are positive (i.e. A x0 + B y0 + C z0 + D > 0). In that case, checking if a new point is inside or outside is just a question of substituting the cartesian coordinates of the point in the plane equations of every face and testing whether all signs are positive or there is one or more negative. 2) No matter if your polyhedron is convex or not, an inside point is such that every ray that begins in the point will intersect the polyhedron faces an odd number of times. Given a new point, you can always decide an arbitrary direction and check for the intersections of the line with the polyhedron faces. If there is zero or an even number of intersections, your point is outside the polyhedron, otherwise it is inside. Hope this helps you. Sincerely, Victor Lua~na -- HomePage http://www.uniovi.es/~quimica.fisica/qcg/vlc/luana.html +--------------------------------------------+ +---^---/ / ! Victor Lua~na ! | ~ / Just in case ! Departamento de Quimica Fisica y Analitica ! | | you don't ! Universidad de Oviedo, 33006-Oviedo, Spain ! < / remember ! e-mail: victor@carbono.quimica.uniovi.es ! | / where Oviedo ! phone: (34)-8-5103491 ! |____ ___/ is ;-) ! fax: (34)-8-5103125 ! \/ +--------------------------------------------+ ------------------------------------------------------------------------------ OK, here is another one: 1) Make a Delone tesselation for the polyhedron vortices. If it is convex, all Delone simplexes (tetrahedra) are inside the polyhedron. In this case if your point is inside of any of the simplexes (simplex is a tetrahedron - so check is simple (center of tetrahedron is always inside, connect center with your point and see wether the border is crossed) it is inside polyhedron. If polyhedron is not convex, there will be Delone simplexes connecting vortices which are entirely outside the polyhedron, and they can be excluded I believe it should work Mike Michael Kotelyanskii PhD Department of Chemical Engineering University of Delaware kotelyan@che.udel.edu Newark DE 19716 ------------------------------------------------------------------------------ If I remember correctly, this is a standard computer science algorithm which is described in Robert Sedgewick's book "Algorithms in C." Normally I'd check first before sending this, but I'm at home, I'm leaving town tomorrow, and the book is currently at my office. Wilfred Tang (wtang@rainbow.uchicago.edu) ------------------------------------------------------------------------------ On Tue, 16 Apr 1996, Brian W. Beck wrote: > Alexander Golbraikh wrote: > : > : > : > : Take any ray beginning at the given point. Count the number of > : points of intersection of this ray with polyhedron surface. If it is > : even, then the point is outside the polyhedron, if it is odd, then inside. > : One precaution: the ray may slide on some edges of the polyhedron. > : > : Best regards, > : Alexander Golbraikh > : > : > ^ / > |/ > < As you say, the ray may slide. The "o" point at the left is > |\ outside the "polyhedron" yet passes through the polyhedron > | \ surface only once if you send the ray only through the vertices > o \ defined by... say the Calphas of a protein. > > -Brian > -- Thank you for your remark. I mean the point must be taken into account in case the ray crosses the surface of the polyhedron, i.e. when any whatever small segment of the ray containing this point contains also points both in the inside and in the outside of the polyhedron. Both cases could be easily discriminated. You may also ask what to do if the given point belongs to the polyhedron surface. In this case all depends on which polyhedron we consider: the closed or the open one. (If we consider that the border (the surface) of the polyhedron belongs to the polyhedron, it is closed). If it is closed, the point belongs to the polyhedron (but isn't its inner point), if it is open, the point doesn't belong to the polyhedron. Alexander +----------------------------------------------------------------------+ + Dr. Alexander Golbraikh Email: golb@osi.lanet.lv + + Group of Molecular Biophysics + + Latvian Institute of Organic Synthesis FAX: + (371) 7-821-038 + + 21 Aizkraukles st. + + Riga LV-1006 Phone: + (371) 7-552-354 + + LATVIA + +----------------------------------------------------------------------+ ------------------------------------------------------------------------------ Dear Netters, Shouldn't be noticed that if you have n points in space, it isn't determined what kind of polyhedron you actually have? This is the non-convex case. Imagine 4 points in 2D: .4 3. 1. 2. You can go 1-2-4-3-1, or 1-3-4-2-1, or 1-3-2-4-1. So the problem is in this case quite complicated. For the "convex" case, staying by 2D (generalization to 3D is straightforward, hopefully :-) I have an idea first to find a gravity centre of the polygon. This is the point we are sure it is inside. Then you join g.c. with the point in question- and determine whether it crosses the border (point outside) or not (inside). Andrzej Szymoszek aszym@ichuwr.chem.uni.wroc.pl ------------------------------------------------------------------------------ > Just an idea. It's very efficient, but not sure it's right. Sorry, but it won't work. > First transform the current coordinate system to one with the given point > (x,y,z) as the origin. I.e. subtrate (xi,yi,zi), where i=1,...,N, by > (x,y,z). This can be done very fast. > > Second look at the sign of the transformed coordinates of all vertices. > If all xi's, where i=1,...,N, have the same sign, the point is outside > of the polyhedron. The statement holds for all yi's or all zi's. So if any > one of the three conditions holds, the point will be outside. Otherwise if > none of the conditions hold, it's inside. If any one of your test conditions is true (eg, all x positive or all x negative) then yes the point is outside the polyhedron, however, if any number of tests is false, the point can still be outside the polyhedron. The tests only work one way. Just consider a square on a 2-d surface with all sides at 45 degrees to the axes. Place the origin just outside one side, and notice that your have points with both positive and negative values for both x and y axes. Cheers, Craig "Imagine if every Thursday your shoes exploded if you tied them the usual way. This happens to us all the time with computers, and nobody thinks of complaining." -- Jeff Raskin, interviewed in Doctor Dobb's Journal Craig Taverner Structural Chemistry, University of the Witwatersrand, South Africa tel: +27-11-716-2290 fax: +27-11-716-3826 email: craig@hobbes.gh.wits.ac.za www: http://www.gh.wits.ac.za/craig ------------------------------------------------------------------------------ Sorry, but can't a voxel algorhythm be instrumental here? -- Eugene ------------------------------------------------------------------------------ -----------------------End of summary-----------------------------------------