Created
October 11, 2013 18:54
-
-
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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