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

[Jorge Gaspar Sanz Salinas]

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.

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/


best

-- 
Jorge Gaspar Sanz Salinas
gvSIG Team at Prodevelop
Technical Collaborations Manager
http://www.gvsig.org
http://www.gvsig.com