[pgrouting-dev] Question about improving alpha shapes

[T_S]

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

--
from talin
      "it's not stupid. it's advanced."

[Stephen_Woodbridge1]

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

[Steve_Horn]

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@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Steve Horn

[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@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@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Steve Horn

---

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

[Mario_Basa]

I forgot to add, st_concavehull also does holes quite nicely.

see attached screen dump.

Mario.

On Thu, Aug 23, 2012 at 4:32 AM, Steve Horn <steve@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@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

–
Steve Horn

---

pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev