Overlapped polygons when using TopoGeo_ToGeoTableGeneralize

[Alessandro Donati]

Hi Sandro,

Hope you can help me investigate a problem I'm experiencing with rttopo simplification through spatialite 4.50-dev.
The source dataset represents high res depth areas, which I can successfully import (TopoGeo_FromGeoTable).
When I call TopoGeo_ToGeoTableGeneralize using higher tolerance than the source data resolution (for example, I have depth areas as close as 0.8 m, and I use a tolerance radius of 1.0 m), I find some overlapped polygons in the resulting geotable.
Is this something you would expect or a problem to report to rttopo developers?
The attached picture "source" shows the input dataset, while "overlapped" shows the output geotable generalized at 1.0 m. If I click on the center of the dataset where I expect to find just the innermost polygon, I find several polygons overlapping each others.
Hope you can offer some insight

Thanks in advance

Ciao
Alessandro

[Alessandro Donati]

This one with attachments..

[a.fu...@lqt.it]

ciao Alessandro,

I've investigated your problem and here are my considerations.

There are _TWO_ different ways to represent a set of contour
lines (as the ones shown in your pictures).

a) by representing geometries as LINESTRINGs (may be of the
closed type as a special case, but it doesn't matter).
b) by representing geometries as POLYGONs (and in this
second case all rings _must_ be necessarily closed).

Building a Topology from the one of from the other will
lead to identical results, because both linestrings
and polygons' rings will be crushed into Edges, and
then Faces will be built accordingly to Edges.

However the type of SFS geometries (Linestring or
Polygon) will have a strong influence when calling
both TopoGeo_ToGeoTable() and TopoGeo_ToGeoTableGeneralize():

1. if the reference table is of the Linestring type
the output table as well will be created as
Linestrings; and only the Edges matching one of
the input Linestrings will be exported into the
output table.
If more Edges will spatially match a single
input Linestring they'll be then merged
altogether.

2. if the reference table is of the Polygon type
the output table will be Polygons; and in this
case all Faces spatially matching one of the
input Polygons will be exported into the output.
If more Faces will match a single input Polygon
they'll be then merged altogether.

Basing my opinion on your pictures, your input
dataset seems to be of the Polygon type.
So there is no "anomaly" at all in your Generalize
results; they are exactly what they are expected
to be.

-----

If (for any good reason) you really intend to
export an output table containing "closed
ribbons" precisely delimited by a couple of
contour lines (see attached figure), you have
to adopt a different approach:

CREATE TABLE ribbons AS
SELECT face_id, ST_GetFaceGeometry('test', face_id) AS geom
FROM topology_face
WHERE face_id > 0;
SELECT RecoverGeometryColumn('ribbons', 'geom', 3003,
'POLYGON', 'XY');

- you have first to "materialize" all the Faces
from your Topology into an ordinary Spatial
Table.
- and then you simply have to pass this table
to TopoGeo_ToGeoTableGeneralize() as the
reference table.

saluti, Sandro

[Alessandro Donati]

Ciao Sandro,

your assumption about the layer being POLYGON is correct, even if (pls forgive me) I miss the difference with it being LINESTRING, since either Faces or Edges might end up as being merged as you say. Can you also clarify "If more Faces will match a single input Polygon they'll be then merged altogether", what are the criteria of the spatial match?

Following your advice about ribbons, I have tried this:

CREATE TABLE ribbons AS
SELECT face_id, ST_GetFaceGeometry('topo', face_id) AS geom
FROM topo_face
WHERE face_id > 0;
SELECT RecoverGeometryColumn('ribbons', 'geom', -1, 'POLYGON', 'XY');
SELECT TopoGeo_ToGeoTableGeneralize('topo', 'main', 'ribbons', NULL, 'out_ribbons_1.0m', 1.0);

but the resulting 'out_ribbons_1.0m' geotable still suffers of the same problem, see the attached picture. I've set a transparent color, so you can appreciate overlapping (darker blue)

A few questions more:

- What is 'WHERE face_id > 0;' supposed to filter out? I might be wrong, but 'out_ribbons_1.0m' appears to include all areas that were in the original geotable.
- Why do I need specialized queries to get what TopoGeo_ToGeoTableGeneralize per se should be able to obtain? The documentation says it should preserve the topology. I expect the simplifier, aided by the topology, should realize that the outer ring of polygon A matches an inner of polygon B, and preserve this relationship after simplification. If not, limited to my use case, why should I build a topology at all?
- Can you explain the rationale of TopoGeo_ToGeoTableGeneralize? Is it doing bare simplification (keep feature counting, just reduce number of points of each feature) or real generalization? In the latter case, it might decide to remove/merge some features, but I need to know what's the criteria and how the attributes of the reference table are migrated into the generalized one.

To be clearer on my expectations, either of the two would be OK for me
1) features are simplified, not removed. No problem because I get the simplification (fewer points) and I don't miss attributes.
2) features are generalized, and some of them might be removed, not merged. Same as above, that's OK because geometries are simpler and attributes are preserved.

Thank you in advance

Ciao
Alessandro

[a.fu...@lqt.it]

Alessandro,

I suppose there is some misunderstanding about what TopoGeo_ToGeoTable
and TopoGeo_ToGeoTableGeneralize are really intended to be.

We'll start first by examining the simpler case of _ToGeoTable:
a. we have some Topology based on Edges and Faces.
b. and we have an external table (reference) containing simple
features with their related attributes.
c. a third table (output) will be then created, containing
geometries directly based on Topology primitives but
preserving the attributes defined in the reference table.
d. the output table will always have the same geometry type
of the reference table.
this practically means that just the Edges will be considered
when processing a Linestring reference, and Faces will be
considered when processing a Polygon reference.
e. we are not necessarily expecting that input geometries
must exactly match Topology primitives, so a loose
spatial matching will be checked, based on SEEDS.
You'll find a more detailed explanation about EdgeSeeds
and FaceSeeds here:

https://www.gaia-gis.it/fossil/libspatialite/wiki?name=topo-intermediate
d. we must expect that a single reference feature matches
many Topology Primitives. in this case all them will be
merged together.

_ToGeoTableGeneralize follows the same identical data flow,
with just a little difference; all Edges will be temporarily
simplified by applying the Douglas-Peucker algorithm.

coming to your specific case: you are using a reference table
composed by Polygons lacking any interior hole.
each polygon has an exterior ring corresponding to some
contour line, and partially overlaps many further polygons
representing upper and lower elevations.
under such conditions both _ToGeoTable and _ToGeoTableGeneralize
will always return output polygons with no interior holes,
just because many Faces will spatially match the input geom
and all the matching Faces will be merged together.

the most obvious solution for simplifying a set of contour
lines seems the one to represent them as Linestrings.
if you really want to represent them as Polygons you
must then accept that the output polygons do overlap
(exactly as it happens in the given reference table).
and finally, if you absolutely want to get a "ribbon
style" output table you necessarily have to export
someway the Faces out from Topology.

----------

passing to your other questions:

> - What is 'WHERE face_id > 0;' supposed to filter out?
>

this is strictly dictated by ISO Topology foundations;
Face ID=0 identifies "the Universe", and can never ever
be directly referenced, or a nasty exception will be
immediately raised.

> - Why do I need specialized queries to get what
> TopoGeo_ToGeoTableGeneralize per se should be able to obtain? The
> documentation says it should preserve the topology. I expect the
> simplifier, aided by the topology, should realize that the outer ring
> of polygon A matches an inner of polygon B, and preserve this
> relationship after simplification.
>

Absolutely no.
as explained before both ToGeoTable and ToGeoTableGeneralize
just collect all Faces spatially matching (via FaceSeeds) each
one of the input Polygons.
You can eventually rearrange your reference table so to "realize

that the outer ring of polygon A matches an inner of polygon B"

but this surely requires some explicit extra processing (nothing
exceptionally difficult anyway).

> If not, limited to my use case, why should I build a topology at all?
>

I agree: deploying a full Topology just for simplifying a
set of contour lines seems to be kind of an overkill.

> - Can you explain the rationale of TopoGeo_ToGeoTableGeneralize? Is
> it
> doing bare simplification (keep feature counting, just reduce number
> of points of each feature) or real generalization? In the latter
> case,
> it might decide to remove/merge some features, but I need to know
> what's the criteria and how the attributes of the reference table are
> migrated into the generalized one.
>

short answer: they do bare simplification.
long answer: both _ToGeoTable and _ToGeoTableGeneralize strictly
respects the reference table.
the geometries will be reworked so to match Topology Primitives
(may be after applying Douglas-Peucker simplification), but no
feature will be never removed or added for any reason.
it could be eventually be that someone of the output geoms
will be NULL: it happens when the input geometry doesn't
match any corresponding Topology Primitive.

bye Sandro

[Alessandro Donati]

Ciao Sandro,

thanks for your clarifications, I'll go straight to remaining doubts

coming to your specific case: you are using a reference table
composed by Polygons lacking any interior hole.
each polygon has an exterior ring corresponding to some
contour line, and partially overlaps many further polygons
representing upper and lower elevations.

That's not true, and is the key point.
Polygons in the reference table do not overlap, they have outer and inner(s), see the attached picture.
When polygon B is inside polygon A, the outer of B exactly matches one of the inners of A, even if I can't assure the starting point in the rings matches, but I don't think this can be a problem.
My issue is that TopoGeo_ToGeoTableGeneralize works great with low tolerance values (for example 0.5 meters for the dataset I'm using), but it begins to generate overlapped polygons at higher tolerance values (1.0 meters).
 

the most obvious solution for simplifying a set of contour
lines seems the one to represent them as Linestrings.

Contours do not convey the same information as depth areas, but I see your point and I'll try this option.

if you really want to represent them as Polygons you
must then accept that the output polygons do overlap
(exactly as it happens in the given reference table).

They don't overlap in the reference table, see above
 

and finally, if you absolutely want to get a "ribbon
style" output table you necessarily have to export
someway the Faces out from Topology.

Knowing that I already have "ribbons" in the reference table, wouldn't TopoGeo_ToGeoTableGeneralize alone (against the reference table, not against extracted faces) theoretically do the job?
 

You can eventually rearrange your reference table so to "realize
that the outer ring of polygon A matches an inner of polygon B"
but this surely requires some explicit extra processing (nothing
exceptionally difficult anyway).

As above, knowing that I already have "ribbons" in the reference table, can rttopo detect that, i.e. realize about "shared" rings? if not, which extra processing do I need?

Thanks a lot for your time

Ciao
Alessandro

[a.fu...@lqt.it]

On Tue, 29 Aug 2017 08:03:41 -0700 (PDT), Alessandro Donati wrote:
> Polygons in the reference table do not overlap, they have outer and
> inner(s), see the attached picture.
> When polygon B is inside polygon A, the outer of B exactly matches
> one
> of the inners of A, even if I can't assure the starting point in the
> rings matches, but I don't think this can be a problem.
> My issue is that TopoGeo_ToGeoTableGeneralize works great with low
> tolerance values (for example 0.5 meters for the dataset I'm using),
> but it begins to generate overlapped polygons at higher tolerance
> values (1.0 meters).
>  

Alessandro,

all this strongly contrasts with my own findings; I'm completely
unable to reproduce this issue.

I'll be absolutely glad to set up a full debug session, but
I absolutely need a copy of your DB and few samples of your
SQL queries for doing such a thing.

even a small sized DB should be enough, but it should
continue to present this issue.
if your data are someway reserved you can send your
sample to my private e-mail.

bye Sandro

[a.fu...@lqt.it]

ciao Alessandro,

thanks for submitting a sample DB; here are the findings
from my debugging session.

SELECT *
FROM "out_test_1.0m"
WHERE ST_NumGeometries(geometry) > 1;

surprise: there are three features unexpectedly
represented by _TWO_ different polygons.
after a quick visual inspection the first seems to
be the "ribbon" we were expecting, but the second
is a solid polygon lacking any internal hole.

note: this never happens for lower simplification
values (Douglas-Peucker radius); in the 0.5m case
all features are simple polygons.
and when I progressively increase the DP-radius
(1.5, 2.0, 2.5, ...) the number of such odd "two
polygons" features is quickly growing.

let's now go to visually check what's really happening.
I've just extracted these three "exceptional" features
into a separate table, then I've suppressed the
second polygon so to keep just the "ribbon" alone.
(I'll avoid to report all the SQL queries because
they are rather trivial and surely boring).

when zooming to the selected areas (fig1) it
becomes crystal clear that the simplification
process has created invalid polygons (fig2, fig3),
because the inner ring intersects the outer ring !!!

it's notorious that many geometry algorithms
implemented by GEOS can produce crazy results
while processing invalid geometries, and this
exactly is what's happening in this case.

in some exceptional cases the exterior and the
interior ring are too much close the one to the
other, so close that the distance dangerously
falls under the Douglas-Peucker radius.
and consequently both rings when simplified can
badly intersect thus creating invalid polygons.

quick conclusion: there is very little we can do
so to programmatically prevent such issues, because
they are directly caused by the intrinsic nature of
the polygons being processed.

the unique viable patch I can imagine is to check
if some invalid geometry will be eventually created
when simplifying then returning a NULL geometry.
(=== problem impossible to solve with given data
and arguments).

bye Sandro

[Alessandro Donati]

Ciao Sandro,

once more many thanks for your in-depth analysis

the unique viable patch I can imagine is to check
if some invalid geometry will be eventually created
when simplifying then returning a NULL geometry.
(=== problem impossible to solve with given data
and arguments).

 

With the intent to intercept a potential problem in advance, my idea is to choose a proper DP tolerance value based on how close geometries are in the source dataset (the closer the contours, the lower the simplification).

I had a look at KNN, but all examples are about comparing two geotables.

Would you share an example to find the minimum distance between geometries, element-wise?

KNN or something else (topology tables themselves?) which is suitable for this problem

Ciao,

Alessandro

[a.fu...@lqt.it]

On Mon, 4 Sep 2017 06:04:03 -0700 (PDT), Alessandro Donati wrote:
> I had a look at KNN, but all examples are about comparing two
> geotables.
>
> Would you share an example to find the minimum distance between
> geometries, element-wise?
>
> KNN or something else (topology tables themselves?) which is suitable
> for this problem
>

Alesandro,

I'm not really sure to understand your question.
KNN simply is a derivative of the R*Tree spatial index, and
it's intended to perform a fast and efficient scan on some
Spatial Table (that must be supported by a companion Spatial
Index) then returning the list (ordered by increasing
distance) of the first N features presenting the shorter
distances in relation to some given reference geometry.
.
examples:

SELECT * FROM Knn
WHERE f_table_name = 'my_table'
AND ref_geometry = MakePoint(x, y);

- this is the short default syntax returning just 3 items.

SELECT * FROM Knn
WHERE f_table_name = 'my_table' AND f_geometry_column = 'geom'
AND ref_geometry = MakePoint(x, y) AND max_items = 100;

- and this is the extended syntax explicitly referencing
a geometry column and returning 100 items.

when writing real world SQL queries based on KNN you'll
probably quickly discover that defining a JOIN between
the KNN and the underlaying table is a practical need.
(exactly as it happens to the examples on the Wiki page).


===============

if KNN isn't what you are looking for, you can directly
use the standard SQL function ST_Distance(geom1, geom2),
may be in an aggregate context as in:
Min( ST_Distance(geom1, geom2) )

note: this second approach will surely run slowly when
"big tables" are involved because it requires computing
a big number of individual distances, that is a costly
operation.
The Knn approach surely is noticeably faster.

I'm not aware of any other SQL function intended to
measure the minimum distance between geometries;
Topology itself internally depends on ST_Distance().

bye Sandro