home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3562 < prev    next >
Encoding:
Text File  |  1993-01-24  |  2.0 KB  |  46 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!cs.utexas.edu!torn!nott!emr1!jagrant
  3. From: jagrant@emr1.emr.ca (John Grant)
  4. Subject: need fast algorithm to intersect wiggly lines with polygons
  5. Message-ID: <1993Jan24.050819.9948@emr1.emr.ca>
  6. Organization: Energy, Mines, and Resources, Ottawa
  7. Date: Sun, 24 Jan 1993 05:08:19 GMT
  8. Lines: 36
  9.  
  10. I want to intersect an aircraft flight line with a bunch of polygons,
  11. both closed and open (i.e. lakes, rivers, roads etc).
  12.  
  13. There is only 1 flight line, which is more or less straight, but not
  14. always (availability of GPS navigation has lessened the restrictions
  15. on flying a really straight line, also crosswinds tend to put a
  16. few curves in the line).
  17.  
  18. The flight line has several hundred points in it (i.e. an (x,y) is recorded
  19. every 1 s).  There may be many polygons.  For the open polygons, I need
  20. just the single point(s) (it may intersect more than once).  For the
  21. closed polygons, I need pairs of points (always pairs, i.e. if the
  22. line starts in the middle of the lake, then that is the first point).
  23. I won't worry about tangents where the 2 points are the same.
  24.  
  25. The co-ordinates are all cartesian (UTM), i.e. not geographic long/lat.
  26.  
  27. I know the bounding rectangle for the flight line and for each of the
  28. polygons.  What I do now is to ignore all polygons whose boundingg
  29. rectangles do not intersect with the bounding rectangle of the line.
  30. After that, I do it the hard way.  I take every straight line segment
  31. from [i] to [i+1] of the line and intersect it with every straight
  32. line segment of the polygon from [j] to [j+1], using the usual
  33. straight line intersection equations.  As you can imagine,
  34. it is slow, but it works.  All co-ordinates and calculations are float.
  35.  
  36. I need this to draw a profile section of the flight line, showing the
  37. open polygons it intersects as vertical lines and the closed polygons
  38. as rectangles.
  39.  
  40. Any ideas or references?
  41.  
  42. -- 
  43. John A. Grant                        jagrant@emr1.emr.ca
  44. Airborne Geophysics
  45. Geological Survey of Canada, Ottawa
  46.