Hi, Did I really wrote that I'm at step five? Now I am really there (hopefully), after a weekend of rewriting code, a lot of silly mistakes and debugging. I'm very happy with the results. You can see them by yourselves. Next step in my work is to remove those nasty loops (like in not_so_cool.png). I was thinking how to do that and came to the conclusion that it will be trickier than I originally thought. (Having said that, I must also note that most of the things I've already dealt with proved to be harder than I originally had thought :). Maybe that's not surprising. )
Happily, Rosen On Sat, Jun 28, 2008 at 12:02 PM, Росен Матев <[EMAIL PROTECTED]> wrote: > > 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: very_cool.png>>
<<attachment: not_so_cool.png>>
_______________________________________________ grass-dev mailing list [email protected] http://lists.osgeo.org/mailman/listinfo/grass-dev
