Hi all,<br><br>This week's productivity was again low because of me studying for final<br>exams. Luckily they will be over in a few days.<br><br>Here's a brief description of the algorithm for generation of type B/C lines.<br>
1.Get input line (n points)<br>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)/<br>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.<br>
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/<br>4'./Type C lines only/. Create a parallel line to every inner contour.<br>
5.Remove ALL loops in the created parallel lines. Some inner parallel lines might be completely removed.<br>Here's how we'll use this for buffer generation.<br>6.Add "caps" to the line ends. Outer parallel line is the buffer area's border. Inner parallel lines are buffer area's holes.<br>
<br>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.<br>
<br>No blocks yet, except of exams.<br><br>See this thread for some idea of type B/C lines:<br><a href="http://lists.osgeo.org/pipermail/grass-dev/2008-June/038334.html">http://lists.osgeo.org/pipermail/grass-dev/2008-June/038334.html</a><br>
<br>Rosen<br>