Skip to content

Instantly share code, notes, and snippets.

@chunkyguy
Created October 11, 2013 18:54
Show Gist options
  • Save chunkyguy/6940114 to your computer and use it in GitHub Desktop.
Save chunkyguy/6940114 to your computer and use it in GitHub Desktop.
Assume two line segments [p, p+r] and [q, q+s], and test if they intersect.
#define CROSS_Z(a, b) ((a.x*b.y) - (a.y*b.x))
bool LinesIntersect(GLKVector2 p, GLKVector2 p_plus_r, GLKVector2 q, GLKVector2 q_plus_s) {
/* Calculate q - p */
GLKVector2 q_p = {
q.x - p.x,
q.y - p.y
};
/* Calculate r */
GLKVector2 r = {
p_plus_r.x - p.x,
p_plus_r.y - p.y
};
/* Calculate s */
GLKVector2 s = {
q_plus_s.x - q.x,
q_plus_s.y - q.y
};
/* Calculate (q-p) x r */
float q_pxr = CROSS_Z(q_p, r);
/* Calculate (q-p) x s */
float q_pxs = CROSS_Z(q_p, s);
/* Calculate (r x s) */
float rxs = CROSS_Z(r,s);
if (q_pxr == 0.0f) {
// Lines are collinear, and so intersect if they have any overlap.
// Assume edge case as failure
return false;
}
if (rxs == 0.0f) {
// Lines are parallel.
return false;
}
/* Calculate 1 / (rxs) */
float one_div_rxs = 1.0f / rxs;
/* Calculate t */
float t = q_pxs * one_div_rxs;
/* Calculate u */
float u = q_pxr * one_div_rxs;
return (t >= 0.0f) && (t <= 1.0f) && (u >= 0.0f) && (u <= 1.0f);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment