Distance from Line to Rectangle in 3D

David Eberly, Geometric Tools, Redmond WA 98052

https://www.geometrictools.com/

This work is licensed under the Creative Commons Attribution 4.0 International License. To view a copy

of this license, visit h ttp://creativecommons.org/licenses/by/4.0/ or send a letter to Creativ eCommons,

PO Box 1866, Mountain View, CA 94042, USA.

Created: June 5, 2018

1 Parameterizations of the Objects

2 Distance Computed by Minimizing a Quadratic Function

3 Equivalence to the 3D Segment-Segment Distance Query

4 Robust Algorithm for Computing the Distance

4.1 A Brief Analysis of the Quadratic Function

4.1.1 The MatrixAis Invertible. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

4.1.2 The MatrixAis not Invertible. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

4.2 Conjugate Gradient Method

4.3 Constrained Conjugate Gradient Algorithm

4.3.1 Casea00= maxfa00;a11g>0. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4.3.2 Casea11= maxfa00;a11g>0. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.4 An Implementation

5 Distance from Ray or Segment to Rectangle in 3D

5.1 Distance between a Point and a Convex Object

5.2 Distance from Point to Rectangle in 3D

5.3 Line-Rectangle Squared Distance is Convex andC1. . . . . . . . . . . . . . . . . . . . . . . .15

5.4 Ray-Rectangle and Segment-Rectangle Squared Distance

17 1

1 Parameterizations of the Objects

The line is parameterized byP+tDwhereDis a unit-length vector andt2R. The rectangle has four verticesVifor 0i3; they are ordered either clockwise or counterclockwise. DeneE0=V1V0and E

1=V3V0to be the directions of the edges emanating from the vertexV0. The edges for a rectangle

must be perpendicular, soE0E1= 0. The remaining vertex isV2=V1+E1=V3+E0. The rectangle is parameterized byV0+uE0+vE1where 0u1 and 0v1.

2 Distance Computed by Minimizing a Quadratic Function

Dene=V0P. Half the squared distance between two points, one point on the rectangle and one point on the line, is the quadratic function

Q(u;v;t) =12

j(V0+uE0+vE1)(P+tD)j2 12 juE0+vE1tD+j2 12 xTAx+bTx+c(1) where the last equality denes x=2 6 664u
v t3 7

775; A=2

6 664E

0E00E0D

0E1E1E1D

E0DE1D13

775;b=2

6 664E
0 E 1 D3 7

775; c=12

jj2(2) The vectorDis unit length, so the lower-right entry ofAisDD= 1. The two zero-valued entries ofA correspond toE0E1= 0. The variables are constrained by 0u1 and 0v1. Thet-variable is unconstrained. For the sake of indexing, letA= [aij] andb= [bj]. For a chosen (u;v)2[0;1]2,Qis a quadratic function fort2R. The minimumQfor the chosen (u;v) must occur when

0 =@Q@t

=a02u+a12v+t+b2(3)quotesdbs_dbs2.pdfusesText_3

[PDF] Distance from Line to Rectangle in 3D - Geometric Tools

QUADRILATÈRES (NON CROISÉS) PARTICULIERS I DÉFINITIONS ET