Skip to content

Instantly share code, notes, and snippets.

@dobrokot
Created May 20, 2012 19:04
Show Gist options
  • Save dobrokot/2759162 to your computer and use it in GitHub Desktop.
Save dobrokot/2759162 to your computer and use it in GitHub Desktop.
segments robust intersection code
#include <stdio.h>
struct Point2f {
float x, y;
Point2f(float _x, float _y): x(_x), y(_y) {}
Point2f(): x(0), y(0) {}
};
Point2f operator -(Point2f p1, Point2f p2) {
return Point2f(p1.x - p2.x, p1.y - p2.y);
}
Point2f operator *(float alpha, Point2f p2) {
return Point2f(alpha*p2.x, alpha*p2.y);
}
Point2f operator +(Point2f p1, Point2f p2) {
return Point2f(p1.x + p2.x, p1.y + p2.y);
}
bool intersection(Point2f start1, Point2f end1, Point2f start2, Point2f end2, Point2f *out_intersection)
{
Point2f dir1 = end1 - start1;
Point2f dir2 = end2 - start2;
//считаем уравнения прямых проходящих через отрезки
float a1 = -dir1.y;
float b1 = +dir1.x;
float d1 = -(a1*start1.x + b1*start1.y);
float a2 = -dir2.y;
float b2 = +dir2.x;
float d2 = -(a2*start2.x + b2*start2.y);
//подставляем концы отрезков, для выяснения в каких полуплоскотях они
float seg1_line2_start = a2*start1.x + b2*start1.y + d2;
float seg1_line2_end = a2*end1.x + b2*end1.y + d2;
float seg2_line1_start = a1*start2.x + b1*start2.y + d1;
float seg2_line1_end = a1*end2.x + b1*end2.y + d1;
//если концы одного отрезка имеют один знак, значит он в одной полуплоскости и пересечения нет.
if (seg1_line2_start * seg1_line2_end >= 0 || seg2_line1_start * seg2_line1_end >= 0)
return false;
float u = seg1_line2_start / (seg1_line2_start - seg1_line2_end);
*out_intersection = start1 + u*dir1;
return true;
}
int main() {
Point2f A1(0, 0);
Point2f A2(15, 12.146760941);
Point2f B1(5.4513401985, -4.4144082069);
Point2f B2(7771.4594727, 6293.2041016);
Point2f result;
if (intersection(A1, A2, B1, B2, &result)) {
printf("%g %g\n", result.x, result.y);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment