Retriangulate surface from intersection pattern of two completely periodic directions

[videlec]

We would like to expose a Deformation that, given two flow decompositions into cylinders, rewrites a surface like a Thurston-Veech surface.

The main ingredient for this is to be able to understand the intersection pattern between all the cylinders in the decompositions.

The information we need to build this is only the intersection points of the cylinders and the order in which they show up on the intersecting cylinders, i.e., we need to be able to map an intersection point's (cylinder, order) to the (crossing cylinder, order there.)

It is acceptable that we only implement this when the underlying ring has division.

It might help with some of the geometry to make the flow directions perpendicular first, recompute the surface there, and then deform back to the original directions.

---

original issue below:

In order to automatize the search for Thurston-Veech constructions it would be convenient to have the following function.

INPUT: two FlowDecomposition D0 and D1 of a FlatTriangulation into cylinders (no minimal, no unknown)

We consider the circumferences of all the cylinders in D0 and D1 (oriented in the directions of the vector D0.vertical() and D1.vertical()). They intersect a certain number of times, let say n. We label these intersections arbitrarily with the integers {0, 1, ..., n-1}. One can then build two permutations p0 and p1 on {0, 1, ..., n-1} which corresponds to either follow the cylinders in D0 or following the ones in D1. The cycles in the cycle decomposition of p0 and p1 are respectively in bijection with the cylinders in D0 and D1.

OUTPUT: the permutations p0 and p1 together with the correspondence : cycles of p0 <-> cylinders in D0, cycles of p1 <-> cylinders in D1.

[saraedum]

There was some related discussion a while back at https://sagemath.zulipchat.com/#narrow/stream/271193-polygon/topic/.281.2C.203.2C.206.29. (How to find intersection points of two cylinders.)

[saraedum]

The hard part of this is: Given two cylinders, produce their intersection points such that they can be ordered along their circumferences.

This can be reduced to: Given two saddle connections, produce their intersection points such that they can be ordered along the saddle connections. (i.e., given a couple of such points on a saddle connection, coming from different intersections, order them.)

[saraedum]

About naming, I guess we could have:

std::vector<SaddleConnectionIntersection> SaddleConnection::intersections(const SaddleConnection&) const;
std::vector<PathIntersection> Path::intersections(const Path&) const;
std::vector<FlowComponentIntersection> FlowComponent::intersections(const FlowComponent&) const;
std::vector<FlowComponentIntersection> FlowDecomposition::intersections(const FlowDecomposition&) const;

Each of these should allow to create the corresponding object on the other SaddleConnection/Path/FlowComponent, i.e., there should be:

SaddleConnection SaddleConnectionIntersection::saddleConnection() const;
SaddleConnectionIntersection SaddleConnectionIntersection::other() const;

Not sure whether other is a good name though.

This makes PathIntersection a quite heavy object since it needs to hold on to copies of both paths at all times. If this turns out to be a problem, FlowComponentIntersection could be implemented without using PathIntersection.

We probably don't want to expose the final application of producing the requested permutations in libflatsurf then and only implement this in sage-flatsurf. It should be quite trivial then if I am not missing anything.

---

Note that there is already HalfEdgeIntersection which describes the intersection of a saddle connection and a half edge (used for drawing mostly) and std::vector<HalfEdgeIntersection> SaddleConnection::path() const.

[videlec]

Should it be

- std::vector<FlowComponentIntersection> FlowDecomposition::intersections(const FlowDecomposition&) const;
+ std::vector<FlowDecompositionIntersection> FlowDecomposition::intersections(const FlowDecomposition&) const;

[videlec]

If each intersection has to hold a copy of the path it is indeed annoying. Would it make sense to have a mutability flag on them and hold a reference to an immutable path ?

[videlec]

Also, I think that the intersection of non-tighten path does not make much sense as you want the size of intersections() to coincide with the geometric intersection.

[videlec]

Also, for paths you would have to be careful with the fact that two paths might share a common saddle connection. What is the meaning of intersection there ? If we want geometric intersection the meaning is clear but the position of the intersection point is not well defined. Maybe, when there is indeed a geometric intersection, the middle of the saddle connection ?

[saraedum]

Should it be

- std::vector<FlowComponentIntersection> FlowDecomposition::intersections(const FlowDecomposition&) const;
+ std::vector<FlowDecompositionIntersection> FlowDecomposition::intersections(const FlowDecomposition&) const;

No. But I forget why exactly.

[saraedum]

If each intersection has to hold a copy of the path it is indeed annoying. Would it make sense to have a mutability flag on them and hold a reference to an immutable path ?

We can just hold a shared pointer instead actually. So that's not an issue.

[saraedum]

Also, I think that the intersection of non-tighten path does not make much sense as you want the size of intersections() to coincide with the geometric intersection.

It does not make much sense but we should probably still allow it.

[saraedum]

Also, for paths you would have to be careful with the fact that two paths might share a common saddle connection. What is the meaning of intersection there ? If we want geometric intersection the meaning is clear but the position of the intersection point is not well defined. Maybe, when there is indeed a geometric intersection, the middle of the saddle connection ?

We don't have to return a point. The SaddleConnectionIntersection can be anything internally. So I think we have to keep track of this as a special case inside a SaddleConnectionIntersection.