Support for Periodic Boundary Conditions (PBC)

[leonardogalliano]

This package works really well and it's super fast. 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!

[dgleich]

Good question! I should know more about the underlying algorithm before I can comment.

The distance function is easy to swap out. The harder thing are the orientation routines.

Is there an analog with the orient function to determine which order three points are in for the periodic boundary case?

[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 Delaunator 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 orientation routines in the algorithm, but it would be really interesting to explore!

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

• Voro++: A library for neighbour 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 neighbours: https://arxiv.org/pdf/0906.4360 (section IIA).