home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14818 < prev    next >
Encoding:
Text File  |  1992-11-11  |  1.2 KB  |  29 lines
  1. Organization: School of Computer Science, Carnegie Mellon, Pittsburgh, PA
  2. Path: sparky!uunet!cis.ohio-state.edu!news.sei.cmu.edu!fs7.ece.cmu.edu!crabapple.srv.cs.cmu.edu!andrew.cmu.edu!at15+
  3. Newsgroups: sci.math
  4. Message-ID: <gf0S1Rq00iV1Q_M6IK@andrew.cmu.edu>
  5. Date: Wed, 11 Nov 1992 23:41:01 -0500 
  6. From: Andrew Lewis Tepper <at15+@andrew.cmu.edu>
  7. Subject: Polygon Coloring
  8. Lines: 19
  9.  
  10.   I know that there must be a fast algorithm for coloring irregular
  11. polygons, but I can't seem to figure it out. I did come up with a slow
  12. algorithm (unimplemented, and unproven) which is as follows:
  13.  
  14. Call the vertices in the polygon V0,V1,...,Vn where V0==Vn
  15. For each point P in the rectangle that encloses the polygon:
  16.   List the angles formed by Vx \ P \ Vx+1 for 0<=x<=n. Express
  17.   all angles in the range -PI < angle < PI. (If angle==PI, it's
  18.   a boundary point.)
  19. Add the list of numbers. If they add to 0, the point is outside the
  20. polygon. Otherwise it's inside.
  21.  
  22. Certainly there are optimizations; the easiest would be to plot the
  23. polygon, run the algorithm for one point, and do a seed fill for the
  24. rest. Is there a more elegant/faster algorithm than this? I want to do
  25. high speed graphics with this...
  26.  
  27. Andy
  28.  
  29.