[GRASS-dev] Re: SoC Report: v.buffer/v.parallel reimplementation

[Росен Матев]

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, Росен Матев <r.matev at gmail.com> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: very_cool.png
Type: image/png
Size: 9656 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/grass-dev/attachments/20080630/7213a987/very_cool-0001.png
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not_so_cool.png
Type: image/png
Size: 10754 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/grass-dev/attachments/20080630/7213a987/not_so_cool-0001.png