Skip to content

Instantly share code, notes, and snippets.

@hanigamal
Created September 13, 2013 21:47
Show Gist options
  • Star 6 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save hanigamal/6556506 to your computer and use it in GitHub Desktop.
Save hanigamal/6556506 to your computer and use it in GitHub Desktop.
Find the point of intersection of two 3D line segments, works in 2D if z=0
// Assume Coord has members x(), y() and z() and supports arithmetic operations
// that is Coord u + Coord v = u.x() + v.x(), u.y() + v.y(), u.z() + v.z()
inline Point
dot(const Coord& u, const Coord& v)
{
return u.x() * v.x() + u.y() * v.y() + u.z() * v.z();
}
inline Point
norm2( const Coord& v )
{
return v.x() * v.x() + v.y() * v.y() + v.z() * v.z();
}
inline Point
norm( const Coord& v )
{
return sqrt(norm2(v));
}
inline
Coord
cross( const Coord& b, const Coord& c) // cross product
{
return Coord(b.y() * c.z() - c.y() * b.z(), b.z() * c.x() - c.z() * b.x(), b.x() * c.y() - c.x() * b.y());
}
bool
intersection(const Line& a, const Line& b, Coord& ip)
// TODO: To work in 2D set z components to zero
{
Coord da = a.second - a.first;
Coord db = b.second - b.first;
Coord dc = b.first - a.first;
if (dot(dc, cross(da,db)) != 0.0) // lines are not coplanar
return false;
Point s = dot(cross(dc,db),cross(da,db)) / norm2(cross(da,db));
if (s >= 0.0 && s <= 1.0)
{
ip = a.first + da * Coord(s,s,s);
return true;
}
return false;
}
@padmalcom
Copy link

This does not work for (0, 0, 0) -> (10, 0, 0) and (9, 0, 0) -> (20, 0, 0). In this case s is not defined since norm2 returns 0.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment