[pgrouting-dev] Question about improving alpha shapes

[Mario Basa]

Hi,

I already implemented the st_concavehull of PostGIS 2.0 into pgRouting, and
even with a low target_percent parameter (~0.8) the performance is still on
par with alpha shape.

It still needs clean up, but you can look at what I have done so far here:

https://github.com/mbasa/pgrouting

wherein I took away the alpha shape altogether in the wrapper sql files.

Mario.



On Thu, Aug 23, 2012 at 4:32 AM, Steve Horn <steve at stevehorn.cc> wrote:

> For what it's worth:
>
> Wouldn't get too excited about the PostGIS 2.0 implementation of
> st_concavehull. It does allow for more flexibility but I found it to be a
> couple orders of magnitude slower than the pgRouting (CGAL) implementation.
>
> On Wed, Aug 22, 2012 at 4:03 PM, Stephen Woodbridge <
> woodbri at swoodbridge.com> wrote:
>
>> Hello T,
>>
>> Lots of good questions.
>>
>> In general, as you found out, "One size fits all" solutions tend to not
>> work well for everyone. So I think have multiple solvers for various
>> problems is a good idea. In an ideal world, we would build things such that
>> they can be chained together, such that the output of one part can be fed
>> as input into the next part.
>>
>> So if we had something like:
>>
>> solve graph -> points with costs -> makealpha -> geometries
>>
>> Where makealpha could be any number of solutions like convex hulls,
>> concave hulls, your_code, etc
>>
>> In fact I have code the takes points with costs and makes a triangulated
>> surface and then slices that at z-levels and extracts geometries from that,
>> but not integrated into pgRouting at the moment.
>>
>> So, yes, contributions are welcome. Don't think of them as needing to be
>> exclusive of other existing solutions.
>>
>> Thanks,
>>   -Steve
>>
>>
>> On 8/22/2012 3:29 PM, T S wrote:
>>
>>> Hello,
>>>
>>> For some projects I've been working on, I've had to make some
>>> modifications to the alphashape method -
>>> namely, allowing a custom alpha instead of just picking the optimal
>>> regularly connected alpha, and allowing for disconnected multipolygons
>>> instead of only returning a single polygon.
>>>
>>> The use case that comes up is that some networks have holes or gaps in
>>> the 2d plane. I.e., driving over a bridge, you can get to the
>>> landmasses on either side of the bridge, but you can't really get to
>>> all the water around the bridge. This water shouldn't be included in
>>> the polygon.
>>>
>>> I have an initial implementation of how this works, I have a few
>>> questions about trying to contribute it in -
>>> 1.) Is there any interest in this feature? Or does pgRouting prefer
>>> the current behavior?
>>> 2.) I noticed an earlier email thread discussing moving to
>>> st_concavehull in postgis 2.0. While this would remove the dependency
>>> on CGAL, st_concavehull doesn't appear to support returning multiple
>>> disconnected geometries, and it's not really a true alpha shape.
>>> 3.) If there is interest in moving this in, where should I look to for
>>> coding standards, and which parts of the API are 'stable' and which
>>> aren't? in specific -
>>> 4) why does points_as_polygon return a setof geoms instead of just a
>>> geometry?
>>> 5) is it important for there to be both a points_as_polygon() and an
>>> alphashape() function, or could the functionality be rolled up?
>>>
>>> Thank you,
>>> T
>>>
>>>
>> ______________________________**_________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>
>
>
>
> --
> Steve Horn
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120823/739001fc/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: st_concavehull.png
Type: image/png
Size: 1056787 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120823/739001fc/attachment-0001.png>