Created
September 23, 2025 10:51
-
-
Save mrpossoms/301211dc77534a69d74999076b56d8f3 to your computer and use it in GitHub Desktop.
Line segment intersection
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
| static inline bool segments_intersect( | |
| const v2f_t path[2], const v2f_t seg[2], | |
| v2f_t* normal_out, v2f_t* intersect_out, float* t_out) | |
| { | |
| /* s0 | |
| * |--p1 | |
| * | / | |
| * |/ | |
| * | | |
| * /| | |
| * p0 s1 | |
| */ | |
| *normal_out = (v2f_t){ seg[0][Y] - seg[1][Y], seg[1][X] - seg[0][X] }; | |
| *normal_out /= MAG(*normal_out); | |
| v2f_t dir = path[1] - path[0]; | |
| v2f_t delta_0 = path[0] - seg[0]; | |
| v2f_t delta_1 = path[1] - seg[0]; | |
| float dot[2] = { | |
| DOT(delta_0, *normal_out), | |
| DOT(delta_1, *normal_out), | |
| }; | |
| if (dot[0] * dot[1] < 0) { // path of travel crosses the plane | |
| // actual intersection | |
| *t_out = -DOT(path[0] - seg[0], *normal_out) / DOT(dir, *normal_out); | |
| *intersect_out = path[0] + dir * (*t_out); | |
| // But does the intersection point lie within the plane? | |
| v2f_t s0_s1 = seg[1] - seg[0]; // Direction from s0 to s1 | |
| v2f_t s1_s0 = seg[0] - seg[1]; // Direction from s1 to s0 (isn't this just -s0_s1?) | |
| v2f_t i_s0 = seg[0] - *intersect_out; // Direction from intersection to s0 | |
| v2f_t i_s1 = seg[1] - *intersect_out; // Direction from intersection to s1 | |
| // project p1 onto the segment and use that as the intersection | |
| //v2f_t s0_s1_norm = s0_s1 / MAG(s0_s1); | |
| *intersect_out = proj2f(delta_1, s0_s1); | |
| // If the intersection is not within the bounds of the segment, then that means | |
| // that s0_s1 and i_s0 are pointing opposite directions (as are s1_s0 and i_s1). | |
| // Because of this, the dot product of each pair must be <= 0 respectively. | |
| if (DOT(s0_s1, i_s0) > 0 || DOT(s1_s0, i_s1) > 0) { | |
| return false; | |
| } | |
| if (dot[1] > 0) { | |
| *normal_out *= -1; | |
| } | |
| return true; | |
| } | |
| return false; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment