[gdal-dev] Countour polygons instead of lines

[Vincent Mora]

Le 20/10/2017 à 20:18, Andrew C Aitchison a écrit :
> On Fri, 20 Oct 2017, Vincent Mora wrote:
>
>> I'll also try the gdal_polygonize approach, but I don't think it's the
>> same thingl: with raster-classif + gdal_polygonize, if you have 3
>> classes 1,2,3 polygons from 1 can touch a polygon from 3, with contour
>> lines there will always be a polygon of class 2 in between.
>>
>> Or am I missing something.
>>
>> If someone believes I'm doing something useless and/or stupid (that also
>> happens), please do tell.
>
> Can you polygonize contours across a vertical cliff ?
> If so, 2 may be "between" 1 and 3, but at some points they may all touch.
>
> On some maps, contours become discontinuous around cliffs and quarries.
>
This is a mapper trick: the levelset algorithm will create line that are
very close to one another, but never touching (safe for numerical
precision).

The algorithm considers the raster grid as **continuous** field, so
vertical/overhanging cliffs cannot be modeled (you need 3D for that).

Those properties give us the opportunity to make some optimization, if
I'm note mistaken:
- any contour that closes on the border cannot be a hole, so you don't
need to check them, and in a lot of cases that's a lot of polygons, and
the big ones (I'm thinking contours for other values than altitude, like
temperature)
- for contours that don't close on border, if they are oriented
counterclockwise,they are holes, so the problem is to find which hole
belongs to which outer ring.

The later is not a fast algorithm in the general case. Especially with
elongated polygons that screw up spatial indexes. You need to do a point
in polygon for each hole point. But since we know that contour lines
never cross, then if one hole point is in the polygon, then the hole is
in the polygon.

I'm no sure you need to test for outer ring / outer ring inclusion (ring
islands), because the hole belongs to the smallest area outer ring that
includes one of its points. This makes me realize that the first
optimization I mentioned may not be useful if we need surface area.

I don't have all the details figured out, but I have good hope for an
efficient algorithm.

Cheers,

V.