Re: [JPP-Devel] Difficult data for concave hull

2016-07-04 Thread Eric Grosso 
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  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 Tech Expo July 15-16. Meet us at AT 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
>
>

Re: [JPP-Devel] Difficult data for concave hull

2016-06-27 Thread Stefan Steiniger 
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 Tech Expo July 15-16. Meet us at AT 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 Tech Expo July 15-16. Meet us at AT 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 Tech Expo July 15-16. Meet us at AT 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 Tech Expo July 15-16. Meet us at AT 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

Re: [JPP-Devel] Difficult data for concave hull

2016-06-27 Thread Rahkonen Jukka (MML) 
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.

[cid:image001.png@01D1D0CE.3B482800]
And it may be that some users would expect the result to be something like
[cid:image003.png@01D1D0CE.9E1E95E0]
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.

[cid:image002.png@01D1D0CE.3B482800]

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 Tech Expo July 15-16. Meet us at AT 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 Tech Expo July 15-16. Meet us at AT 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 Tech Expo July 15-16. Meet us at AT 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

Re: [JPP-Devel] Difficult data for concave hull

2016-06-24 Thread Stefan Steiniger 

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 Tech Expo July 15-16. Meet us at AT 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 Tech Expo July 15-16. Meet us at AT 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 Tech Expo July 15-16. Meet us at AT 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

Re: [JPP-Devel] Difficult data for concave hull

2016-06-23 Thread Michaël Michaud 

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 Tech Expo July 15-16. Meet us at AT 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 Tech Expo July 15-16. Meet us at AT 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