У меня тоже была эта ошибка, но в моем случае причиной была устаревшая версия npm v1.4.28.
Обновление до npm v3 с последующим
rm -rf node_modules
npm -i
работало на меня. В выпуске npm 2697 содержатся подробные сведения о «максимально плоской» структуре папок, включенной в npm v3 (выпущена в 2015-06-25).
Взятие
Вычислить:
d = L - E (Вектор направления луча,
Заглушка:
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 DOT d) + 2t * (f DOT d) + (f DOT 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 ;
}
Здесь вам понадобится немного математики:
Предположим, A = (Xa, Ya), B = (Xb, Yb) и C = (Xc, Yc). Любая точка на линии от A до B имеет координаты (альфа * Xa + (1-альфа) Xb, альфа Ya + (1-альфа) * 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, используя решение (я) для альфы, вы получите точки пересечения , если таковые существуют.
Если координаты линии 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, и его решениями являются точки пересечения (если они есть). Если вы получите значение, которое меньше 0 или больше 1, то это не решение, но оно показывает, что линия «указывает» в направлении круга.
Координаты s - это 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, и его решениями являются точки пересечения (если они есть). Если вы получите значение, которое меньше 0 или больше 1, то это не решение, но оно показывает, что линия «указывает» в направлении круга.
Координаты s - это 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, и его решениями являются точки пересечения (если они есть). Если вы получите значение, которое меньше 0 или больше 1, то это не решение, но оно показывает, что линия «указывает» в направлении круга.
y - y) ^ 2 = R ^ 2, если вы подставите формулы x и y прямой в формулу окружностей, вы получите уравнение второго порядка для t, и его решениями являются точки пересечения (если таковые имеются). Если вы получите значение, которое меньше 0 или больше 1, то это не решение, но оно показывает, что линия «указывает» в направлении круга.
y - y) ^ 2 = R ^ 2, если вы подставите формулы x и y прямой в формулу окружностей, вы получите уравнение второго порядка для t, и его решениями являются точки пересечения (если таковые имеются). Если вы получите значение, которое меньше 0 или больше 1, то это не решение, но оно показывает, что линия «указывает» в направлении круга.
Если вы найдете расстояние между центром сферы (поскольку она трехмерна, я предполагаю, что вы имеете в виду сферу, а не круг) и линией, то проверьте, меньше ли это расстояние, чем радиус, который будет сделайте трюк.
Точка столкновения, очевидно, является ближайшей точкой между линией и сферой (которая будет вычислена, когда вы вычисляете расстояние между сферой и линией)
Расстояние между точкой и линией :
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html
Вы можете найти точку на бесконечной прямой, ближайшую к центру окружности, проецируя вектор 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
}
}
РЕДАКТИРОВАТЬ: добавлен код для проверки, действительно ли найденные точки пересечения находятся в пределах сегмента линии.
Хорошо, я не буду давать вам код, но поскольку вы отметили этот алгоритм , Я не думаю, что это будет иметь для вас значение. Во-первых, вам нужно получить вектор, перпендикулярный линии.
У вас будет неизвестная переменная в y = ax + c
( c
будет неизвестна )
Чтобы решить эту проблему, вычислите ее значение, когда линия проходит через центр круга.
То есть
Подставьте местоположение центра круга в уравнение прямой и решите относительно c
.
Затем вычислите точку пересечения исходной линии и ее нормали.
Это даст вам ближайшую точку на прямой к окружности.
Вычислите расстояние между этой точкой и центром круга (используя величину вектора).
Если он меньше радиуса круга - вуаля, у нас есть пересечение!
Похоже, никто не рассматривает проекцию, я совсем не в курсе?
Спроецируйте вектор AC
на AB
. Спроецированный вектор AD
дает новую точку D
.
Если расстояние между D
и C
меньше (или равно) R
, мы имеем пересечение.
Примерно так:
Другой метод использует формулу площади треугольника ABC. Тест на пересечение проще и эффективнее, чем метод проекции, но для определения координат точки пересечения требуется больше работы. По крайней мере, он будет отложен до требуемой точки.
Формула для вычисления площади треугольника: area = bh / 2
где b - длина основания, а h - высота. Мы выбрали отрезок AB в качестве основания, чтобы h было кратчайшим расстоянием от C, центра круга, до линии.
Так как площадь треугольника также может быть вычислена с помощью векторного скалярного произведения, мы можем определить 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 отличается of B и длина сегмента не равна нулю, если это может произойти в вашем приложении.
Я бы использовал алгоритм для вычисления расстояния между точкой (центром круга) и линией (линия AB). Затем это можно использовать для определения точек пересечения прямой с окружностью.
Допустим, у нас есть точки A, B, C. Ax и Ay - компоненты x и y точек A. То же самое для 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
Эта функция 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;
}