Re: [Boost-users] [boost.geometry] buffer distance strategies

Subject: Re: [Boost-users] [boost.geometry] buffer distance strategies
From: gchlebus (gchlebus_at_[hidden])
Date: 2015-01-27 08:17:52

Hi Barend,

2015-01-16 17:33 GMT+01:00 Grzegorz Chlebus <gchlebus_at_[hidden]>:

> Hi Barend,
>
> 2014-11-24 19:33 GMT+01:00 Barend Gehrels [via Boost] <
> ml-node+s2283326n4669451h8_at_[hidden]>:
>
>> Hi Grzegorz,
>>
>>
>> gchlebus wrote On 24-11-2014 11:06:
>>
>> Hallo Barend,
>>
>> 2014-11-13 22:07 GMT+01:00 Barend Gehrels [via Boost] <[hidden email]
>> <http:///user/SendEmail.jtp?type=node&node=4669423&i=0>>:
>>
>>> Hi Grzegorz,
>>>
>>>
>>> gchlebus wrote On 13-11-2014 18:39:
>>>
>>>  Hi Barend,
>>>
>>> 2014-11-12 22:21 GMT+01:00 Grzegorz Chlebus <[hidden email]
>>> <http://user/SendEmail.jtp?type=node&node=4669068&i=0>>:
>>>
>>>>
>>>>
>>>> 2014-11-12 22:07 GMT+01:00 Barend Gehrels [via Boost] <[hidden email]
>>>> <http://user/SendEmail.jtp?type=node&node=4669068&i=1>>:
>>>>
>>>>  Hi Grzegorz,
>>>>>
>>>>>
>>>>> gchlebus wrote On 12-11-2014 21:52:
>>>>>
>>>>>  2014-11-08 11:53 GMT+01:00 Barend Gehrels [via Boost] <[hidden email]
>>>>> <http://user/SendEmail.jtp?type=node&node=4669040&i=0>>:
>>>>>
>>>>>  Gu Grzegorz,
>>>>>>
>>>>>> gchlebus wrote On 8-11-2014 2:33:
>>>>>>
>>>>>>
>>>>>> 2014-11-07 19:30 GMT+01:00 Barend Gehrels [via Boost] <[hidden email]
>>>>>> <http://user/SendEmail.jtp?type=node&node=4668825&i=0>>:
>>>>>>
>>>>>>  Hi Grzegorz,
>>>>>>>
>>>>>>> gchlebus wrote On 6-11-2014 19:08:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> 2014-11-04 17:23 GMT+01:00 Barend Gehrels [via Boost] <[hidden
>>>>>>> email] <http://user/SendEmail.jtp?type=node&node=4668774&i=0>>:
>>>>>>>
>>>>>>>  Hi Grzegorz,
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> 2014-10-29 23:18 GMT+01:00 Barend Gehrels [via Boost] <[hidden
>>>>>>>> email] <http://user/SendEmail.jtp?type=node&node=4668617&i=0>>:
>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> gchlebus wrote On 24-10-2014 16:44:
>>>>>>>>>
>>>>>>>>> > Hi,
>>>>>>>>> >
>>>>>>>>> > I am wondering whether it would be possible to achieve
>>>>>>>>> anisotropic buffering
>>>>>>>>> > (distances in neg x, pos x, neg y, pos y can have different
>>>>>>>>> values) of a
>>>>>>>>> > polygon using the buffer function with custom-implemented
>>>>>>>>> distance strategy.
>>>>>>>>> > What I want to achieve is presented on the figure 2-b in the
>>>>>>>>> following
>>>>>>>>> > paper:
>>>>>>>>> >
>>>>>>>>> http://itcnt05.itc.nl/agile_old/Conference/mallorca2002/proceedings/posters/p_molina.pdf
>>>>>>>>> >
>>>>>>>>> > I would be grateful to hear from you whether it is doable, and
>>>>>>>>> if positive,
>>>>>>>>> > how one could implement such a custom distance strategy.
>>>>>>>>>  The current distance strategy has (currently) no means to get the
>>>>>>>>> angle,
>>>>>>>>> or a vector of the new point to be buffered. We can consider
>>>>>>>>> adding that.
>>>>>>>>>
>>>>>>>>> However, by writing custom strategies for join, side, point (for
>>>>>>>>> point-buffers) and possibly end (for line-buffers) you should be
>>>>>>>>> able to
>>>>>>>>> create this, because these have this information.
>>>>>>>>>
>>>>>>>>> Attached a program doing similar things with polygons and points
>>>>>>>>> (I vary
>>>>>>>>> the distance based on angle - you will have to do something with
>>>>>>>>> your
>>>>>>>>> anistropic model).
>>>>>>>>>
>>>>>>>>> The output is also attached.
>>>>>>>>>
>>>>>>>>> The program defines three custom strategies, all based on the same
>>>>>>>>> mechanism, to create interesting output.
>>>>>>>>> I did not do the end-strategy but that would look similar, you can
>>>>>>>>> look
>>>>>>>>> at the provided end-strategy (round) and apply the same function.
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> gchlebus wrote On 31-10-2014 18:13:
>>>>>>>>
>>>>>>>> I really appreciate your example code, it helped me a lot. Attached
>>>>>>>> you can find my source code.
>>>>>>>> In my implementation of the anisotropic buffering I didn't know how
>>>>>>>> to make use of the distance strategy, as it was possible to make it work
>>>>>>>> using only side and join strategies.
>>>>>>>> I encountered strange behavior when changing number of points
>>>>>>>> describing a full circle. Using 360 points produced a good output, whereas
>>>>>>>> 90 points caused only the second polygon to be buffered (see attached
>>>>>>>> figures). I would be thankful if you could help me to resolve this issue as
>>>>>>>> well as for any remarks to my code.
>>>>>>>>
>>>>>>>>
>>>>>>>>  I could reproduce this. Basically the join-strategy should always
>>>>>>>> include points perp1 and perp2 (these are the two points perpendicular to
>>>>>>>> the two sides which the join-strategy joints). Either they are
>>>>>>>> re-calculated, or they can be just added to begin and end. So I did the
>>>>>>>> last option, and that piece of code now looks like:
>>>>>>>>
>>>>>>>>       double const angle_increment = 2.0 * M_PI /
>>>>>>>> double(point_count);
>>>>>>>>       double alpha = angle1 - angle_increment;
>>>>>>>> *      range_out.push_back(perp1);*
>>>>>>>> * // added *      for (int i = 0; alpha >= angle2 && i <
>>>>>>>> point_count; i++, alpha -= angle_increment)
>>>>>>>>       {
>>>>>>>>         pdd v = getPointOnEllipse(alpha);
>>>>>>>>         Point p;
>>>>>>>>         bg::set<0>(p, bg::get<0>(vertex) + v.first);
>>>>>>>>         bg::set<1>(p, bg::get<1>(vertex) + v.second);
>>>>>>>>         range_out.push_back(p);
>>>>>>>>       }
>>>>>>>> *      range_out.push_back(perp2);** // added*
>>>>>>>>
>>>>>>>> My sample code of course also suffered from that, so I added it
>>>>>>>> there too if I use it in the future.
>>>>>>>>
>>>>>>>> I tested your algorithm with various points and distances and it
>>>>>>>> now seems always OK.
>>>>>>>>
>>>>>>>> You ask for remarks on your code: it looks good ;-) one thing, many
>>>>>>>> terms are recalculated such as pow(xPos*tan(alpha), 2)); or just
>>>>>>>> tan(alpha), I usually store these into variables, to avoid expensive
>>>>>>>> recalculations of the same terms, though maybe they are optimized by the
>>>>>>>> compiler.
>>>>>>>>
>>>>>>>> Regards, Barend
>>>>>>>>
>>>>>>>>
>>>>>>>> P.S. this list discourages top-postings
>>>>>>>>
>>>>>>>>
>>>>>>>  Hallo Barend,
>>>>>>>
>>>>>>>  I corrected the join strategy, but still the buffering doesn't
>>>>>>> work in all cases as expected. When using xPos = 1, and other values equal
>>>>>>> 0, the buffered polygon contains a hole (see xPos1.svg), whereas setting
>>>>>>> xPos to 2 produces a correct result (xPos2.svg). Do you know how to fix it?
>>>>>>> I attached also main.cpp, as I changed the code a bit and it contains the
>>>>>>> polygon for which causes the strange behavior.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> That is most probably caused by an error in some of your
>>>>>>> calculations:
>>>>>>>
>>>>>>> The line y = sqrt(yPos2 * (1 - pow(x, 2) / xNeg2));
>>>>>>> causes a NAN for this input:
>>>>>>>
>>>>>>> alpha about PI
>>>>>>> then xNeg2 = 0.010000000000000002
>>>>>>> and x = -0.10000000000000002
>>>>>>> and yPos2 = 0.010000000000000002
>>>>>>>
>>>>>>> This adds a weird line containing NAN to the join, causing the
>>>>>>> buffer process fail.
>>>>>>> I got this using these parameters:
>>>>>>> double xPos = 1.0, xNeg = 0.1, yPos = 0.1, yNeg = 0.1;
>>>>>>>
>>>>>>> and not the parameters you have (that was fine for me).
>>>>>>>
>>>>>>> I think you should make the calculations full-proof first...
>>>>>>>
>>>>>>> For example add a line in the join-strategy:
>>>>>>>         std::cout << i << " "<< angle1 << " " << angle2 << " " <<
>>>>>>> v.first << " " << v.second << std::endl;
>>>>>>>
>>>>>>>
>>>>>>> Regards, Barend
>>>>>>>
>>>>>>>
>>>>>>  Thanks, I'll try to improve my calculations.
>>>>>> By the way, I was playing with different strategies combinations and
>>>>>> I found out that when using only boost buffer strategies:
>>>>>>
>>>>>>         double points_per_circle = 36;
>>>>>>         double distance = 130;
>>>>>>         bg::strategy::buffer::distance_symmetric<double>
>>>>>> distance_strategy(distance);
>>>>>>  bg::strategy::buffer::end_flat end_strategy;
>>>>>>  bg::strategy::buffer::point_circle point_strat(points_per_circle);
>>>>>>  bg::strategy::buffer::side_straight sideStrat;
>>>>>>  bg::strategy::buffer::join_round joinStrat(points_per_circle);
>>>>>>
>>>>>>  the buffer function can still fail (produce no output) when the
>>>>>> distance is higher than 128 (e.g, 128, 130, 150, 300, 400). But this
>>>>>> happens up to a certain value, where the buffer function starts producing a
>>>>>> correct output (e.g., distances 900, 1000).
>>>>>>
>>>>>>
>>>>>> Hmm, I see (starting at different values, but I can reproduce).
>>>>>>
>>>>>> I created a ticket, will be looked at. Thanks for reporting.
>>>>>> https://svn.boost.org/trac/boost/ticket/10770
>>>>>>
>>>>>> Barend
>>>>>>
>>>>>>
>>>>>  Hi Barend,
>>>>>
>>>>>  I'm glad that I could help.
>>>>> Anyway, I fixed the bug with NAN, but still when using (e.g. xNeg = 1,
>>>>> other 0) the buffer produces no output. I am really wondering, how it could
>>>>> work on your machine.
>>>>> I printed the values used by join and side strategies and they seem to
>>>>> be fine (no NANs or other strange values) - see attached log.txt and
>>>>> updated main.cpp used to produce the log file.
>>>>>
>>>>>  I've compiled my code using msvc 12.0 and gcc 4.8.
>>>>>
>>>>>
>>>>> Which branch or version of Boost do you use?
>>>>>
>>>>> In the meantime, I managed to fix the bug you reported, and it is
>>>>> committed today.
>>>>>
>>>>> Sorry for my question, but could you try it again with the latest
>>>>> branch "develop" from github ?
>>>>>
>>>>> Regards, Barend
>>>>>
>>>>>
>>>>
>>>>  Hi Barend,
>>>>
>>>>  sure, I downloaded the geometry lib from the develop branch, but
>>>> still buffer returns an empty geometry (using xNeg = 1, others 0).
>>>> I've ran my code also for big distances, and it works perfectly. Good
>>>> job!
>>>>
>>>>  Best,
>>>>  Grzegorz
>>>>
>>>
>>>   I made today an interesting observation. It seems that the buffer
>>> function has a problem when the extents (xNeg, xPos, yNeg, yPos) are zero.
>>> Taking my last example, setting xNeg to 1 and others to 1e-3 makes the
>>> buffer work.
>>>
>>>
>>>
>>> Sure - thanks for sending me, that saves me time to find it out.
>>> Buffer-distance 0 is not supported (yet). Some GIS packages use that to
>>> clean a polygon, but we have designed dissolve for that. We might support
>>> it later but currently, indeed, as you found out, it will not work. I hope
>>> small distances are OK for your application, for now.
>>>
>>> Negative distances should work if used in the distance-policy, making
>>> the polygon smaller, but I don't think that it will work currently out of
>>> the box if you mix negative and positive distances in one join-strategy...
>>>
>>> Regards, Barend
>>>
>>
>>  with small adjustment I made also shrinking possible, but I had to do
>> this in a not very clean way. I had to add to the join strategy additional
>> bool parameter in order to know whether shrinking or expanding should be
>> performed. Do you have any idea how one could find out inside the join
>> strategy whether the structure is being shrunk or expanded? For example in
>> side strategy one of the parameters is distance strategy, which can tell me
>> whether it's negative or positive.
>>
>>
>> Yes but these strategies are used differently. join-strategy is only
>> called for convex joins. If a join is concave, internally another piece is
>> created, there is no strategy for that (from user-perspective you don't see
>> anything because the sides intersect and the concave piece disappears).
>>
>> Now for a shrink/deflate operation, the polygon is walked reversily, so
>> counter-clockwise (if your polygons are clockwise). What is then a concave
>> configuration becomes convex, and v.v. so your join-strategy is then only
>> called for concave turns, creating the join on the inside. The convex turn
>> gets then nothing visible.
>>
>> For your operation I believe it becomes more complex then because the
>> angle is different. In the next version we will add some more info to the
>> apply method of the strategy such that you can more easily detect this, and
>> that probably will also solve this problem.
>>
>> Besides that, I have no problem to add the distance-strategy there too,
>> that is a good idea and makes the strategies more similar.
>>
>>
>>
>>  Btw, I'm just wondering how complex it would be to allow zero distances?
>>
>>
>> Yes, that is complex but in the future we will work on it. But that won't
>> be next version.
>>
>> Regards, Barend
>>
>
>
> In the meantime I managed to alter the code to make it possible to shrink
> the input polygons anisotropically as well.
> Unfortunately I found that the temporary solution with constraining the
> extent values (xNeg, xPos, yNeg, yPos) to be bigger than 0 doesn't work in
> all cases. I observed two behaviors:
> 1. spikes/lines appears (see case1.svg)
> 2. the buffered function fails, i.e. no polygon is outputted
>
> I tired to debug the code and I couldn't find anyting wrong on my side of
> code. In case 2 I found out that in the traverse::apply function which is
> called from withing boost::geometry::buffer 2 polygons are created instead
> of only one. Due to the complexity of the code I wasn't able to get to know
> what exactly causes this behavior, so I decided to turn with this question
> to you. I'd really appreciate your help.
>
> Attached source code illustrating above mentioned behaviors. I'm using
> boost 1.57 on VC12.
>
> Best,
> Grzegorz
>
>

 have you maybe found time to investigate my problem? I'd be really
greatful for your help.

Best,
Grzegorz

--
View this message in context: http://boost.2283326.n4.nabble.com/boost-geometry-buffer-distance-strategies-tp4668469p4671721.html
Sent from the Boost - Users mailing list archive at Nabble.com.