[quickbook] Code links not working

classic Classic list List threaded Threaded
21 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[quickbook] Code links not working

Edward Diener-3
I can not seem to get the quickbook code links to work. Nothing is being
generated from the code link. As an example, to test them out I have in
quickbook:

This is a test of a macro reference - [macroref VMD_DATA_SIZE Test Macro
reference] .

and in my doxygen generated XML I see:

<library-reference id="variadic_macro_data_reference">
   <title>Variadic Macro Data Reference
   </title>
   <header name="boost/variadic_macro_data/VariadicMacroData.hpp">
     <macro name="VMD_DATA_SIZE" kind="functionlike">

etc.

but the output shows:

This is a test of a macro reference - .

Any ideas to get this to work would be appreciated.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [quickbook] Code links not working

Daniel James-3
On 15 October 2010 00:22, Edward Diener <[hidden email]> wrote:
> but the output shows:
>
> This is a test of a macro reference - .
>
> Any ideas to get this to work would be appreciated.

I just tried using macroref to link to a doxygen macro and it's
currently ok in trunk. Whatever the problem is, it's probably nothing
to do with the doxygen to boostbook translation, but more likely an
issue with either the quickbook to boostbook or boostbook to docbook
stages. If might be something to do with the context that you use the
link in. If you check your documentation into subversion I'll have a
look at it. If you can't do that then can you try to create a minimal
quickbook file with the issue (no need for the doxygen files, it
should just produce a broken link if they're absent), and also post
the jamfile and the relevant sections of your user-config.jam.

Daniel
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [quickbook] Code links not working

Edward Diener-3
On 10/15/2010 7:03 AM, Daniel James wrote:

> On 15 October 2010 00:22, Edward Diener<[hidden email]>  wrote:
>> but the output shows:
>>
>> This is a test of a macro reference - .
>>
>> Any ideas to get this to work would be appreciated.
>
> I just tried using macroref to link to a doxygen macro and it's
> currently ok in trunk. Whatever the problem is, it's probably nothing
> to do with the doxygen to boostbook translation, but more likely an
> issue with either the quickbook to boostbook or boostbook to docbook
> stages. If might be something to do with the context that you use the
> link in. If you check your documentation into subversion I'll have a
> look at it. If you can't do that then can you try to create a minimal
> quickbook file with the issue (no need for the doxygen files, it
> should just produce a broken link if they're absent), and also post
> the jamfile and the relevant sections of your user-config.jam.

The quickbook Code Links are now working correctly. Sorry for the noise.
Thanks for your help !

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

[polygon] [GSOC] voronoi diagram of line segments

Simonson, Lucanus J
I just wanted to update the boost dev community on the progress of the GSOC project from this summer implementing voronoi diagram of points and line segments, which leads to delauney triangulation, medial axis of polygons and nearest neighbor.  The student has the sweepline implementation of voronoi for line segments working for several test cases and has provision in the code to handle numerical robustness with the caveot that input coordinates must be integer.  I have attached an appealing screenshot showing the result produced by the new code for a small test case.  Since the sweepline algorithm implementation is optimal O (n log n) and can be made robust given the techniques employed to compute predicates I believe we may be able to release new features in Boost.Polygon based on this work in 2011.  The code isn't yet ready for preview or experimentation, but I thought the community would appreciate the update and sneak peek at the early results generated by the solution to this very challenging computatinal geometry problem.  I also want to publically recognize and congratulate the student, Andrii Sydorchuk, for his good work and great achievement.

Regards,
Luke

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

voronoi_segments.JPG (22K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Dave Abrahams
At Fri, 15 Oct 2010 19:54:07 -0700,
Simonson, Lucanus J wrote:

>
> I just wanted to update the boost dev community on the progress of
> the GSOC project from this summer implementing voronoi diagram of
> points and line segments, which leads to delauney triangulation,
> medial axis of polygons and nearest neighbor.  The student has the
> sweepline implementation of voronoi for line segments working for
> several test cases and has provision in the code to handle numerical
> robustness with the caveot that input coordinates must be integer.
> I have attached an appealing screenshot showing the result produced
> by the new code for a small test case.  

Hey, very appealing!  I have a soft place in my heart for
computational geometry, but it's been a long time since I've studied
it and I'd never seen a voronoi diagram for points *and* line segments
before.  So (just guessing when I could look it up), every line
segment gets a perpendicular line through its endpoints and the curved
lines are equidistant between each line segment and its nearest
point(s)?

> Since the sweepline algorithm implementation is optimal O (n log n)
> and can be made robust given the techniques employed to compute
> predicates I believe we may be able to release new features in
> Boost.Polygon based on this work in 2011.  

So that makes this a very significant achievement.

> The code isn't yet ready for preview or experimentation, but I
> thought the community would appreciate the update and sneak peek at
> the early results generated by the solution to this very challenging
> computatinal geometry problem.  I also want to publically recognize
> and congratulate the student, Andrii Sydorchuk, for his good work
> and great achievement.

Indeed, congratulations to student and mentor alike!

Best Regards,

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Andrii Sydorchuk
Hey, very appealing!  I have a soft place in my heart for

computational geometry, but it's been a long time since I've studied

it and I'd never seen a voronoi diagram for points *and* line segments

before.  So (just guessing when I could look it up), every line

segment gets a perpendicular line through its endpoints and the curved

lines are equidistant between each line segment and its nearest

point(s)?

The voronoi diagram is constructed using the bisectors (the locus of
points equidistant from the two objects) between pairs of objects.
Bisector of two points is a line. While the bisector of two disjoint
segments is a simple curve that may consist up to seven sections (line
or parabola). To simplify everything each segment is divided onto three
parts: two endpoints and segment itself. This way the bisector between
any two objects consists of one section (line or parabola) and falls into
one of four categories:
1) both objects are points - bisector is the line bisecting them;
2) a segment and its endpoint - bisector is the line perpendicular to
    segment through endpoint;
3) a segment and disjoint point - bisector is the section of parabola;
4) both objects are segments - bisector is the line segment.
I guess this simplified explanation will help to understand how it
works for people who haven't seen voronoi of segments before.

 Indeed, congratulations to student and mentor alike!

Thanks.

Best,
Andrii Sydorchuk
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Dave Abrahams
At Sun, 17 Oct 2010 15:18:16 +0300,
Andriy Sydorchuk wrote:
>
> I guess this simplified explanation will help to understand how it
> works for people who haven't seen voronoi of segments before.

It does, thanks much!

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Thomas Klimpel
In reply to this post by Simonson, Lucanus J
Hi Luke and Andriy,

congratulations to this great achievement. I was positively surprised when I saw that the proposal was accepted as a GSOC project, and I always enjoyed seeing that Andriy was making good progress. It's nice to see that Andriy even succeeded implementing Voronoi diagrams of line segments and not just Voronoi diagrams of points.

Simonson, Lucanus J wrote:
> The code isn't yet ready for preview or experimentation,
> but I thought the community would appreciate the update
> and sneak peek at the early results generated by the solution
> to this very challenging computatinal geometry problem.

I agree with Luke's assessment. Even the popular Qhull code <http://www.qhull.org/> only computes Voronoi diagrams of points. Of course, CGAL implements Voronoi diagrams of line segments <http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Segment_Delaunay_graph_2/Chapter_main.html>, but CGAL is not "free". I didn't see a "free" implementation in <http://www.geom.uiuc.edu/software/cglist/>, but I think <http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html> is at least another non-"free" implementation for Voronoi diagrams of line segments.

> I also want to publically recognize and congratulate the student,
> Andrii Sydorchuk, for his good work and great achievement.

I think Andriy really earned that recognition. However, I noticed that the only other feedback is from Dave. I recall Barend Gehrels complained that the student doing the spatial indexing GSOC project was publicly shot down <http://lists.boost.org/Archives/boost/2008/10/143220.php> and subsequently lost any motivation to continue working on his project. It's not clear to me whether scarce positive feedback is even worse than abundant feedback also containing open critique, but working on such a project may depend more on inner motivation than on external feedback anyway. However, I wonder whether also posting to the Boost.Geometry mailing list <http://lists.osgeo.org/mailman/listinfo/ggl> would be a good idea, at least when the code is ready for review and experimentation. It might generate a bit more feedback, because the people there are at least interested in computational geometry. (But more feedback will normally also contain open critique, so you better be prepared.) As
  far as I can see, the only relation between Boost.Polygon and the sweepline project at the current moment is that both rely on integer coordinates to provide robustness (and of course the mentor), so that the project is not too closely tied to Boost.Polygon anyway.

I didn't reply earlier because I had a project deadline last Wednesday. And because I was unable to reply immediately, I took the chance to review the current state of the project a bit. I could successfully build the interactive example qt program on linux, and really liked it. I also build the tests, but some of these were extremely memory hungry and also pushed the processor to full power over a long time. I was less successful on win32. I somehow didn't manage to configure qt as to be able to build the example program. (I will have to work this out when I have time.) The test ran out of memory on win32 with the strange error message "cmalloc would have returned NULL". Tests and benchmarks should push the tested library to its limits, not the test machine.


I thought a bit about the occasions in the past where I wished to have a good Voronoi diagram implementation.

- The Voronoi diagram of a point set would have been useful for the case where some measurements (or computations) were given at some suitably placed 2D points without any explicit grid structure, and the goal was to project these measurements onto a given regular grid using piecewise constant interpolation. When we always use the measurement value of the nearest measurement point for the interpolation, we will implicitly compute the Voronoi diagram of the measurement points. The explicit availability of the Voronoi diagram should speedup this procedure.

- The Voronoi diagram of line segments would have been useful for the case where a 3D topography had been defined by a polygonal base and a cross-section. For a point with given x- and y-coordinate, the signed distance from the polygon edges was computed and used to lookup z-positions in the cross-section. In a certain sense, this procedure will implicitly compute the Voronoi diagram of the Polygon edges viewed as line segments. (The task here was also to evaluate the z-positions on a given regular grid in x-y direction.) The explicit availability of the line segments Voronoi diagram should speedup this computation.

- There are many more application of Voronoi diagrams like triagulations, offseting, shape detection, ..., but the above two are the ones that I can actually still remember having encountered in real live.

Regards,
Thomas
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Mateusz Loskot
On 26/10/10 20:53, Thomas Klimpel wrote:
> However, I wonder whether also posting to the
> Boost.Geometry mailing list
> <http://lists.osgeo.org/mailman/listinfo/ggl> would be a good idea,
> at least when the code is ready for review and experimentation. It
> might generate a bit more feedback, because the people there are at
> least interested in computational geometry.

Thomas,

Andrey's achievement and solid work hasn't slipped unnoticed, certainly not.

Good point though and I have just forwarded this thread there.

Best regards,
--
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org
Member of ACCU, http://accu.org
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
--
Mateusz Loskot, http://mateusz.loskot.net
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Andrii Sydorchuk
Thanks to all of You!

 I also build the tests, but some of these were extremely memory hungry and
> also pushed the processor to full power over a long time.

The test configuration includes tests with 1 000 000 input points. This was
helpful to figure out some longrun bugs. Probably you should run those tests
with release option.
Using release it takes me around 20 secs to run all the tests and around 60
secs to run benchmark tests. The algorithm implementation uses stl vectors,
lists, maps and queues.
Those data structure are slower in the debug mode especially when you run
large inputs.

 I was less successful on win32. I somehow didn't manage to configure qt as
> to be able to build the example program.

I've updated build script, you shouldn't have any troubles now.

 The test ran out of memory on win32 with the strange error message "cmalloc
> would have returned NULL". Tests and benchmarks should push the tested
> library to its limits, not the test machine.

Did you use mingw or cygwin to compile it? I am using msvc 9.0 compiler on
win32 and it works fine. However I received the same message using cygwin +
gcc.
In my case this was failing on the 1 000 000 points test.

Best,
Andrii

On Tue, Oct 26, 2010 at 11:20 PM, Mateusz Loskot <[hidden email]> wrote:

> On 26/10/10 20:53, Thomas Klimpel wrote:
> > However, I wonder whether also posting to the
> > Boost.Geometry mailing list
> > <http://lists.osgeo.org/mailman/listinfo/ggl> would be a good idea,
> > at least when the code is ready for review and experimentation. It
> > might generate a bit more feedback, because the people there are at
> > least interested in computational geometry.
>
> Thomas,
>
> Andrey's achievement and solid work hasn't slipped unnoticed, certainly
> not.
>
> Good point though and I have just forwarded this thread there.
>
> Best regards,
> --
> Mateusz Loskot, http://mateusz.loskot.net
> Charter Member of OSGeo, http://osgeo.org
> Member of ACCU, http://accu.org
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>



--
Best regards,
Andrii Sydorchuk
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Simonson, Lucanus J
In reply to this post by Thomas Klimpel
Thomas Klimpel wrote:
> I agree with Luke's assessment. Even the popular Qhull code
> <http://www.qhull.org/> only computes Voronoi diagrams of points. Of
> course, CGAL implements Voronoi diagrams of line segments
> <http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Segment_Delaunay_graph_2/Chapter_main.html>,
> but CGAL is not "free". I didn't see a "free" implementation in
> <http://www.geom.uiuc.edu/software/cglist/>, but I think
> <http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html> is at
> least another non-"free" implementation for Voronoi diagrams of line
> segments.        

Thanks for the link to vroni, I didn't know of its existence.

> I recall Barend Gehrels
> complained that the student doing the spatial indexing GSOC project
> was publicly shot down
> <http://lists.boost.org/Archives/boost/2008/10/143220.php> and
> subsequently lost any motivation to continue working on his project.

I watched the whole thing play out with the GSOC 2006 spacial indexes project.  That particular GSOC project was a special case in that it would have been reasonable for the mentor to fail the student, in my opinion, based on lack of progress and poor quality of the code.  That's a tough call for a mentor to make, and I hope I'm never in the position where I have to make it.  I feel very fortunate to have found a strong student this year.

> It's not clear to me whether scarce positive feedback is even worse
> than abundant feedback also containing open critique, but working on
> such a project may depend more on inner motivation than on external
> feedback anyway. However, I wonder whether also posting to the
> Boost.Geometry mailing list
> <http://lists.osgeo.org/mailman/listinfo/ggl> would be a good idea,
> at least when the code is ready for review and experimentation. It
> might generate a bit more feedback, because the people there are at
> least interested in computational geometry. (But more feedback will
> normally also contain open critique, so you better be prepared.) As
> far as I can see, the only relation between Boost.Polygon and the
> sweepline project at the current moment is that both rely on integer
> coordinates to provide robustness (and of course the mentor), so that
> the project is not too closely tied to Boost.Polygon anyway.        

Should Andrii eventually provide for floating point numerical robustness I would expect that his work could be integrated into Boost.Geometry, perhaps as an extension that depends on minimal Boost.Polygon detail header files authored by Andrii.  As you say, he has not coupled his implementation to my library so far.  We will need to figure out the policies about cross library dependency between Polygon and Geometry, but that can wait until the first instance of such is suggested.

Regards,
Luke
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Fernando Cacciola-2
Hi Luke,
Hi Andrii,

First of all, congratulations to you both on such an achivement!!

I will try to squeeze some free time during the next weeks to sneak peak into
the code and provide some constructive cricticism.

> Thomas Klimpel wrote:
>> I agree with Luke's assessment. Even the popular Qhull code
>> <http://www.qhull.org/>  only computes Voronoi diagrams of points. Of
>> course, CGAL implements Voronoi diagrams of line segments
>> <http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Segment_Delaunay_graph_2/Chapter_main.html>,
>> but CGAL is not "free". I didn't see a "free" implementation in
>> <http://www.geom.uiuc.edu/software/cglist/>, but I think
>> <http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html>  is at
>> least another non-"free" implementation for Voronoi diagrams of line
>> segments.
>
> Thanks for the link to vroni, I didn't know of its existence.
>
Have in mind that Vroni (which indeed is not free) does not use exact predicates
so it is not robust. At least last time I checked (this is many many years ago)
Martin might have have updated it since then though.

Best


--
---
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Barend Gehrels-3
In reply to this post by Simonson, Lucanus J

Congratulations from my side as well. The diagram in the original mail
is great.

Sorry for my late reaction, I was off-line for most of the time last weeks.


>> However, I wonder whether also posting to the
>> Boost.Geometry mailing list
>> <http://lists.osgeo.org/mailman/listinfo/ggl>  would be a good idea,
>> at least when the code is ready for review and experimentation.

Yes, good idea and Mateusz did forward it, thanks.

>> It
>> might generate a bit more feedback, because the people there are at
>> least interested in computational geometry. (But more feedback will
>> normally also contain open critique, so you better be prepared.) As
>> far as I can see, the only relation between Boost.Polygon and the
>> sweepline project at the current moment is that both rely on integer
>> coordinates to provide robustness (and of course the mentor), so that
>> the project is not too closely tied to Boost.Polygon anyway.
> Should Andrii eventually provide for floating point numerical robustness I would expect that his work could be integrated into Boost.Geometry, perhaps as an extension that depends on minimal Boost.Polygon detail header files authored by Andrii.  As you say, he has not coupled his implementation to my library so far.  We will need to figure out the policies about cross library dependency between Polygon and Geometry, but that can wait until the first instance of such is suggested.

I'm very interested in this. Boost.Geometry does not yet have any
Voronoi diagram related code, it would be a welcome addition. Especially
also the segments Dave mentioned, I didn't see this earlier neither.
And yes, it would also be a good opportunity to investigate cross
library possibilities.

Regards, Barend


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Mateusz Loskot
In reply to this post by Andrii Sydorchuk
Him

Hi,

I tried to find details on this project, but it looks there is no dedicated page on the Wiki
The only information I found is the proposal

https://svn.boost.org/trac/boost/wiki/SoC2010

and lot of archived discussions, of course.

I'm not sure where to look for current codes. Has it been published?
Perhaps it would make sense to have a dedicated wiki page like:

https://svn.boost.org/trac/boost/wiki/SoC2010SweeplineAlgorithm

Regards,
Mateusz
--
Mateusz Loskot, http://mateusz.loskot.net
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Simonson, Lucanus J
In reply to this post by Fernando Cacciola-2
Fernando Cacciola wrote:
>> Thanks for the link to vroni, I didn't know of its existence.
>>
> Have in mind that Vroni (which indeed is not free) does not use exact
> predicates so it is not robust. At least last time I checked (this is
> many many years ago) Martin might have have updated it since then
> though.

Yes, I noticed his discussion of relaxing epsilon and panic mode with some alarm.  Depending on the details of his license we might benchmark against his library.  Most non-free licenses allow benchmarking without charge.  I didn't see a link to the code, and the web site implied that he does not give it out except by request.

Regards,
Luke
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Simonson, Lucanus J
In reply to this post by Mateusz Loskot
mloskot wrote:

> I tried to find details on this project, but it looks there is no
> dedicated page on the Wiki
> The only information I found is the proposal
>
> https://svn.boost.org/trac/boost/wiki/SoC2010
>
> and lot of archived discussions, of course.
>
> I'm not sure where to look for current codes. Has it been published?
> Perhaps it would make sense to have a dedicated wiki page like:
>
> https://svn.boost.org/trac/boost/wiki/SoC2010SweeplineAlgorithm

We don't yet have documentation.  Once we do I planned to integrate it into the boost.polygon documentation on the trunk along with the code.  There will also be a paper and possibly a boostcon presentation at some point.  We want to focus on getting the implementation of the algorithm correct first.  Once it is ready for an API layer to go on top I'll engage the community on what kind of interface to provide for it.  I have a prototype for a line segment concept in boost.polygon and we'll want to be sure to provide the diagram as a graph compatible with boost.graph.  There are quite a few things still to do.  I'm not sure I want to add a wiki to the list.

Thanks,
Luke
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Mateusz Loskot
On 27/10/10 19:17, Simonson, Lucanus J wrote:

> mloskot wrote:
>> I tried to find details on this project, but it looks there is no
>> dedicated page on the Wiki The only information I found is the
>> proposal
>>
>> https://svn.boost.org/trac/boost/wiki/SoC2010
>>
>> and lot of archived discussions, of course.
>>
>> I'm not sure where to look for current codes. Has it been
>> published? Perhaps it would make sense to have a dedicated wiki
>> page like:
>>
>> https://svn.boost.org/trac/boost/wiki/SoC2010SweeplineAlgorithm
>
> We don't yet have documentation.  Once we do I planned to integrate
> it into the boost.polygon documentation on the trunk along with the
> code.

Luke and Andrii,

Thank you, looking forward to checking it.

> There will also be a paper and possibly a boostcon
> presentation at some point.

Nice!

> We want to focus on getting the
> implementation of the algorithm correct first.  Once it is ready for
> an API layer to go on top I'll engage the community on what kind of
> interface to provide for it.  I have a prototype for a line segment
> concept in boost.polygon and we'll want to be sure to provide the
> diagram as a graph compatible with boost.graph.  There are quite a
> few things still to do.  I'm not sure I want to add a wiki to the
> list.

Understood.

Best regards,
--
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org
Member of ACCU, http://accu.org
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
--
Mateusz Loskot, http://mateusz.loskot.net
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Thomas Klimpel
In reply to this post by Andrii Sydorchuk
Andrii Sydorchuk wrote:
> The test configuration includes tests with 1 000 000 input points.
> This was helpful to figure out some longrun bugs.
> Probably you should run those tests with release option.

Ah yes, benchmarking the debug version is a certainly not a good idea.


> > I was less successful on win32. I somehow didn't manage to configure qt as
> > to be able to build the example program.
>
> I've updated build script, you shouldn't have any troubles now.

Great, it works for me now. However, I have to admit that my own mistake was much simpler: I added the line "using qt : /Qt/4.7.0 ;" to the "wrong" user-config.jam file. But I checked that your fix is really required.


> Did you use mingw or cygwin to compile it? I am using
> msvc 9.0 compiler on win32 and it works fine.
> However I received the same message using cygwin + gcc.

You're right, this was cygwin + gcc. I wasn't patient enough to wait for the results with MSVC-9 (as you mentioned before, the std debug checks can slow things down considerably, and MSVC-9 really takes these debug checks serious), but later forgot that I was using cygwin.

Regards,
Thomas
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

Andrii Sydorchuk
Actually I implemented predicate that gives ability to compute exact diagram
in case of voronoi of points. However I removed it from the implementation
because it slowed down algorithm seriously and required additional memory
usage. In case of voronoi of segments there might be up to 9 new predicates
required. Of course they will slow down algorithm seriously and increase
memory consumption.

On Thu, Oct 28, 2010 at 2:41 AM, Thomas Klimpel <[hidden email]
> wrote:

> Andrii Sydorchuk wrote:
> > The test configuration includes tests with 1 000 000 input points.
> > This was helpful to figure out some longrun bugs.
> > Probably you should run those tests with release option.
>
> Ah yes, benchmarking the debug version is a certainly not a good idea.
>
>
> > > I was less successful on win32. I somehow didn't manage to configure qt
> as
> > > to be able to build the example program.
> >
> > I've updated build script, you shouldn't have any troubles now.
>
> Great, it works for me now. However, I have to admit that my own mistake
> was much simpler: I added the line "using qt : /Qt/4.7.0 ;" to the "wrong"
> user-config.jam file. But I checked that your fix is really required.
>
>
> > Did you use mingw or cygwin to compile it? I am using
> > msvc 9.0 compiler on win32 and it works fine.
> > However I received the same message using cygwin + gcc.
>
> You're right, this was cygwin + gcc. I wasn't patient enough to wait for
> the results with MSVC-9 (as you mentioned before, the std debug checks can
> slow things down considerably, and MSVC-9 really takes these debug checks
> serious), but later forgot that I was using cygwin.
>
> Regards,
> Thomas
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>



--
Best regards,
Andrii Sydorchuk
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [polygon] [GSOC] voronoi diagram of line segments

laurent.rineau__boost
In reply to this post by Dave Abrahams
Le dimanche 17 octobre 2010 11:01:08, David Abrahams a écrit :

> At Fri, 15 Oct 2010 19:54:07 -0700,
>
> Simonson, Lucanus J wrote:
> > I just wanted to update the boost dev community on the progress of
> > the GSOC project from this summer implementing voronoi diagram of
> > points and line segments, which leads to delauney triangulation,
> > medial axis of polygons and nearest neighbor.  The student has the
> > sweepline implementation of voronoi for line segments working for
> > several test cases and has provision in the code to handle numerical
> > robustness with the caveot that input coordinates must be integer.
> > I have attached an appealing screenshot showing the result produced
> > by the new code for a small test case.
>
> Hey, very appealing!  I have a soft place in my heart for
> computational geometry, but it's been a long time since I've studied
> it and I'd never seen a voronoi diagram for points *and* line segments
> before.  So (just guessing when I could look it up), every line
> segment gets a perpendicular line through its endpoints and the curved
> lines are equidistant between each line segment and its nearest
> point(s)?

There is an implementation of that class of diagram in CGAL:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Segment_Delaunay_graph_2/Chapter_main.html

It could be interresting to compare with.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
12