Finding rows with points that make up a convex hull

[Mike Castle]

I have a simple table, poi, with two columns: guid, ST_POINT

I can get the convex hull of all points easily enough:

SELECT ST_ConvexHull(ST_Union(point)) FROM poi;

I can get the rows using that query as a subselect:

SELECT guid
FROM poi
WHERE ST_Touches(
(SELECT ST_ConvexHull(ST_Union(point)) FROM poi), point);


But I was wondering: as all of the (x, y) values in the points are
floats, do I run the risk of ST_Touches() failing?

Right now I'm just ignoring the fact that these points are actually
WGS84 datums and the above probably works since the floating point
values are not actually modified. However, I will eventually process
'point' with ST_Transform(). So I imagine that I'll run a greater
risk of float equality issues.

Best I can tell, there is no way to build collections through
ST_Union() and the like that include both the point and <user defined
data> (e.g., guid, rowid, entire row). Or am I missing something?

I imagine this is not a concern unique to spatialite, but it happens
to be the only relevant list I'm subscribed to that has people
knowledgeable in this domain. (And so far my web searches have not
been too useful.)

Any comments, pointers to specific docs to read, etc, are appreciated!

mrc

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

Hi MIke,

I'll reply in two steps to your questions

> SELECT guid
> FROM poi
> WHERE ST_Touches(
> (SELECT ST_ConvexHull(ST_Union(point)) FROM poi), point);
>

I'm not entirely sure I understand your intentions correctly.

Taken literally, your query works as follows:
1. First, the Convex Hull is determined, that's a Polygon that
encloses all the Points present in the dataset.
2. Then ST_Touches will identify which Points fall exactly
on the Polygon's boundary.
In other words, what are the Points that have become
vertices of the Convex Hull Polygon.

If instead you wanted to check whether all the Points in
the dataset are actually included in the Polygon then you
should have used ST_Intersects instead of ST_Touches.

> But I was wondering: as all of the (x, y) values in the points
> are floats, do I run the risk of ST_Touches() failing?
>

Absolutely not, because the coordinates of the vertices of
the Polygon are directly copied from the corresponding Points,
and therefore will always exectly match.

I'll give you a more detailed answer in my next email

best regards,
Sandro

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

> I imagine this is not a concern unique to spatialite, but it happens
> to be the only relevant list I'm subscribed to that has people
> knowledgeable in this domain. (And so far my web searches have not
> been too useful.)
>
> Any comments, pointers to specific docs to read, etc, are
> appreciated!
>

Recall: what is a floating point number (DOUBLE) really?

- there are 64 bits available
- 53 bits are for storing the binary value
(more or less corresponding to about 16 decimal digits)
- the remaining are for storing the exponent in the range
between -1022 and +1023

It's an extremely flexible format that lends itself well
to representing both infinitesimal values ​​and exaggeratedly
enormous values.
It's not by chance that it's also called scientific notation,
because it adapts indifferently to the microscopic values ​​of
the atomic scale as well as to the huge values ​​of astronomy.

However, there are two important limitations to always keep in mind:
1. Values ​​always have a fixed length, so they may be subject to
truncation and rounding during calculations.
2. The precision is very variable because it depends on the
scale (value of the exponent)

Let's see a very concrete case: determining the intersection between
two segments (think of an X)
Unless we are dealing with two segments perfectly parallel to the axes
(or other very particular cases) the intersection Point will certainly
be assigned coordinates that have suffered the adverse effects of
truncation / rounding.
With the unfortunate consequence that a subsequent check via
ST_Intersects might say that the intersection Point does not fall on
the one or the othe segment (or may be both).
Definitely puzzling but absolutely unavoidable.

The canonical solution in all these cases is to use ST_Snap to force
the insertion of the intersection Point in each of the two segments;
in this way the intersection problem is solved, but it should be noted
that it introduces a (small) alteration of the geometry which is no
longer exactly the same as before.

This is the thorniest problem that the Topology module has to face,
where everything relies on the perfect coincidence of coordinates.
It's no coincidence that many topological functions have a <tolerance>
parameter that allows you to establish how far you can push the
rearrangement of the geometries to make them fit together exactly.

----------------------------------

Fortunately in many cases these problems are never encountered, but
whenever any intersection between two segments or between a segment
and a point comes into play, danger is always lurking.

I don't see any particular problems in using ST_Transform; it's
obvious that some more or less evident alteration will always be
introduced, but the deterministic nature of the geodesic calculations
will always lead to consistent results.

Final conclusion: the very nature of floating point numbers always
introduces some risk due to truncations and roundings, it's something
absolutely unavoidable.
Can become a major source of severe headaches when rigorous
topological consistency is required.
Fortunately, in most cases, it's something we can safely ignore.

But above all let us never forget that the fabulous calculation
speed ensured by the floating points of modern CPUs is the real
secret of all computational geometry.
It's an approach that is not without flaws, but at the same time
ensures many excellent advantages.
As always it is a trade-off; you lose something but you gain a lot.

bye Sandro