home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / graphics / 9510 < prev    next >
Encoding:
Text File  |  1992-09-08  |  2.0 KB  |  55 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!munnari.oz.au!uniwa!cujo!cc.curtin.edu.au!crod
  3. From: crod@cc.curtin.edu.au (Scott Kevill)
  4. Subject: Re: Centroid of a triangle
  5. Message-ID: <1992Sep8.192356.1@cc.curtin.edu.au>
  6. Lines: 43
  7. Sender: news@cujo.curtin.edu.au (News Manager)
  8. Organization: Curtin University of Technology
  9. References: <1992Sep8.064202.24022@monu6.cc.monash.edu.au>
  10. Date: Tue, 8 Sep 1992 10:23:56 GMT
  11.  
  12. In article <1992Sep8.064202.24022@monu6.cc.monash.edu.au>, int565c@ccds.cc.monash.edu.au writes:
  13. > Given a triangle with vertices A(x1,y1), B(x2,y2) and C(x3,y3), what is the
  14. > most efficient algorithm to calculate the centroid of the triangle?
  15. > Calculation needs not to be exact but the key is efficiency/fast.
  16. > 
  17. > EA
  18. > 
  19. > 
  20.  
  21. This may be simpler than you realise, I had almost forgotten this.
  22. I think for any polygon, or even polyhedron in 3D, all you have to
  23. do is average all the points to get the centroid.
  24.  
  25. So in the case of a triangle, it would be : A + B + C
  26.                                            -----------
  27.                                                 3
  28. or more efficiently (A + B + C) *  1/3.
  29. Store 1/3 as a constant, ie 0.333333333, then the operation is just
  30. a multiply.
  31. Pseudocoded it would be something like this :
  32.  
  33. Somewhere in beginning of program or constant declaration ...
  34. oneThird = 0.3333333333
  35.  
  36. Later ...
  37. cx = (x1 + x2 + x3) * oneThird
  38. cy = (y1 + y2 + y3) * oneThird
  39.  
  40. Storing 1/3 as a constant could be a time saver because it is used
  41. twice. That makes the algorithm 6 additions and 2 multiplies.
  42. Shortening the constant to 0.33 or 0.3 may even speed up the
  43. multiplies depending on your accuracy needs, I'm not sure.
  44.  
  45. Has anyone else found anything better ?
  46.  
  47. Hope this helps,
  48.   
  49.   Scott Kevill
  50.  
  51. +-----------------------+--------------------------------------+
  52. I Scott Kevill          I   "Be like me, be original"          I
  53. I crod@cc.curtin.edu.au I                              -- Me   I
  54. +-----------------------+--------------------------------------+
  55.