concave hull

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

concave hull

Jeremy Murphy
Hi there,

a year or so ago I brought up (I can't remember exactly with who or where) the possibility of contributing a concave hull algorithm and the good news is that I'm close to convincing my work to open-source an implementation I wrote.

To justify additional effort in preparing the code for release, they (senior leads) want to confirm that other people actually want it. I think that's hard for other people to give without seeing the actual code, but what I'm hoping for from the maintainers is just a non-binding "yes" that, in principle, you would be interested in an implementation of the concave hull algorithm described in the following paper:


There would be no obligation for you to accept or take custody of the code (obviously), they just want to know that we're not wasting our time preparing it. I originally wrote it with contribution in mind, so I really just need to do some polishing, make it respectable, etc.

Hope you're interested. Thanks, cheers.

Jeremy


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: concave hull

Adam Wulkiewicz
Hi Jeremy,

Jeremy Murphy wrote:
Hi there,

a year or so ago I brought up (I can't remember exactly with who or where) the possibility of contributing a concave hull algorithm and the good news is that I'm close to convincing my work to open-source an implementation I wrote.

To justify additional effort in preparing the code for release, they (senior leads) want to confirm that other people actually want it. I think that's hard for other people to give without seeing the actual code, but what I'm hoping for from the maintainers is just a non-binding "yes" that, in principle, you would be interested in an implementation of the concave hull algorithm described in the following paper:


There would be no obligation for you to accept or take custody of the code (obviously), they just want to know that we're not wasting our time preparing it. I originally wrote it with contribution in mind, so I really just need to do some polishing, make it respectable, etc.

I personally think that every contribution is welcome. There is no concave_hull() algorithm in Boost.Geometry and I think it would be a valuable addition. So it's a "yes" from me.
Barend, what do you think?
Are there any users which would find this addition welcome?

You probably already know this but just in case. We use certain conventions at Boost.Geometry. Every algorithm is divided into two parts, geometry-specific algorithm part dispatched by geometry tag and coordinate-system-specific strategies. In the case of convex_hull() the algorithm simply calls strategy which does everything. So I suppose it could be the same in this case.

As a part of your implementation have you used convex hull algorithm implemented in Boost.Geometry or have you implemented your own?

Regards,
Adam

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: concave hull

Barend
Hi Jeremy, Adam,



Op 1-6-2016 om 22:06 schreef Adam Wulkiewicz:
Hi Jeremy,

Jeremy Murphy wrote:
Hi there,

a year or so ago I brought up (I can't remember exactly with who or where) the possibility of contributing a concave hull algorithm and the good news is that I'm close to convincing my work to open-source an implementation I wrote.

To justify additional effort in preparing the code for release, they (senior leads) want to confirm that other people actually want it. I think that's hard for other people to give without seeing the actual code, but what I'm hoping for from the maintainers is just a non-binding "yes" that, in principle, you would be interested in an implementation of the concave hull algorithm described in the following paper:


There would be no obligation for you to accept or take custody of the code (obviously), they just want to know that we're not wasting our time preparing it. I originally wrote it with contribution in mind, so I really just need to do some polishing, make it respectable, etc.

I personally think that every contribution is welcome. There is no concave_hull() algorithm in Boost.Geometry and I think it would be a valuable addition. So it's a "yes" from me.
Barend, what do you think?

Yes, sure - thanks for the reminder, I indeed wanted to react on this. I also think that it is a very useful addition to our library. Actually in the past it has been asked for.


Are there any users which would find this addition welcome?

You probably already know this but just in case. We use certain conventions at Boost.Geometry. Every algorithm is divided into two parts, geometry-specific algorithm part dispatched by geometry tag and coordinate-system-specific strategies. In the case of convex_hull() the algorithm simply calls strategy which does everything. So I suppose it could be the same in this case.

As a part of your implementation have you used convex hull algorithm implemented in Boost.Geometry or have you implemented your own?

Regards, Barend


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: concave hull

Jeremy Murphy
In reply to this post by Adam Wulkiewicz
Hi Adam,

On 2 June 2016 at 06:06, Adam Wulkiewicz <[hidden email]> wrote:
Hi Jeremy,

I personally think that every contribution is welcome. There is no concave_hull() algorithm in Boost.Geometry and I think it would be a valuable addition. So it's a "yes" from me.
Barend, what do you think?
Are there any users which would find this addition welcome?

Thanks for the positive response.
I did receive one reply privately from a user that they were very interested in using it in an established library of their own.

 
You probably already know this but just in case. We use certain conventions at Boost.Geometry. Every algorithm is divided into two parts, geometry-specific algorithm part dispatched by geometry tag and coordinate-system-specific strategies. In the case of convex_hull() the algorithm simply calls strategy which does everything. So I suppose it could be the same in this case.

Although I had contribution in the back of my mind, it admittedly wasn't a priority, so I do have some work to do, including conversion from C++11. I'll base it on the existing convex_hull() implementation and see how it goes.

 
As a part of your implementation have you used convex hull algorithm implemented in Boost.Geometry or have you implemented your own?

I use the Boost.Geometry algorithm by default, but it's also designed to allow users to provide their own convex hull geometry.

Cheers.

Jeremy


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: concave hull

Jeremy Murphy
In reply to this post by Barend
Hi Barend,

On 2 June 2016 at 07:05, Barend Gehrels <[hidden email]> wrote:
Hi Jeremy, Adam,

Yes, sure - thanks for the reminder, I indeed wanted to react on this. I also think that it is a very useful addition to our library. Actually in the past it has been asked for.

Thanks for the positive response!

I don't follow the literature closely, but it seems to be an active area of research with several applications. So actually, thinking about the future, there could potentially be several concave hull strategies that have different output with regard to properties such as holes (cavities), guarantee of Jordan boundary (homeomorphic to a circle) and regularity.

Cheers.

Jeremy


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: concave hull

justinjk007
This post has NOT been accepted by the mailing list yet.
Hello there,

Was the algorithm ever implemented  and added to boost ?. If so Where is it. I couldn't find it in the algorithm section together with convex hull. I am using Boost 1.64 on windows platform.

Thank you very much