# Find intersections between mesh and curve inside it

I have a simple square mesh, and a curve (discretised by another mesh) inside it. Here a picture worths thousand words. What I want to achieve is to find, for every cell $$K$$ of the circular (discretised) grid, I want to get the intersection points with the cells T of other grid. Here they are marked with a red dot.

What is the correct algorithmic to follow? Of course, if two consecutive support points for the circular grid are in different cells, then I can compute the intersection, but in general it may be that a cell $$T$$ is cut and no support points of the other mesh are in there, see again the picture above.

I started with FEnics, but I think in this case deal.II is the way to go. So, any explanation in the deal.II "lingo" is more than welcome.

• Is it possible that one edge of your curve crosses multiple edges of the background mesh? Commented Jan 25, 2022 at 18:19
• @DanielShapero yes, that is possible, and it is indeed what happens in the top right cell! Commented Jan 25, 2022 at 18:35
• Ah of course, I should have looked more carefully! In any case, if you're using deal.II I think a good place to start would be to find the cell containing an initial point of the curve and work by breadth-first search from there. The functions you'll want are probably compute_point_locations and get_neighbors. Commented Jan 25, 2022 at 19:48
• When I had to deal with non-conforming meshes, I used Clipper to determine the cut areas needed for the domain integrals. Until now, I couldn't find software that can clip arbitrary polyhedra, so going to 3D could be difficult. Commented Jan 25, 2022 at 22:33
• @DanielShapero I started with those functions indeed, but I don't know what you mean with "breadth-first search" in this case. Commented Jan 25, 2022 at 22:51

• Thanks @WolfgangBangerth. I understood the idea, and I like it a lot as indeed I'd be using deal.II capabilities to the full. What I am missing is how to compute those coordinates. From your answer, it seems that I only can say which cells are intersected. But that could've been achieved also by calling compute_point_locations() repeatedly. Commented Jan 26, 2022 at 22:59
• @bobinthebox compute_point_locations() is expensive on its own. You want to make sure that you only look at cells for which there is a reasonable chance that a point is inside. That's why GridTools::Cache exists. Commented Jan 27, 2022 at 14:52