[gdal-dev] Convex hull with holes

[Paul Meems]

Thanks Jukka for your reply.

I understand it is hard.
In my case, I have a lot of data points making your edge case not a problem
for me.
The data points are collected driving over a field with 1 or more sensors.
The result can be something like this:
[image: image.png]
The red dots are the data points and I manually created the black border
and added a small buffer.
The red dots are transformed into polygons using inverse distance and
afterward, I need to 'blank' the data using the black border.
I can automate all steps except for creating this field border.

I'm also struggling to get a proper name for my needs, making it harder to
Google for a solution.
'Convex hull' is not correct. What would be a more appropriate name?

Regards,

Paul

Op vr 3 mrt. 2023 om 14:13 schreef Rahkonen Jukka <
jukka.rahkonen at maanmittauslaitos.fi>:

> Hi,
>
>
>
> So you have an uncategorized bunch of points and you wish to have an
> algorithm that recognizes outer and inner rings automatically? I fear that
> is not as easy as it may appear. Have a look at the annexed image with two
> polygons having the same vertices. How could an algorithm know which
> interpretation is correct? In this simple case you could make a convex
> hull, delete the vertices which were consumed for the outer ring, and
> create a new ring from the remaining points, but generally it will not work
> if there are two holes, for example.
>
>
>
> If the points come from a GPX device, make the application to record
> indexes for both the points and the rings “ring1-point1,
> ring1-point2---ring2-point1,ring2-point2” and construct the polygon ring by
> ring.
>
>
>
> -Jukka Rahkonen-
>
>
>
> *Lähettäjä:* gdal-dev <gdal-dev-bounces at lists.osgeo.org> *Puolesta *Paul
> Meems
> *Lähetetty:* perjantai 3. maaliskuuta 2023 14.52
> *Vastaanottaja:* gdal-dev at lists.osgeo.org
> *Aihe:* [gdal-dev] Convex hull with holes
>
>
>
> How can I algorithmically create a parcel border that accounts for islands
> or holes within the parcel based on a list of coordinates?
>
>
>
> While GDAL+GEOS has a Convex hull method, it only identifies the outer
> border.
>
>
>
> Has GDAL+GEOS a method that I can use to detect inner holes as well, such
> as in a donut-shaped field?
>
>
>
> The output can be json or shapefile, that doesn't matter.
>
>
>
> Thanks,
>
> Paul Meems
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/gdal-dev/attachments/20230303/a51d9deb/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 28630 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/gdal-dev/attachments/20230303/a51d9deb/attachment-0001.png>