Hi all, This week's productivity was again low because of me studying for final exams. Luckily they will be over in a few days.
Here's a brief description of the algorithm for generation of type B/C lines. 1.Get input line (n points) 2.Add points to the line in every self-intersection. As a result we don't have any intersections on the inside of line segments. /currently: O(n^2) time; optimal: O(n*logn)/ 3.Extract outer and inner contours /currently: approx O((n+k)^2) time; optimal: approx O(n+k); k is number of self intersections/. See attached image for idea of contours. 4.Create parallel line(s) for outer contour(s). /We have left and right outer contour when both line ends are not in a loop. Otherwise the outer contour is only one/ 4'./Type C lines only/. Create a parallel line to every inner contour. 5.Remove ALL loops in the created parallel lines. Some inner parallel lines might be completely removed. Here's how we'll use this for buffer generation. 6.Add "caps" to the line ends. Outer parallel line is the buffer area's border. Inner parallel lines are buffer area's holes. Today I'll start implementing step 5, since the 1-4 seem to work fine. Next week I'll be implementing and testing the above algorithm. As soon as I finish it, I'll start making optimal versions of the functions, since these will be slow on big inputs. Step 2 will be done in O(nlogn) using a line sweeping algorithm. No blocks yet, except of exams. See this thread for some idea of type B/C lines: http://lists.osgeo.org/pipermail/grass-dev/2008-June/038334.html Rosen
<<attachment: contours.png>>
_______________________________________________ grass-dev mailing list [email protected] http://lists.osgeo.org/mailman/listinfo/grass-dev
