Support for Periodic Boundary Conditions (PBC)

[leonardogalliano]

I like this package and all its capabilities. I I would like to request a feature that could enhance its utility in a common setup for 2D particle simulations: periodic boundary conditions (PBC), i.e., defining points on a torus instead of a plane.

In particle simulations, periodic boundaries are often used to ensure a precise definition of neighbours. Specifically, neighbours are defined by connectivity in the Delaunay triangulation.

Would it be possible to extend the package to support triangulation on a torus? This would likely involve modifying the distance metric to use the minimum image distance (MID) instead of the standard Euclidean distance.

For a system confined to a box of side length L, the (squared) minimum image distance between two points (x_i, y_i) and (x_j, y_j) is computed as:

d2 = ((xi-xj) - round((xi - xj) / L) * L)^2 + ((yi-yj) - round((yi - yj) / L) * L)^2.

This compares to the standard Euclidean distance formula:

d2 = (xi-xj)^2 + (yi-yj)^2.

Adding PBC would significantly benefit the community working on 2D particle simulations, as it allows for a more accurate representation of neighbours in a bounded system without edge effects.

I hope this feature can be considered, and I’m happy to provide further details if needed!

[DanielVandH]

I'm not sure the package is really in a position to support such a metric. The closest would be weighted triangulations where the metric is euclidean(p, q)^2 - w(p) - w(q) for some weight function w (i.e., p and q are assigned weights w(p) and w(q)), but I don't think that works for your case.

Can you give me some references that would help with the definitions/details involved in such a computation? I know how to compute e.g. triangulations on the sphere (and actually have a documentation example I'm working on for that if it's of any interest) but a torus I've never actually worked on before. If it's possible to compute the triangulation on a torus easily from some triangulation of a projected set of points, like on the sphere, then maybe it's doable.

[leonardogalliano]

Thanks for your response! Let me clarify the problem a bit more. Periodic boundary conditions (PBC) are commonly used to simulate large systems while minimizing boundary effects. Essentially, the simulation cell is replicated along each direction, so particles on one edge of the box interact with those on the opposite edge (see attached picture 1). For example, a particle at the top left is actually very close to its periodic image near the top right.

At the moment, I’ve worked around the issue by manually duplicating particles near the borders and running DelaunayTriangulation on this extended set (see attached picture 2). However, this approach isn’t ideal and can get messy.

The proper solution would involve using the minimum image distance formula I mentioned earlier, which correctly accounts for particles near the boundary by considering their periodic images. Geometrically, this is equivalent to placing the points on the surface of a torus: imagine folding the box so that the left and right edges touch, then folding it again so the top and bottom edges touch again.

I’m not entirely sure how this would affect the algorithm, but maybe it is not so different from triangulating a sphere and it could be really interesting to explore!

I share a couple of references where similar work has been done (though not in Julia):

• Voro++: A library for neighbor determination via Voronoi tessellation that supports PBC. There’s also a Python wrapper: https://math.lbl.gov/voro++/
• A PRE paper that proposes a Delaunay triangulation algorithm, where every triangle has exactly three neighbors: https://arxiv.org/pdf/0906.4360 (section IIA).

[DanielVandH]

Steps 1-6 in that second paper are probably not too hard to implement if you want to look into that.

Looking online there are some references for explicitly triangulating a torus by triangulating projected points, although I can't tell if it's equivalent to these methods. That would probably be the easiest approach for me to implement. I'd have to think about it some more / find some other references for that.