<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
span.Shkpostityyli18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 2.0cm 70.85pt 2.0cm;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="FI" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:EN-US">Hi,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:EN-US"><br>
I did not know until today that SpatiaLite has also ST_ConcaveHull function <a href="https://www.gaia-gis.it/gaia-sins/spatialite-sql-latest.html">
https://www.gaia-gis.it/gaia-sins/spatialite-sql-latest.html</a> but I am glad that I know it now.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:EN-US">I digitized some points (concave.jml) for a test<br>
<img border="0" width="168" height="177" style="width:1.75in;height:1.8472in" id="Kuva_x0020_2" src="cid:image001.png@01D94FB8.5E7E69E0"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:EN-US">and then I used ogr2ogr and allowed ST_ConcaveHull to create holes<br>
<br>
ogr2ogr -f jml -dialect SQLite -sql "select ST_ConcaveHull(ST_Collect(geometry),3,1) from concave" out.jml concave.jml<br>
<br>
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:EN-US">and the result was<br>
<br>
<img border="0" width="167" height="177" style="width:1.743in;height:1.8472in" id="Kuva_x0020_3" src="cid:image003.png@01D94FB8.7A12A7C0"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:EN-US">For fine tuning you may want to add ST_Buffer into the SQL.<br>
<br>
-Jukka Rahkonen-<br>
<br>
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b>Lähettäjä:</b> Paul Meems <bontepaarden@gmail.com> <br>
<b>Lähetetty:</b> perjantai 3. maaliskuuta 2023 16.47<br>
<b>Vastaanottaja:</b> gdal-dev@lists.osgeo.org<br>
<b>Kopio:</b> Rahkonen Jukka <jukka.rahkonen@maanmittauslaitos.fi><br>
<b>Aihe:</b> Re: [gdal-dev] Convex hull with holes<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><span lang="EN-US">Thanks Jukka for your reply.<o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">I understand it is hard. <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">In my case, I have a lot of data points making your edge case not a problem for me.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">The data points are collected driving over a field with 1 or more sensors.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">The result can be something like this:<br>
</span><img border="0" width="228" height="810" style="width:2.375in;height:8.4375in" id="Kuva_x0020_1" src="cid:image002.png@01D94FB8.5E7E69E0"><span lang="EN-US"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">The red dots are the data points and I manually created the black border and added a small buffer.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">The red dots are transformed into polygons using inverse distance and afterward, I need to 'blank' the data using the black border.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">I can automate all steps except for creating this field border.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">I'm also struggling to get a proper name for my needs, making it harder to Google for a solution.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">'Convex hull' is not correct. What would be a more appropriate name?<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">Regards,<o:p></o:p></span></p>
</div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal"><span lang="EN-US"><br>
Paul<o:p></o:p></span></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<div>
<div>
<p class="MsoNormal"><span lang="EN-US">Op vr 3 mrt. 2023 om 14:13 schreef Rahkonen Jukka <</span><a href="mailto:jukka.rahkonen@maanmittauslaitos.fi"><span lang="EN-US">jukka.rahkonen@maanmittauslaitos.fi</span></a><span lang="EN-US">>:<o:p></o:p></span></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US">Hi,<o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US">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.<o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US">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.<o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">-Jukka Rahkonen-<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><b>Lähettäjä:</b> gdal-dev <<a href="mailto:gdal-dev-bounces@lists.osgeo.org" target="_blank">gdal-dev-bounces@lists.osgeo.org</a>>
<b>Puolesta </b>Paul Meems<br>
<b>Lähetetty:</b> perjantai 3. maaliskuuta 2023 14.52<br>
<b>Vastaanottaja:</b> <a href="mailto:gdal-dev@lists.osgeo.org" target="_blank">gdal-dev@lists.osgeo.org</a><br>
<b>Aihe:</b> [gdal-dev] Convex hull with holes<o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US">How can I algorithmically create a parcel border that accounts for islands or holes within the parcel based on a list of coordinates? <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US">While GDAL+GEOS has a Convex hull method, it only identifies the outer border. <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US">Has GDAL+GEOS a method that I can use to detect inner holes as well, such as in a donut-shaped field?<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US">The output can be json or shapefile, that doesn't matter.<br clear="all">
<o:p></o:p></span></p>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Thanks,<br>
<br>
Paul Meems<o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</body>
</html>