[Gvsig_english] QUESTION gvSIG 1.9 (BN 1253) -- Corrupted Polygon / Create new polygon using nodes

[Antonio Falciano]

Il 02/07/2010 12.58, Jorge Gaspar Sanz Salinas ha scritto:
> El 02/07/10 11:19, Antonio Falciano escribió:
>> Il 02/07/2010 9.45, Jorge Gaspar Sanz Salinas ha scritto:
>>> El 01/07/10 13:16, Antonio Falciano escribió:
>>>> Il 01/07/2010 12.30, Jorge Gaspar Sanz Salinas ha scritto:
>>>>> El 01/07/10 12:08, Antonio Falciano escribió:
>>>>>> Il 01/07/2010 10.56, Simon Cropper (Botanicus Australia Pty Ltd) ha scritto:
>>>>>>> Hi,
>>>>>>>
>>>>>>> I have inherited a polygon -- nodes in the polygon do not run
>>>>>>> sequentially from clockwise or anti-clockwise. This is throwing an error.
>>>>>>>
>>>>>>> I was able to extract the nodes from the polygon but have had problems
>>>>>>> finding the routine to create a new polygon using these points (there is
>>>>>>> no holes in the polygon).
>>>>>>>
>>>>>>> Can anyone please point me to a suitable routine?
>>>>>>
>>>>>> Hi Simon,
>>>>>> you can try with the SEXTANTE library: in detail, applying "Minimum
>>>>>> enclosing shapes" (Convex hull) on vertices and then subtract the more
>>>>>> external triangles (selected manually) computed with "Delauney
>>>>>> triangulation". This is a quite huge task, also known as "Concave hull".
>>>>>> I don't know if this problem has been solved in GFOSS world...
>>>>>> http://code.flickr.com/blog/2008/10/30/the-shape-of-alpha/
>>>>>> Cheers,
>>>>>> Antonio
>>>>>>
>>>>>
>>>>> Schuyler Erle developed for flickr a free software to create alpha
>>>>> shapes[1], but the trac/svn[2] is closed now...
>>>>>
>>>>> More info about the flickr project at [3]
>>>>>
>>>>> It would be great to have a SEXTANTE geoprocess for that, indeed.
>>>>>
>>>>> Best
>>>>>
>>>>> [1] http://biogeometry.duke.edu/software/alphashapes/index.html
>>>>> [2] http://code.flickr.com/trac/browser/trunk/clustr
>>>>> [3] http://code.flickr.com/blog/2008/10/30/the-shape-of-alpha/
>>>>
>>>> Hi Jorge,
>>>> I'm agree with you about the need of a such tool. Its algorithm is quite
>>>> complex, however there are a lot of interesting resources on the web [4]
>>>> or in the literature [5]. Furthermore, there are many possibilities to
>>>> obtain good approximations. For instance, see [6]. Maybe, with a good
>>>> SEXTANTE model or script it's possible to obtain something of useful.
>>>>
>>>> Cheers,
>>>> Antonio
>>>>
>>>> [4]
>>>> http://stackoverflow.com/questions/83593/is-there-an-efficient-algorithm-to-generate-a-2d-concave-hull
>>>> [5]
>>>> http://www.wipo.int/pctdb/en/wo.jsp?WO=2008107859&IA=IB2008050849&DISPLAY=DESC
>>>> [6] http://grass.osgeo.org/wiki/Create_concave_hull
>>>>
>>>
>>> Hi, thanks for the links Antonio.
>>>
>>> Schuyler finally pointed me to the current location of Clustr code at
>>> [1]. He told me that well, it's focused on Flickr needs but maybe can be
>>> interesting to someone else.
>>>
>>> BTW, two days ago I have nice developers workshop about SEXTANTE so just
>>> to do a matter of exercise I adapted (I mean, copy&pasted) some code
>>> posted at JTS mailing list [2] and created an algorithm.
>>>
>>> It's just a dirty hack and you have to do some "try and error" until you
>>> get something interesting but well, the results are not soy bad after
>>> all :-) [3].
>>>
>>> Cheers
>>>
>>> [1] http://github.com/straup/Clustr
>>> [2]
>>> http://jts-devel.219725.n2.nabble.com/polygonizer-and-line-strings-tp2572524p2591002.html
>>> [3] http://yfrog.com/7fe71p
>>>
>>
>> Hi Jorge,
>> your results are very interesting, congrats! The alpha shapes algorithm
>> [1] cited on JTS mailing list is relatively easy to understand and it
>> seem very effective in order to solve the problem. I'm looking forward
>> to test your new SEXTANTE geoalgorithm! ;)
>>
>> Cheers,
>> Antonio
>>
>> [1] http://www.isprs.org/proceedings/XXXVII/congress/3b_pdf/37.pdf
>>
>
> last shot :-)
>
> I've compiled clustr and the results seem pretty fine (as I expected).
>
> Using it is easy: you just provide it a text file with a tag (to
> categorize your clusters if you need) and a pair of long/lat values and
> it returns a shapefile of polygons. I've get that file from a shapefile
> with the gvSIG field calculator and some openoffice calc and text replace.

BTW, there are the "Spatial cluster" algorithm in SEXTANTE which allows to
create "clusters from an input points layer, grouping them according to
their spatial location" and the "Add coordinates to point" one.

> it don't deals with holes at this time
>
> and finally you can let it to calculate the optimal alpha value or
> provide it this parameter. some simple results:
>
> http://yfrog.com/5zzdmp
>
> If I would need to use that kind of geoprocess I would use Clustr at
> this time, but if anyone wants to improve my hack, the algorithm, along
> with the SEXTANTE workshop simple algorithms, are at:
>
> https://svn.prodevelop.es/public/labs/users/jsanz/sextante_algorithms/sextante_tests/

I have tested a bit your alg and it work like a charm! ;) It need only a
bit of code cleaning, nothing of transcendental!
It's clear that we have to play a bit with alpha value, however I think
this feature is better than calculate an optimal alpha value in order to
control the process. Awesome job!

Cheers,
Antonio

-- 
Antonio Falciano
http://www.linkedin.com/in/antoniofalciano