# PostGIS - Partition over distinct geometries ignoring directionality

I have a table containing geometries, some of which are spatially equal (`ST_Equals` returns true), but are not strictly equal due to different directionality (`=` operator returns false, assuming the new behavior of the `=` operator since PostGIS 2.4):

`````` gid |        geom
-----+---------------------
1 | LINESTRING(0 0,1 1)
2 | LINESTRING(1 1,0 0)
3 | LINESTRING(2 2,3 3)
4 | LINESTRING(0 0,1 1)
5 | LINESTRING(4 4,5 5)
6 | LINESTRING(3 3,2 2)
``````

Note in the table above, there are 3 distinct geometry groups:

• Geometries with gid 1, 2, and 4 are spatially equal (despite different directionality).
• Geometries with gid 3 and 6 are spatially equal (despite different directionality).
• Geometry with gid 5 is not spatially equal with any other geometry in the table.

I would like to partition over this table and assign a geometry "group ID" to each row. The group ID should be the same for all rows where the geometry is spatially equal (ignoring directionality).

The desired result should look like this:

`````` gid |        geom         | grpnum
-----+---------------------+--------
1 | LINESTRING(0 0,1 1) |      1
2 | LINESTRING(1 1,0 0) |      1
3 | LINESTRING(2 2,3 3) |      2
4 | LINESTRING(0 0,1 1) |      1
5 | LINESTRING(4 4,5 5) |      3
6 | LINESTRING(3 3,2 2) |      2
``````

If directionality could be ignored, I could do something like this (the `geoms` CTE is just for sample data):

``````WITH
geoms AS
(
SELECT 1 AS gid, ST_GeomFromText('LINESTRING(0 0, 1 1)') AS geom
UNION ALL
SELECT 2 AS gid, ST_GeomFromText('LINESTRING(1 1, 0 0)') AS geom
UNION ALL
SELECT 3 AS gid, ST_GeomFromText('LINESTRING(2 2, 3 3)') AS geom
UNION ALL
SELECT 4 AS gid, ST_GeomFromText('LINESTRING(0 0, 1 1)') AS geom
UNION ALL
SELECT 5 AS gid, ST_GeomFromText('LINESTRING(4 4, 5 5)') AS geom
UNION ALL
SELECT 6 AS gid, ST_GeomFromText('LINESTRING(3 3, 2 2)') AS geom
)
SELECT
geoms.*,
dense_rank() OVER (ORDER BY geom) AS grpnum
FROM geoms
ORDER BY gid;
``````

The result of which is:

`````` gid |      st_astext      |   grpnum
-----+---------------------+------------
1 | LINESTRING(0 0,1 1) |          1
2 | LINESTRING(1 1,0 0) |          2
3 | LINESTRING(2 2,3 3) |          3
4 | LINESTRING(0 0,1 1) |          1
5 | LINESTRING(4 4,5 5) |          5
6 | LINESTRING(3 3,2 2) |          4
``````

However, that assigns a different group to 1 and 2, as well as to 3 and 6, which I would like to treat as equal. I need to use `ST_Equals` here somehow, which has the behavior I want (it ignores directionality), but I'm not sure how to structure the query since `ST_Equals` requires that you pass it in a pair of geometries.

• It returns the proper result with 2.3 It's all explained here
– JGH
Dec 4, 2017 at 18:52
• I think you may want to add `'LINESTRING(0 1,1 0)'` or `'LINESTRING(1 1, 0.3 0.8, 0 0)'` to your test set as well to show the true behaviour of group by geom. To mimic that behaviour then `ST_Envelope(geom)` will do in the `GROUP BY` Dec 5, 2017 at 0:48

## 3 Answers

Unfortunately I do not have 2.4 to test this against, however it seemed to work with 2.3, taking into account that the `GROUP BY` on a geometry uses the bounds.

I think you need to do a order by `ST_Normalize(geom)` giving you a query like:

``````WITH my_table AS (
SELECT *
FROM (VALUES
(1 ,'LINESTRING(0 0,1 1)'::Geometry)
,(2 ,'LINESTRING(1 1,0 0)'::Geometry)
,(3 ,'LINESTRING(2 2,3 3)'::Geometry)
,(4 ,'LINESTRING(0 0,1 1)'::Geometry)
,(5 ,'LINESTRING(4 4,5 5)'::Geometry)
,(6 ,'LINESTRING(3 3,2 2)'::Geometry)
,(7 ,'LINESTRING(0 1,1 0)'::Geometry)
,(8 ,'LINESTRING(1 1, 0.3 0.8, 0 0)'::Geometry)
)a(gid,geom)
)
select *,
ST_AsText(ST_Normalize(geom)),
dense_rank() over (order by ST_Normalize(geom))
--dense_rank() over (order by ST_AsText(ST_Normalize(geom))) -- used for testing in 2.3
from my_table;
``````
• Awesome! Seems to produce the correct result for the real data I'm working with, and takes less than a second to run. Didn't know about `ST_Normalize` - very useful! Dec 5, 2017 at 4:47
• @SergeyK To be honest it's the first time that I've found a use for this.function. I suspect this is not wat it was really intended for, but as long as it does what is required. Dec 5, 2017 at 6:05

Thanks for the heads up on this issue. I was not exactly conscious of it though I don't usually group by things by geometry equality myself.

Why not just adjust the linestrings to all orient the same way before doing the aggregation?

``````WITH geoms AS (
SELECT 1 AS gid, ST_GeomFromText('LINESTRING(0 0, 1 1)') AS geom
UNION ALL
SELECT 2 AS gid, ST_GeomFromText('LINESTRING(1 1, 0 0)') AS geom
UNION ALL
SELECT 3 AS gid, ST_GeomFromText('LINESTRING(2 2, 3 3)') AS geom
UNION ALL
SELECT 4 AS gid, ST_GeomFromText('LINESTRING(0 0, 1 1)') AS geom
UNION ALL
SELECT 5 AS gid, ST_GeomFromText('LINESTRING(4 4, 5 5)') AS geom
UNION ALL
SELECT 6 AS gid, ST_GeomFromText('LINESTRING(3 3, 2 2)') AS geom
)
,reorient AS (
SELECT
a.gid
,CASE
WHEN ST_X(ST_StartPoint(a.geom)) > ST_X(ST_EndPoint(a.geom))
OR (
ST_X(ST_StartPoint(a.geom)) = ST_X(ST_EndPoint(a.geom))
AND ST_Y(ST_StartPoint(a.geom)) > ST_Y(ST_EndPoint(a.geom))
)
THEN
ST_Reverse(a.geom)
ELSE
a.geom
END AS geom
FROM
geoms a
)
SELECT
b.*
,DENSE_RANK() OVER (ORDER BY b.geom) AS grpnum
FROM
reorient b
ORDER BY
b.gid;
``````

One problem would occur if the lines formed closed rings with the start and end the same. If that is a possible scenario you could test if end is equal to start and then use the next point for the comparison.

* EDIT MickyT's solution using ST_Normalize is simpler and handles the ring scenario - I'd go with his answer *

Cheers,

Paul

• Thanks, I accepted MickyT's solution as it was simpler, but you definitely had the right idea. Dec 5, 2017 at 4:57

Here's the best I could come up with. Not sure if there's a cleaner, more succinct way - seems like it could be simplified. It also takes a while to run (up to a full minute for a table containing 5000 rows):

``````WITH
geoms AS
(
SELECT 1 AS gid, ST_GeomFromText('LINESTRING(0 0, 1 1)') AS geom
UNION ALL
SELECT 2 AS gid, ST_GeomFromText('LINESTRING(1 1, 0 0)') AS geom
UNION ALL
SELECT 3 AS gid, ST_GeomFromText('LINESTRING(2 2, 3 3)') AS geom
UNION ALL
SELECT 4 AS gid, ST_GeomFromText('LINESTRING(0 0, 1 1)') AS geom
UNION ALL
SELECT 5 AS gid, ST_GeomFromText('LINESTRING(4 4, 5 5)') AS geom
UNION ALL
SELECT 6 AS gid, ST_GeomFromText('LINESTRING(3 3, 2 2)') AS geom
),
matches AS
(
SELECT
g1.gid gid1,
g2.gid gid2
FROM geoms g1
INNER JOIN geoms g2
ON ST_Equals(g1.geom, g2.geom)
AND g1.gid <= g2.gid
ORDER BY
gid1,
gid2
),
first_matches AS
(
SELECT
m.gid1 AS gid,
(
SELECT MIN(m2.gid1) AS mgid1
FROM matches m2
WHERE m2.gid1 <= m.gid1 AND m.gid1 = m2.gid2
) first_matching_gid
FROM matches m
ORDER BY
gid1,
gid2
),
groups AS
(
SELECT DISTINCT ON (gid)
m.gid,
dense_rank() OVER (ORDER BY first_matching_gid) AS grpnum
FROM first_matches m
ORDER BY
gid
)
SELECT
geoms.*,
grpnum
FROM geoms
INNER JOIN groups USING (gid);
``````

The first CTE (`geoms`) just contains the sample data for this example.

The second CTE (`matches`) does a self-join against the `geoms` data using `ST_Equals` to find all matching geometries (ignoring directionality). The matching geometries are returned as a pair of columns `gid1` and `gid2`. The condition `g1.gid <= g2.gid` is used to avoid returning duplicate pairs (e.g., if we already had the pair `(1, 4)`, then the pair `(4, 1)` is redundant, so we exclude it).

The result so far looks like this:

`````` gid1 | gid2
------+------
1 |    1
1 |    2
1 |    4
2 |    2
2 |    4
3 |    3
3 |    6
4 |    4
5 |    5
6 |    6
``````

The purpose of the next CTE (`first_matches`) is, for each `gid`, to find the first (i.e., lowest) `gid` that has a matching geometry. In other words, for gid 4, the first matching gid would be 1 (even though 2 also matches). Here is the result of that CTE:

`````` gid | first_matching_gid
-----+--------------------
1 |                  1
1 |                  1
1 |                  1
2 |                  1
2 |                  1
3 |                  3
3 |                  3
4 |                  1
5 |                  5
6 |                  3
``````

At this point, `first_matching_gid` already fulfills the requirement of `grpnum` in that it uniquely identifies the distinct geometries in the original table. Now we just need to whittle the result down to a single row per geometry (i.e., per unique `gid`), and perhaps also reassign the group numbers so there are no gaps in the numbering. That's the role of the last CTE (`groups`), the result of which looks like this:

`````` gid | grpnum
-----+--------
1 |      1
2 |      1
3 |      2
4 |      1
5 |      3
6 |      2
``````

After all the CTEs, the final `SELECT` statement just joins back to the original `geoms` CTE to get the final desired result:

`````` gid |        geom         | grpnum
-----+---------------------+--------
1 | LINESTRING(0 0,1 1) |      1
2 | LINESTRING(1 1,0 0) |      1
3 | LINESTRING(2 2,3 3) |      2
4 | LINESTRING(0 0,1 1) |      1
5 | LINESTRING(4 4,5 5) |      3
6 | LINESTRING(3 3,2 2) |      2
``````