topology.GetRingEdges return wrong ring when edge.next_left/right = edge

[remic]

The problem is reproducible by creating a topology like the polar stars constellation (a square of 4 edges + a tail of on edge connected to the square).

When using GetRingEdges(tail), we loop in the same order as when using GetRingEdges(-tail). We should have 2 different direction of looping (which is the case when using the function or normal edges)

I don't understand recursive CTE enough to correct it myself

Here is what the function returns : GetRingEdges(-574) -574 574 576 575

GetRingEdges(574) 574 576 575 -574

The two correct ring should be : (starting from 576 and -576)

576

575 -574 574

-576 -575

Rémi-c

[remic]

Screenshot of Polar Constellation configuration

[strk]

It's not an error. The function lists the edge being walked on and the direction. By starting with a negative value you request to walk on that edge backward, from its right side. A left turn is taken on every node.

[remic]

Hm in my opinion it is an error. In no case should you have the same walk by walking forward or backward. Now if calling the function for +X and -X gives the same result (except for isolated edge).

It is the case here, because whatever the sign you always end up turning in the same direction.

Cheers, Rémi-C

[remic]

Here is an example of a function that turns in the other direction (but is subject ot same limitation than regular getedge)

---

DROP FUNCTION IF EXISTS topology.rc_GetRingEdges_backward( topology_name text, s_edge_id int) ; CREATE OR REPLACE FUNCTION topology.rc_GetRingEdges_backward( topology_name text, s_edge_id int) RETURNS TABLE (ordinality int, signed_edge_id INT)

AS

$BODY$

/ @brief given a signed edge, compute the ring it belongs to. It is a safer version than the traditionnal one, because it also work on flat faces */ DECLARE

_q text ;

BEGIN

_q := format('

WITH RECURSIVE edgering AS (

WITH input_edge_id AS (

SELECT %1$s as signed_edge_id LIMIT 1

) SELECT signed_edge_id

, edge_id , next_left_edge , next_right_edge

FROM input_edge_id, %2$I.edge_data as ed WHERE ed.next_left_edge = signed_edge_id OR ed.next_right_edge = signed_edge_id UNION

SELECT CASE WHEN p.signed_edge_id = p.next_right_edge THEN -1*p.edge_id ELSE p.edge_id END

, ed.edge_id , ed.next_left_edge , ed.next_right_edge

FROM edgering AS p , %2$I.edge_data as ed WHERE ed.next_left_edge =

CASE WHEN p.signed_edge_id = p.next_right_edge THEN -1*p.edge_id ELSE p.edge_id END OR ed.next_right_edge = CASE WHEN p.signed_edge_id = p.next_right_edge THEN -1*p.edge_id ELSE p.edge_id END

) —note : row_number is not safe here, it cannont guarantee the ordering SELECT (row_number() over())::int as ordinality, signed_edge_id::int FROM edgering ;',s_edge_id,topology_name); RETURN QUERY EXECUTE _q;

RETURN ;

END ; $BODY$

LANGUAGE plpgsql VOLATILE;

---

[strk]

You really walk on the edge _side_, not on the edge. And you take left turns. Dangling edges, like the one you're walking on, have the same face on both sides so wherever you walk you are on the same face. This is useful to determine if removing the edge would merge two faces or not (for example).

[remic]

Again I strongly disagree. Of course you walk on the edge side, this is precisely why walking from -N or +N shouldn't give the same result (the sign change the direction of edge). So even when walking always to the left, you should have different results.

In fact, our data structure is a disguised half-edge.

When you have the correct ring, it is easy to find which edges are "isolated" (that is next_left_edge or next_right_edge = edge_id), it is simply the edge that are present with both sign in the ring.

CHeers, Rémi-C

[strk]

Sign does not only change direction but also side. You walk forward on the left side, backward on the right side. This is by design.

The only way to change direction would be to walk backward on the left side or forward on the right side.

[strk]

documentation improved with r13262 in 2.1 branch (2.1.6) and r13263 in trunk (2.2.0)