4
$\begingroup$

I need to find a distance from a point in 3D space to a parallelepiped (a crystal lattice cell). The problem boils down to a quadratic programming task:

Let $L$ be a matrix of lattice vectors (row-wise); $q$ is a point to find a distance from. Then the problem is following:

$$\min_{\textbf{x}} |L^T \textbf{x} - \textbf{q} |^2 \\ \forall i=1..3 : 0 \leq \textbf{x}_i \leq 1 $$

or equivalently

$$\min_{\textbf{x}} \frac{1}{2} \textbf{x}^TLL^T\textbf{x} - \textbf{x}^T L \textbf{q}\\ \forall i=1..3 : 0 \leq \textbf{x}_i \leq 1 $$

This is obviously a QP problem with inequality constraints. And there are many methods and libraries capable of solving it. However, I don't want to bring an additional library into the project for a minor task. Given that it is a small problem, with fixed dimensions and simple constraints, I have a hope, that it is possible to get a simple self-contained Fortran code that would solve it. Perhaps there is a solver with a code generator for small cases.

$\endgroup$
3
  • 1
    $\begingroup$ As a rule of thumb, whenever you find yourself using the word "obviously", it's a good time to take a step back and question yourself. Calculating the distance from a point to a quadrilateral in 3d space can be done with an explicit formula; this doesn't require general methods to solve an optimisation problem. A parallelepiped is just the union of six quadrilaterals. $\endgroup$
    – Stef
    Dec 24, 2023 at 12:28
  • $\begingroup$ Related question: Distance between a point and rectangle in 3D space (although the question is about rectangles, the answer applies equally well to non-rectangular parallelograms). $\endgroup$
    – Stef
    Dec 24, 2023 at 15:08
  • $\begingroup$ @Stef, sure. But it turned out, that the BVLS solution takes less code, than the geometrical one from Burkardt. $\endgroup$
    – user36313
    Dec 24, 2023 at 16:15

2 Answers 2

8
$\begingroup$

Your problem is a bounded variables least squares (BVLS) problem. For small instances, an active set method can quickly solve the problem. Lawson and Hanson have Fortran code for this in their book on least squares problems.

$\endgroup$
1
9
$\begingroup$

John Burkardt provides parallelepiped_point_dist_3d in his geometry library. The Fortran90 version: https://people.sc.fsu.edu/~jburkardt/f_src/geometry/geometry.html (MIT license). It computes the minimum distance to each face, rather than solve a constrained optimization problem by general methods. Unless you have prior knowledge of the hidden faces from the perspective of the viewing point, it may be the most efficient exploitation of the problem structure.

$\endgroup$
2
  • $\begingroup$ Thanks, looks good. And the license is good. But the BVLS solution is just more compact. $\endgroup$
    – user36313
    Dec 24, 2023 at 16:12
  • 3
    $\begingroup$ Regarding the license: if he is the original author, fine. Otherwise, while his site is invaluable, I'm wary of Burkardt's code licenses: for instance, ASA code has a note "The Royal Statistical Society holds the copyright to these routines, but has given its permission for their distribution provided that no fee is charged.", and on JB's site it's distributed under LGPL (e.g. ASA063). I believe it may be a problem. $\endgroup$
    – user46456
    Dec 25, 2023 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.