Boost logo

Boost Users :

Subject: Re: [Boost-users] [boost.geometry] buffer distance strategies
From: Barend Gehrels (barend_at_[hidden])
Date: 2015-01-28 07:20:07


Hi Grzegorz,

gchlebus schreef op 16-1-2015 om 17:32:
> Hi Barend,
>
> 2014-11-24 19:33 GMT+01:00 Barend Gehrels [via Boost] <[hidden email]
> </user/SendEmail.jtp?type=node&node=4671252&i=0>>:
>
> 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.
> 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) Download Attachment
> <http://boost.2283326.n4.nabble.com/attachment/4671252/0/case1.svg>
> *PolygonBuffer.zip* (10K) Download Attachment
> <http://boost.2283326.n4.nabble.com/attachment/4671252/1/PolygonBuffer.zip>
>

Thanks for the report and your reminder - I will have a look.

Regards, Barend



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