1. What did you get done this week: (Almost) reimplemented
parallel_line() and added elliptical distances feature. The func can
create sharp outside corners. (expect round corners soon)
2. What do you plan on doing next week: Finish parallel_line()
(implement round corners feature). Reimplement clean_parallel(), so
that it supports the new elliptical distances feature. Then we'll be
able to use loops/without loops feature of v.parallel.
3. Are you blocked on anything: No
1. What did you get done this week: Elliptical distances feature is
working properly now. Round corners option is working.
2. What do you plan on doing next week: Implement loop removal and by
that finish v.parallel. Then I'll announce it on grass-dev ml so that
the new module could be tested by others. Start working on v.buffer
(around Wednesday).
3. Are you blocked on anything: No
why not use hypot() ? There are vector library versions too, for both Cartesian and lat/lon. Vect_line_length(), Vect_line_geodesic_length() and the rest in lib/vector/Vlib/line.c
Vect_line_geodesic_length() will switch to hypot if location is not lat/lon, otherwise it uses the great circle calc.
any thoughts in general on how to deal with parallel lines in lat/lon? I would guess to make them parallel "on the ground" rather than as simple parallel rhumblines.
3D?
+G_message("tol=%f atol=%f", tol, angular_tol);
I would recommend making good use of G_debug() there. You can set the level to "0" to always show the message when developing then adjust that to something higher later on.
---------- Forwarded message ----------
From: Росен Матев <r.matev@gmail.com>
Date: Sun, Jun 15, 2008 at 12:09 PM
Subject: Re: [GRASS-dev] SoC Report: v.buffer/v.parallel reimplementation
To: hamish_b@yahoo.com
Hi Hamish,
Thanks for the suggestions. I'll strip out those G_message calls. I
like the 'both' option and I'll add it. Generating lines which are
parallel "on the ground" is much tougher than simply changing the
LENGTH function. The first thing I'll do after I finish the
traditional parallel lines and buffers is to do some research on this
topic (making parallel lines on ellipsoids' surface).
Regards,
Rosen
On Sat, Jun 14, 2008 at 5:19 AM, Hamish <hamish_b@yahoo.com> wrote:
Hi,
I know it is very much a work in progress, but some minor comments/suggestions.
why not use hypot() ? There are vector library versions too, for both Cartesian and lat/lon. Vect_line_length(), Vect_line_geodesic_length() and the rest in lib/vector/Vlib/line.c
Vect_line_geodesic_length() will switch to hypot if location is not lat/lon, otherwise it uses the great circle calc.
any thoughts in general on how to deal with parallel lines in lat/lon? I would guess to make them parallel "on the ground" rather than as simple parallel rhumblines.
3D?
+G_message("tol=%f atol=%f", tol, angular_tol);
I would recommend making good use of G_debug() there. You can set the level to "0" to always show the message when developing then adjust that to something higher later on.
This week's productivity was very low because of me studying for final
exams. I expect that I won't do much work next week, too.
Nevertheless, this week I analyzed algorithms and with two great ideas
from Wolf and Maris (codenamed "type B/C parallel lines") we will be
able to generate buffers around lines easily and what's more important
- correctly. Type B (and especially type C) lines are tricky for
generation. So far I've thought how to make type B lines and I'm
currently writing a function.
Blocks so far: no significant ones except from university exams
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.
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@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.
I recall that buffering a suburban road network was also a tricky test for the old v.buffer. maybe it helps you as a test for the new version?
(spearfish or NC test datasets, or OpenStreetMap extraction)
I have the "ditches test" on hand, but it contains areas and points as
I recall. I've not implemented nothing in v.buffer yet. I'm now
working on those parallel lines (to lines of course), which will make
implementing of v.buffer a piece of cake. Wait for a few more days,
and you'll be able to test the new modules. I'll update docs, since
there are new features and different cmd line options.
Rosen
On Mon, Jun 30, 2008 at 3:38 AM, Hamish <hamish_b@yahoo.com> wrote:
I recall that buffering a suburban road network was also a tricky test for the old v.buffer. maybe it helps you as a test for the new version?
(spearfish or NC test datasets, or OpenStreetMap extraction)
This week I managed to finish the part, which generates parallel lines
to all the inner and outer contours of the input line. You probably
already saw that, as I posted images. I figured out the algorithm for
the final phase (the cleaning of extra loops). It's a matter of hours
for me to implement it and test it. It has running time comparable
(and less) to previous parts of the whole algorithm, so it won't be a
bottleneck. Moreover, it doesn't have the flaws of the old
implementation. My task for the weekend is to finish the final part
and integrate the whole thing into v.buffer2. It should be pretty
straightforward process and I don't expect difficulties. Then I'll
update the documentation, so that it covers the new features. There
were some minor blocks this week and they were resolved.
Hi,
This week I was blocked by unexpected behavior of my module. Some
inputs resulted in (slightly) wrong output and sometimes no output at
all. I have identified the causes after a lot of debugging. I came to
the conclusion that I need to reimplement two functions. Wolf, my
mentor, showed me some functions in GRASS library, which can do the
work but using them introduces several complications. Therefore, I
decided to write my own functions. That way the code will be much
faster. By the way, these particular routines might come in handy for
other uses. I'll post a detailed description when I finish them.
(Briefly, they construct a graph, given a polyline on the input.) To
sum up, the last week was somewhat disappointing because of those
*bugs*, but I've resolved them at least on paper.
Next week I'll be implementing the things I've thought up.
The blocks are (hopefully) gone.
This week, I've done the implementation of functions which create the
graph I mentioned about. I've modified all nessessary code to use
them. There are some bugs which I'm dealing with at the moment. Next
week, I'll fix the two bugs (which I found some time ago) in
parallel_line(). I already thought up how to do that. Next week you
should expect the brand new v.buffer showing up in developers ml.
There are no blocks at moment.
This week I finished the development of contour line extraction
algorithm. It works fine now. I only need to do some minor tweaks. It
runs in O(n*n) time but after buffers are working I'll write O(nlogn)
version, which is more complicated (I actually need to rewrite only
one function and not all of them). The previous week I realized that
the issues I found earlier with parallel_line() are serious. I've
found out how to fix the two bugs but the behavior of parallel_line()
is still not well defined. I'm going to start a thread in order to
clear things up (hopefully). However this problems don't stop me from
continuing development of buffer generation because there I need to
create parallel lines only to lines containing no loops. Next week
I'll write this specialized routine and discuss the issues with
general parallel lines.
This week I finished the algorithmic part of buffer lines creation.
The main problem which ocured during tests is due to floating-point
accuracy errors. If I manually set the tolerance it works. The one
approach I tired to compute tolerance from the input map failed. I am
starting to think there might be a need for more precise calculations
at certain points of the code (more than double can give us).
Except this <little> issue, buffer lines are working fine. Next week,
I'll incorporate everything into v.buffer2. I will also do research on
floating point calculations and see what I can do with all the RETs
mess. I already have vague idea how to cope with the issue. I still
have issues with parallel lines. Yes, buffers are ok, but parallel
lines are not, because I don't use those parallel lines for buffer
creation. So defining parallel lines behavior is still open topic.
Probably I should write in ml for help with the last one.
What I've done?
Fought with floating point arithmetic... Finally, decided that using
multi-precision library is inevitable. I've written correct
Vect_segment_intersection() version and optimized it. Also, I've
mostly rewritten the v.buffer/main.c to use the brand new functions.
Fixed some bugs. Now I'm struggling with GRASS' topology. I've posted
to dev ml a question.
Next week?
Finish v.buffer and update documentation. Deal with the only issue
which left - round parallel lines with big distances.
This week I worked on the v.buffer2 module. Found some errors and
fixed them. I've added options for the new features. The code compiles
without GMP, and you can checkout from here: http://trac.osgeo.org/grass/browser/grass-addons/vector/v.buffer2 http://trac.osgeo.org/grass/browser/grass-addons/vector/v.parallel2
Everyone interested can start testing it so we can fix/improve the
code before submitting to trunk. Please email to the grass-dev list,
and to R-dot-Matev-at-gmail-dot-com if you encounter problems/improper
behavior.
I'll be on a vacation next week, so I will probably not respond to
mails till next Saturday.
