AからBへの線と、半径RのCに配置された円があります。
線が円と交差するかどうかを確認するために使用するのに適したアルゴリズムは何ですか?そして、それは円の端に沿ったどの座標で発生しましたか?
AからBへの線と、半径RのCに配置された円があります。
線が円と交差するかどうかを確認するために使用するのに適したアルゴリズムは何ですか?そして、それは円の端に沿ったどの座標で発生しましたか?
取る
計算:
d = L - E (始点から終点までの光線の方向ベクトル)
f = E - C (中心球から光線の始点までのベクトル)
次に、交点は次のように求められます..
プラグイン:
P = E + t * d
これはパラメトリック方程式です:
P x = E x + td x
P y = E y + td y
を
(x - h) 2 + (y - k) 2 = r 2
(h,k) = 円の中心。
注: ここでは問題を 2D に単純化しました。得られた解決策は 3D でも適用されます。
取得するため:
t 2 * ( d · d
) +
2t *( f · d ) + ( f · f - r 2 ) = 0
したがって、二次方程式を解く:
float a = d.Dot( d ) ;
float b = 2*f.Dot( d ) ;
float c = f.Dot( f ) - r*r ;
float discriminant = b*b-4*a*c;
if( discriminant < 0 )
{
// no intersection
}
else
{
// ray didn't totally miss sphere,
// so there is a solution to
// the equation.
discriminant = sqrt( discriminant );
// either solution may be on or off the ray so need to test both
// t1 is always the smaller value, because BOTH discriminant and
// a are nonnegative.
float t1 = (-b - discriminant)/(2*a);
float t2 = (-b + discriminant)/(2*a);
// 3x HIT cases:
// -o-> --|--> | | --|->
// Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit),
// 3x MISS cases:
// -> o o -> | -> |
// FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1)
if( t1 >= 0 && t1 <= 1 )
{
// t1 is the intersection, and it's closer than t2
// (since t1 uses -b - discriminant)
// Impale, Poke
return true ;
}
// here t1 didn't intersect so we are either started
// inside the sphere or completely past it
if( t2 >= 0 && t2 <= 1 )
{
// ExitWound
return true ;
}
// no intn: FallShort, Past, CompletelyInside
return false ;
}
誰もプロジェクションを考慮していないようです。私はここで完全に軌道から外れていますか?
ベクトルAC
を に投影しAB
ます。射影されたベクトルAD
は、新しい点 を与えますD
。と
の間の距離がより小さい (または等しい) 場合、交点があります。D
C
R
このような:
後でこの投稿に出くわし、そのようなアルゴリズムをどのように実装できるか疑問に思っている人のために、一般的なベクトル操作関数を使用して JavaScript で記述された一般的な実装を次に示します。
/**
* Returns the distance from line segment AB to point C
*/
function distanceSegmentToPoint(A, B, C) {
// Compute vectors AC and AB
const AC = sub(C, A);
const AB = sub(B, A);
// Get point D by taking the projection of AC onto AB then adding the offset of A
const D = add(proj(AC, AB), A);
const AD = sub(D, A);
// D might not be on AB so calculate k of D down AB (aka solve AD = k * AB)
// We can use either component, but choose larger value to reduce the chance of dividing by zero
const k = Math.abs(AB.x) > Math.abs(AB.y) ? AD.x / AB.x : AD.y / AB.y;
// Check if D is off either end of the line segment
if (k <= 0.0) {
return Math.sqrt(hypot2(C, A));
} else if (k >= 1.0) {
return Math.sqrt(hypot2(C, B));
}
return Math.sqrt(hypot2(C, D));
}
この実装では、作業している環境に関係なく、既に提供されている可能性が高いいくつかの一般的なベクトル操作関数を使用しました。ただし、これらの関数をまだ使用できない場合は、次の方法で実装できます。
// Define some common functions for working with vectors
const add = (a, b) => ({x: a.x + b.x, y: a.y + b.y});
const sub = (a, b) => ({x: a.x - b.x, y: a.y - b.y});
const dot = (a, b) => a.x * b.x + a.y * b.y;
const hypot2 = (a, b) => dot(sub(a, b), sub(a, b));
// Function for projecting some vector a onto b
function proj(a, b) {
const k = dot(a, b) / dot(b, b);
return {x: k * b.x, y: k * b.y};
}
このアルゴリズムを使用して、点 (円の中心) と線 (線 AB) の間の距離を計算します。これを使用して、線と円の交点を決定できます。
点 A、B、C があるとします。Ax と Ay は、A 点の x 成分と y 成分です。B と C も同じです。スカラー R は円の半径です。
このアルゴリズムでは、A、B、および C が異なる点であり、R が 0 でないことが必要です。
ここにアルゴリズムがあります
// compute the euclidean distance between A and B
LAB = sqrt( (Bx-Ax)²+(By-Ay)² )
// compute the direction vector D from A to B
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB
// the equation of the line AB is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= LAB.
// compute the distance between the points A and E, where
// E is the point of AB closest the circle center (Cx, Cy)
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)
// compute the coordinates of the point E
Ex = t*Dx+Ax
Ey = t*Dy+Ay
// compute the euclidean distance between E and C
LEC = sqrt((Ex-Cx)²+(Ey-Cy)²)
// test if the line intersects the circle
if( LEC < R )
{
// compute distance from t to circle intersection point
dt = sqrt( R² - LEC²)
// compute first intersection point
Fx = (t-dt)*Dx + Ax
Fy = (t-dt)*Dy + Ay
// compute second intersection point
Gx = (t+dt)*Dx + Ax
Gy = (t+dt)*Dy + Ay
}
// else test if the line is tangent to circle
else if( LEC == R )
// tangent point to circle is E
else
// line doesn't touch circle
さて、私はあなたにコードを与えませんが、あなたはこのアルゴリズムにタグを付けているので、それはあなたにとって重要ではないと思います。まず、線に垂直なベクトルを取得する必要があります。
に不明な変数がありますy = ax + c
( c
不明になります)
。これを解決するには、線が円の中心を通過するときの値を計算します。
つまり
、円の中心の位置を直線方程式に接続し、を解きc
ます。
次に、元の線とその法線の交点を計算します。
これにより、線上で円に最も近い点が得られます。
この点と円の中心の間の距離を計算します(ベクトルの大きさを使用)。
これが円の半径よりも小さい場合-出来上がり、交差点があります!
別の方法では、三角形 ABC 面積式を使用します。交差テストは投影法よりも単純で効率的ですが、交点の座標を見つけるにはより多くの作業が必要です。少なくとも、必要な時点までは遅れるでしょう。
三角形の面積を計算する式は次のとおりです。面積 = bh/2
ここで、b は底辺の長さ、h は高さです。円の中心である C から直線までの最短距離が h になるように、線分 AB をベースとして選択しました。
三角形の面積はベクトル内積でも計算できるため、h を決定できます。
// compute the triangle area times 2 (area = area2/2)
area2 = abs( (Bx-Ax)*(Cy-Ay) - (Cx-Ax)(By-Ay) )
// compute the AB segment length
LAB = sqrt( (Bx-Ax)² + (By-Ay)² )
// compute the triangle height
h = area2/LAB
// if the line intersects the circle
if( h < R )
{
...
}
更新 1:
ここで説明する高速逆平方根計算を使用してコードを最適化し、1/LAB の適切な近似値を得ることができます。
交点の計算はそれほど難しくありません。ここに行きます
// compute the line AB direction vector components
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB
// compute the distance from A toward B of closest point to C
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)
// t should be equal to sqrt( (Cx-Ax)² + (Cy-Ay)² - h² )
// compute the intersection point distance from t
dt = sqrt( R² - h² )
// compute first intersection point coordinate
Ex = Ax + (t-dt)*Dx
Ey = Ay + (t-dt)*Dy
// compute second intersection point coordinate
Fx = Ax + (t+dt)*Dx
Fy = Ay + (t+dt)*Dy
h = R の場合、直線 AB は円に接し、値 dt = 0 および E = F です。点座標は E および F の座標です。
アプリケーションでこれが発生する可能性がある場合は、A が B と異なり、セグメントの長さが null でないことを確認する必要があります。
円の中心点を線に投影して交差をテストする小さなスクリプトを作成しました。
vector distVector = centerPoint - projectedPoint;
if(distVector.length() < circle.radius)
{
double distance = circle.radius - distVector.length();
vector moveVector = distVector.normalize() * distance;
circle.move(moveVector);
}
http://jsfiddle.net/ercang/ornh3594/1/
セグメントとの衝突を確認する必要がある場合は、円の中心から始点と終点までの距離も考慮する必要があります。
vector distVector = centerPoint - startPoint;
if(distVector.length() < circle.radius)
{
double distance = circle.radius - distVector.length();
vector moveVector = distVector.normalize() * distance;
circle.move(moveVector);
}
ベクトル AC をベクトル AB に射影することにより、円の中心に最も近い無限直線上の点を見つけることができます。その点と円の中心の間の距離を計算します。R より大きい場合、交差はありません。距離が R に等しい場合、直線は円の接線であり、円の中心に最も近い点が実際の交点です。距離が R より小さい場合、2 つの交点があります。それらは、円の中心に最も近い点から同じ距離にあります。その距離は、ピタゴラスの定理を使用して簡単に計算できます。疑似コードのアルゴリズムは次のとおりです。
{
dX = bX - aX;
dY = bY - aY;
if ((dX == 0) && (dY == 0))
{
// A and B are the same points, no way to calculate intersection
return;
}
dl = (dX * dX + dY * dY);
t = ((cX - aX) * dX + (cY - aY) * dY) / dl;
// point on a line nearest to circle center
nearestX = aX + t * dX;
nearestY = aY + t * dY;
dist = point_dist(nearestX, nearestY, cX, cY);
if (dist == R)
{
// line segment touches circle; one intersection point
iX = nearestX;
iY = nearestY;
if (t < 0 || t > 1)
{
// intersection point is not actually within line segment
}
}
else if (dist < R)
{
// two possible intersection points
dt = sqrt(R * R - dist * dist) / sqrt(dl);
// intersection point nearest to A
t1 = t - dt;
i1X = aX + t1 * dX;
i1Y = aY + t1 * dY;
if (t1 < 0 || t1 > 1)
{
// intersection point is not actually within line segment
}
// intersection point farthest from A
t2 = t + dt;
i2X = aX + t2 * dX;
i2Y = aY + t2 * dY;
if (t2 < 0 || t2 > 1)
{
// intersection point is not actually within line segment
}
}
else
{
// no intersection
}
}
編集:見つかった交点が実際に線分内にあるかどうかを確認するコードを追加しました。
奇妙なことに、私は答えることができますが、コメントすることはできません...円の中心が原点にくるようにすべてをシフトするMultitaskproのアプローチが好きでした。残念ながら、彼のコードには 2 つの問題があります。まず、平方根の下の部分で、倍力を取り除く必要があります。そうではありません:
var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));
しかし:
var underRadical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);
最終的な座標で、彼は解を元に戻すのを忘れています。そうではありません:
var i1 = {x:t1,y:m*t1+b}
しかし:
var i1 = {x:t1+c.x, y:m*t1+b+c.y};
関数全体は次のようになります。
function interceptOnCircle(p1, p2, c, r) {
//p1 is the first line point
//p2 is the second line point
//c is the circle's center
//r is the circle's radius
var p3 = {x:p1.x - c.x, y:p1.y - c.y}; //shifted line points
var p4 = {x:p2.x - c.x, y:p2.y - c.y};
var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line
var b = p3.y - m * p3.x; //y-intercept of line
var underRadical = Math.pow(r,2)*Math.pow(m,2) + Math.pow(r,2) - Math.pow(b,2); //the value under the square root sign
if (underRadical < 0) {
//line completely missed
return false;
} else {
var t1 = (-m*b + Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //one of the intercept x's
var t2 = (-m*b - Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //other intercept's x
var i1 = {x:t1+c.x, y:m*t1+b+c.y}; //intercept point 1
var i2 = {x:t2+c.x, y:m*t2+b+c.y}; //intercept point 2
return [i1, i2];
}
}
ここでいくつかの数学が必要になります:
A =(Xa、Ya)、B =(Xb、Yb)、C =(Xc、Yc)と仮定します。AからBまでの線上の任意の点は、座標(alpha * Xa +(1-alpha)Xb、alpha Ya +(1-alpha)* Yb)= P
点Pの距離がRからCの場合、それは円上にある必要があります。あなたが望むのは解決することです
distance(P, C) = R
あれは
(alpha*Xa + (1-alpha)*Xb)^2 + (alpha*Ya + (1-alpha)*Yb)^2 = R^2
alpha^2*Xa^2 + alpha^2*Xb^2 - 2*alpha*Xb^2 + Xb^2 + alpha^2*Ya^2 + alpha^2*Yb^2 - 2*alpha*Yb^2 + Yb^2=R^2
(Xa^2 + Xb^2 + Ya^2 + Yb^2)*alpha^2 - 2*(Xb^2 + Yb^2)*alpha + (Xb^2 + Yb^2 - R^2) = 0
この方程式にABC式を適用してアルファを解き、アルファの解を使用してPの座標を計算すると、交点が存在する場合はそれが得られます。
このスレッドへの単なる追加...以下は、pahlevan によって投稿されたコードのバージョンですが、C#/XNA 用であり、少し整理されています。
/// <summary>
/// Intersects a line and a circle.
/// </summary>
/// <param name="location">the location of the circle</param>
/// <param name="radius">the radius of the circle</param>
/// <param name="lineFrom">the starting point of the line</param>
/// <param name="lineTo">the ending point of the line</param>
/// <returns>true if the line and circle intersect each other</returns>
public static bool IntersectLineCircle(Vector2 location, float radius, Vector2 lineFrom, Vector2 lineTo)
{
float ab2, acab, h2;
Vector2 ac = location - lineFrom;
Vector2 ab = lineTo - lineFrom;
Vector2.Dot(ref ab, ref ab, out ab2);
Vector2.Dot(ref ac, ref ab, out acab);
float t = acab / ab2;
if (t < 0)
t = 0;
else if (t > 1)
t = 1;
Vector2 h = ((ab * t) + lineFrom) - location;
Vector2.Dot(ref h, ref h, out h2);
return (h2 <= (radius * radius));
}
球の中心 (3D であるため、円ではなく球を意味すると仮定します) と線の間の距離がわかっている場合は、その距離が半径よりも小さいかどうかを確認してください。
衝突ポイントは明らかに、線と球の間の最も近い点です (球と線の間の距離を計算するときに計算されます)。
点と線の間の距離:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html
' VB.NET - Code
Function CheckLineSegmentCircleIntersection(x1 As Double, y1 As Double, x2 As Double, y2 As Double, xc As Double, yc As Double, r As Double) As Boolean
Static xd As Double = 0.0F
Static yd As Double = 0.0F
Static t As Double = 0.0F
Static d As Double = 0.0F
Static dx_2_1 As Double = 0.0F
Static dy_2_1 As Double = 0.0F
dx_2_1 = x2 - x1
dy_2_1 = y2 - y1
t = ((yc - y1) * dy_2_1 + (xc - x1) * dx_2_1) / (dy_2_1 * dy_2_1 + dx_2_1 * dx_2_1)
If 0 <= t And t <= 1 Then
xd = x1 + t * dx_2_1
yd = y1 + t * dy_2_1
d = Math.Sqrt((xd - xc) * (xd - xc) + (yd - yc) * (yd - yc))
Return d <= r
Else
d = Math.Sqrt((xc - x1) * (xc - x1) + (yc - y1) * (yc - y1))
If d <= r Then
Return True
Else
d = Math.Sqrt((xc - x2) * (xc - x2) + (yc - y2) * (yc - y2))
If d <= r Then
Return True
Else
Return False
End If
End If
End If
End Function
線の座標がAx、Ay、Bx、Byで、円の中心がCx、Cyの場合、線の式は次のようになります。
x = Ax * t + Bx *(1-t)
y = Ay * t + By *(1-t)
ここで、0 <= t <= 1
そして円は
(Cx --x)^ 2 +(Cy --y)^ 2 = R ^ 2
直線のx式とy式を円の式に代入すると、tの2次方程式が得られ、その解が交点になります(存在する場合)。が0より小さいか1より大きい場合、それは解決策ではありませんが、線が円の方向を「指している」ことを示しています。
C# の別のもの (部分的な Circle クラス)。テスト済みで、魅力のように機能します。
public class Circle : IEquatable<Circle>
{
// ******************************************************************
// The center of a circle
private Point _center;
// The radius of a circle
private double _radius;
// ******************************************************************
/// <summary>
/// Find all intersections (0, 1, 2) of the circle with a line defined by its 2 points.
/// Using: http://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle
/// Note: p is the Center.X and q is Center.Y
/// </summary>
/// <param name="linePoint1"></param>
/// <param name="linePoint2"></param>
/// <returns></returns>
public List<Point> GetIntersections(Point linePoint1, Point linePoint2)
{
List<Point> intersections = new List<Point>();
double dx = linePoint2.X - linePoint1.X;
if (dx.AboutEquals(0)) // Straight vertical line
{
if (linePoint1.X.AboutEquals(Center.X - Radius) || linePoint1.X.AboutEquals(Center.X + Radius))
{
Point pt = new Point(linePoint1.X, Center.Y);
intersections.Add(pt);
}
else if (linePoint1.X > Center.X - Radius && linePoint1.X < Center.X + Radius)
{
double x = linePoint1.X - Center.X;
Point pt = new Point(linePoint1.X, Center.Y + Math.Sqrt(Radius * Radius - (x * x)));
intersections.Add(pt);
pt = new Point(linePoint1.X, Center.Y - Math.Sqrt(Radius * Radius - (x * x)));
intersections.Add(pt);
}
return intersections;
}
// Line function (y = mx + b)
double dy = linePoint2.Y - linePoint1.Y;
double m = dy / dx;
double b = linePoint1.Y - m * linePoint1.X;
double A = m * m + 1;
double B = 2 * (m * b - m * _center.Y - Center.X);
double C = Center.X * Center.X + Center.Y * Center.Y - Radius * Radius - 2 * b * Center.Y + b * b;
double discriminant = B * B - 4 * A * C;
if (discriminant < 0)
{
return intersections; // there is no intersections
}
if (discriminant.AboutEquals(0)) // Tangeante (touch on 1 point only)
{
double x = -B / (2 * A);
double y = m * x + b;
intersections.Add(new Point(x, y));
}
else // Secant (touch on 2 points)
{
double x = (-B + Math.Sqrt(discriminant)) / (2 * A);
double y = m * x + b;
intersections.Add(new Point(x, y));
x = (-B - Math.Sqrt(discriminant)) / (2 * A);
y = m * x + b;
intersections.Add(new Point(x, y));
}
return intersections;
}
// ******************************************************************
// Get the center
[XmlElement("Center")]
public Point Center
{
get { return _center; }
set
{
_center = value;
}
}
// ******************************************************************
// Get the radius
[XmlElement]
public double Radius
{
get { return _radius; }
set { _radius = value; }
}
//// ******************************************************************
//[XmlArrayItemAttribute("DoublePoint")]
//public List<Point> Coordinates
//{
// get { return _coordinates; }
//}
// ******************************************************************
// Construct a circle without any specification
public Circle()
{
_center.X = 0;
_center.Y = 0;
_radius = 0;
}
// ******************************************************************
// Construct a circle without any specification
public Circle(double radius)
{
_center.X = 0;
_center.Y = 0;
_radius = radius;
}
// ******************************************************************
// Construct a circle with the specified circle
public Circle(Circle circle)
{
_center = circle._center;
_radius = circle._radius;
}
// ******************************************************************
// Construct a circle with the specified center and radius
public Circle(Point center, double radius)
{
_center = center;
_radius = radius;
}
// ******************************************************************
// Construct a circle based on one point
public Circle(Point center)
{
_center = center;
_radius = 0;
}
// ******************************************************************
// Construct a circle based on two points
public Circle(Point p1, Point p2)
{
Circle2Points(p1, p2);
}
必須:
using System;
namespace Mathematic
{
public static class DoubleExtension
{
// ******************************************************************
// Base on Hans Passant Answer on:
// http://stackoverflow.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre
/// <summary>
/// Compare two double taking in account the double precision potential error.
/// Take care: truncation errors accumulate on calculation. More you do, more you should increase the epsilon.
public static bool AboutEquals(this double value1, double value2)
{
if (double.IsPositiveInfinity(value1))
return double.IsPositiveInfinity(value2);
if (double.IsNegativeInfinity(value1))
return double.IsNegativeInfinity(value2);
if (double.IsNaN(value1))
return double.IsNaN(value2);
double epsilon = Math.Max(Math.Abs(value1), Math.Abs(value2)) * 1E-15;
return Math.Abs(value1 - value2) <= epsilon;
}
// ******************************************************************
// Base on Hans Passant Answer on:
// http://stackoverflow.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre
/// <summary>
/// Compare two double taking in account the double precision potential error.
/// Take care: truncation errors accumulate on calculation. More you do, more you should increase the epsilon.
/// You get really better performance when you can determine the contextual epsilon first.
/// </summary>
/// <param name="value1"></param>
/// <param name="value2"></param>
/// <param name="precalculatedContextualEpsilon"></param>
/// <returns></returns>
public static bool AboutEquals(this double value1, double value2, double precalculatedContextualEpsilon)
{
if (double.IsPositiveInfinity(value1))
return double.IsPositiveInfinity(value2);
if (double.IsNegativeInfinity(value1))
return double.IsNegativeInfinity(value2);
if (double.IsNaN(value1))
return double.IsNaN(value2);
return Math.Abs(value1 - value2) <= precalculatedContextualEpsilon;
}
// ******************************************************************
public static double GetContextualEpsilon(this double biggestPossibleContextualValue)
{
return biggestPossibleContextualValue * 1E-15;
}
// ******************************************************************
/// <summary>
/// Mathlab equivalent
/// </summary>
/// <param name="dividend"></param>
/// <param name="divisor"></param>
/// <returns></returns>
public static double Mod(this double dividend, double divisor)
{
return dividend - System.Math.Floor(dividend / divisor) * divisor;
}
// ******************************************************************
}
}
この Java 関数は DVec2 オブジェクトを返します。円の中心、円の半径、および線のDVec2を使用します。
public static DVec2 CircLine(DVec2 C, double r, Line line)
{
DVec2 A = line.p1;
DVec2 B = line.p2;
DVec2 P;
DVec2 AC = new DVec2( C );
AC.sub(A);
DVec2 AB = new DVec2( B );
AB.sub(A);
double ab2 = AB.dot(AB);
double acab = AC.dot(AB);
double t = acab / ab2;
if (t < 0.0)
t = 0.0;
else if (t > 1.0)
t = 1.0;
//P = A + t * AB;
P = new DVec2( AB );
P.mul( t );
P.add( A );
DVec2 H = new DVec2( P );
H.sub( C );
double h2 = H.dot(H);
double r2 = r * r;
if(h2 > r2)
return null;
else
return P;
}
これは、@Mizipzor が提案したアイデア (プロジェクションを使用) に従って、TypeScript での私のソリューションです。
/**
* Determines whether a line segment defined by a start and end point intersects with a sphere defined by a center point and a radius
* @param a the start point of the line segment
* @param b the end point of the line segment
* @param c the center point of the sphere
* @param r the radius of the sphere
*/
export function lineSphereIntersects(
a: IPoint,
b: IPoint,
c: IPoint,
r: number
): boolean {
// find the three sides of the triangle formed by the three points
const ab: number = distance(a, b);
const ac: number = distance(a, c);
const bc: number = distance(b, c);
// check to see if either ends of the line segment are inside of the sphere
if (ac < r || bc < r) {
return true;
}
// find the angle between the line segment and the center of the sphere
const numerator: number = Math.pow(ac, 2) + Math.pow(ab, 2) - Math.pow(bc, 2);
const denominator: number = 2 * ac * ab;
const cab: number = Math.acos(numerator / denominator);
// find the distance from the center of the sphere and the line segment
const cd: number = Math.sin(cab) * ac;
// if the radius is at least as long as the distance between the center and the line
if (r >= cd) {
// find the distance between the line start and the point on the line closest to
// the center of the sphere
const ad: number = Math.cos(cab) * ac;
// intersection occurs when the point on the line closest to the sphere center is
// no further away than the end of the line
return ad <= ab;
}
return false;
}
export function distance(a: IPoint, b: IPoint): number {
return Math.sqrt(
Math.pow(b.z - a.z, 2) + Math.pow(b.y - a.y, 2) + Math.pow(b.x - a.x, 2)
);
}
export interface IPoint {
x: number;
y: number;
z: number;
}