Hi Michaël, Jukka and Stefan, Sorry for this late reply.
Michaël is right. At the moment, it creates a simple and single polygon as described in Duckham et al.'s paper. It'd be possible to extend the current algorithm to create, if needed, several concave polygons as a result. Spatial clusters would be created first, then for each of them, a concave hull would be computed. The clustering could be created quite easily on top of the existing triangulation but I can't see (at least for now) an easy way to create a concave hull for each cluster without using the concave hull algorithm for each of them separately. Nevertheless, Jukka's case is a bit tricky (because of the polygon in the middle) and I don't think the concave hull algorithm is well adapted in this context, even if using a threshold of 116-117 (see attached jml file -- I densified manually the number of vertices of the original polygons), it gives an approximate result. To obtain the result proposed by Jukka (which is what as users, we can expect "naturally"), there would be the need to create another algorithm whose the aim would be to create a concave hull (remark: many concave hulls can be defined, contrary to the convex hull which is unique) with the smallest area using only their original vertices (it would also be based on a triangulation). But I'm not sure this is the kind of algorithm which would be used on a daily basis. FYI, there is a very interesting report which deals with the concave hull problem and how to compute it using some parallelisation: http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project10/Project-10-report.pdf The example given in page 29 shows the same kind of problem encountered in Jukka's example. FYI (bis), I'm aware of some minor problems with the current algorithm which are relatively easy to fix (e.g. need to add the case where the input geometry contains only 3 points and to return the related triangle or a segment if the 3 points are aligned -- the other cases are very specific, e.g. all the points are aligned, etc.). But all the feedbacks I received about the implementation were all very positive (efficiency, running time, etc.). I hope that I'll find some time next year to improve it and to release a second version, including at least the possibility to create a concave hull for each cluster, to allow visually the choice of the threshold (it's possible as the time complexity is related to the triangulation not to the concave hull algorithm). Cheers, Eric On 28 June 2016 at 00:58, Stefan Steiniger <sst...@geo.uzh.ch> wrote: > thanks for explaining Jukka! Makes sense. But how to implement that... > phewww... not sure. > > On 6/27/16 17:54, Rahkonen Jukka (MML) wrote: > > Hi Stefan, > > > > Actually the issue was that without playing with densification and > tolerance (which is documented) the result did contain all the vertices but > not the whole area of the polygons. > > > > And it may be that some users would expect the result to be something like > > I guess that it is hard to define how the result should be as a basis for > the algorithm. Perhaps “follow the shapes as closely as possible while > keeping the perimeter of the linear ring below threshold []. > > > > -Jukka Rahkonen- > > > > > > Stefan Steiniger wrote: > > > > Hi, > > actually the question is: What do you expect for a result, Jukka? The > picture by Michaël seems reasonable to me and I wonder how it should look > for you. > > cheers., > Stefan > > On 6/23/16 17:30, Michaël Michaud wrote: > > Hi Jukka, > > As far as I remember (I did not find confirmation in Eric's > documentation), the algorithm produces a single polygon. > > In your case, there are several input polygons. If you densify their > boundaries, you'll get something close to the original polygons, but with > narrow corridors to rely them. I think this is a limitation of the > algorithm rather than a bug. Here is what I get with a densification of 1m. > Would be interesting to overcome this limitation though. > > > > Le 23/06/2016 à 14:50, Rahkonen Jukka (MML) a écrit : > > Hi, > > > > I was playing with the Concave hull plugin and got usually good results. > However, the attached data gives odd results even if I followed the hint to > densify the geometries. Sending to the list if some developers happens to > be interested in having a look. > > > > -Jukka Rahkonen- > > > > > ------------------------------------------------------------------------------ > > Attend Shape: An AT&T Tech Expo July 15-16. Meet us at AT&T Park in San > > Francisco, CA to explore cutting-edge tech and listen to tech luminaries > > present their vision of the future. This family event has something for > > everyone, including kids. Get more information and register today. > > http://sdm.link/attshape > > > > > _______________________________________________ > > Jump-pilot-devel mailing list > > Jump-pilot-devel@lists.sourceforge.net > > https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel > > > > > > ------------------------------------------------------------------------------ > > Attend Shape: An AT&T Tech Expo July 15-16. Meet us at AT&T Park in San > > Francisco, CA to explore cutting-edge tech and listen to tech luminaries > > present their vision of the future. This family event has something for > > everyone, including kids. Get more information and register today. > > http://sdm.link/attshape > > > > > _______________________________________________ > > Jump-pilot-devel mailing list > > Jump-pilot-devel@lists.sourceforge.net > > https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel > > > > > ------------------------------------------------------------------------------ > Attend Shape: An AT&T Tech Expo July 15-16. Meet us at AT&T Park in San > Francisco, CA to explore cutting-edge tech and listen to tech luminaries > present their vision of the future. This family event has something for > everyone, including kids. Get more information and register > today.http://sdm.link/attshape > > > > _______________________________________________ > Jump-pilot-devel mailing > listJump-pilot-devel@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/jump-pilot-devel > > > > > ------------------------------------------------------------------------------ > Attend Shape: An AT&T Tech Expo July 15-16. Meet us at AT&T Park in San > Francisco, CA to explore cutting-edge tech and listen to tech luminaries > present their vision of the future. This family event has something for > everyone, including kids. Get more information and register today. > http://sdm.link/attshape > _______________________________________________ > Jump-pilot-devel mailing list > Jump-pilot-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel > >
concave_problem_concave_hull.jml
Description: Binary data
------------------------------------------------------------------------------ Attend Shape: An AT&T Tech Expo July 15-16. Meet us at AT&T Park in San Francisco, CA to explore cutting-edge tech and listen to tech luminaries present their vision of the future. This family event has something for everyone, including kids. Get more information and register today. http://sdm.link/attshape
_______________________________________________ Jump-pilot-devel mailing list Jump-pilot-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
