Boost logo

Boost Users :

Subject: Re: [Boost-users] [boost.geometry] buffer distance strategies
From: gchlebus (gchlebus_at_[hidden])
Date: 2015-01-16 11:32:05


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
>
>
>
> _______________________________________________
> Boost-users mailing list
> [hidden email] <http:///user/SendEmail.jtp?type=node&node=4669451&i=0>
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
> ------------------------------
> If you reply to this email, your message will be added to the discussion
> below:
>
> http://boost.2283326.n4.nabble.com/boost-geometry-buffer-distance-strategies-tp4668469p4669451.html
> To unsubscribe from [boost.geometry] buffer distance strategies, click
> here
> <http://boost.2283326.n4.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4668469&code=Z2NobGVidXNAZ21haWwuY29tfDQ2Njg0Njl8LTExMTg0ODQ4MTY=>
> .
> NAML
> <http://boost.2283326.n4.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
>

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

case1.svg (2K) <http://boost.2283326.n4.nabble.com/attachment/4671252/0/case1.svg>
PolygonBuffer.zip (10K) <http://boost.2283326.n4.nabble.com/attachment/4671252/1/PolygonBuffer.zip>

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net