# 問題B：你如何檢測兩條線是否相交？

``````function doLinesIntersect(AB, CD) {
if (x1 == x2) {
return !(x3 == x4 && x1 != x3);
} else if (x3 == x4) {
return true;
} else {
// Both lines are not parallel to the y-axis
m1 = (y1-y2)/(x1-x2);
m2 = (y3-y4)/(x3-x4);
return m1 != m2;
}
}
``````

# 問題D：兩條線相交？

## C和Objective-C

``````const AGKLine AGKLineZero = (AGKLine){(CGPoint){0.0, 0.0}, (CGPoint){0.0, 0.0}};

AGKLine AGKLineMake(CGPoint start, CGPoint end)
{
return (AGKLine){start, end};
}

double AGKLineLength(AGKLine l)
{
return CGPointLengthBetween_AGK(l.start, l.end);
}

BOOL AGKLineIntersection(AGKLine l1, AGKLine l2, CGPoint *out_pointOfIntersection)
{
// http://.com/a/565282/202451

CGPoint p = l1.start;
CGPoint q = l2.start;
CGPoint r = CGPointSubtract_AGK(l1.end, l1.start);
CGPoint s = CGPointSubtract_AGK(l2.end, l2.start);

double s_r_crossProduct = CGPointCrossProductZComponent_AGK(r, s);
double t = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), s) / s_r_crossProduct;
double u = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), r) / s_r_crossProduct;

if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
{
if(out_pointOfIntersection != NULL)
{
*out_pointOfIntersection = CGPointZero;
}
return NO;
}
else
{
if(out_pointOfIntersection != NULL)
{
CGPoint i = CGPointAdd_AGK(p, CGPointMultiply_AGK(r, t));
*out_pointOfIntersection = i;
}
return YES;
}
}

CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
return v1.x * v2.y - v1.y * v2.x;
}

CGPoint CGPointSubtract_AGK(CGPoint p1, CGPoint p2)
{
return (CGPoint){p1.x - p2.x, p1.y - p2.y};
}

{
return (CGPoint){p1.x + p2.x, p1.y + p2.y};
}

CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
return v1.x * v2.y - v1.y * v2.x;
}

CGPoint CGPointMultiply_AGK(CGPoint p1, CGFloat factor)
{
return (CGPoint){p1.x * factor, p1.y * factor};
}
``````

Python版本的iMalc的答案：

``````def find_intersection( p0, p1, p2, p3 ) :

s10_x = p1[0] - p0[0]
s10_y = p1[1] - p0[1]
s32_x = p3[0] - p2[0]
s32_y = p3[1] - p2[1]

denom = s10_x * s32_y - s32_x * s10_y

if denom == 0 : return None # collinear

denom_is_positive = denom > 0

s02_x = p0[0] - p2[0]
s02_y = p0[1] - p2[1]

s_numer = s10_x * s02_y - s10_y * s02_x

if (s_numer < 0) == denom_is_positive : return None # no collision

t_numer = s32_x * s02_y - s32_y * s02_x

if (t_numer < 0) == denom_is_positive : return None # no collision

if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision

# collision detected

t = t_numer / denom

intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ]

return intersection_point
``````

A C++ program to check if two given line segments intersect

``````#include <iostream>
using namespace std;

struct Point
{
int x;
int y;
};

// Given three colinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(Point p, Point q, Point r)
{
if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
return true;

return false;
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
// See 10th slides from following link for derivation of the formula
// http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);

if (val == 0) return 0;  // colinear

return (val > 0)? 1: 2; // clock or counterclock wise
}

// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
// Find the four orientations needed for general and
// special cases
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);

// General case
if (o1 != o2 && o3 != o4)
return true;

// Special Cases
// p1, q1 and p2 are colinear and p2 lies on segment p1q1
if (o1 == 0 && onSegment(p1, p2, q1)) return true;

// p1, q1 and p2 are colinear and q2 lies on segment p1q1
if (o2 == 0 && onSegment(p1, q2, q1)) return true;

// p2, q2 and p1 are colinear and p1 lies on segment p2q2
if (o3 == 0 && onSegment(p2, p1, q2)) return true;

// p2, q2 and q1 are colinear and q1 lies on segment p2q2
if (o4 == 0 && onSegment(p2, q1, q2)) return true;

return false; // Doesn't fall in any of the above cases
}

// Driver program to test above functions
int main()
{
struct Point p1 = {1, 1}, q1 = {10, 1};
struct Point p2 = {1, 2}, q2 = {10, 2};

doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

p1 = {10, 0}, q1 = {0, 10};
p2 = {0, 0}, q2 = {10, 10};
doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

p1 = {-5, -5}, q1 = {0, 0};
p2 = {1, 1}, q2 = {10, 10};
doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

return 0;
}
``````

``````int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
//L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3)
int d;
d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
if(!d)
return 0;
p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d;
p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d;
return 1;
}

int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y)
{
return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2;

}

int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y))
return 0;

return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y);
}
``````

Here's a basic implementation of a line segment in C#, with corresponding intersection detection code. It requires a 2D vector/point struct called `Vector2f` , though you can replace this with any other type that has X/Y properties. You could also replace `float` with `double` if that suits your needs better.

This code is used in my .NET physics library, Boing .

``````public struct LineSegment2f
{
public Vector2f From { get; }
public Vector2f To { get; }

public LineSegment2f(Vector2f @from, Vector2f to)
{
From = @from;
To = to;
}

public Vector2f Delta => new Vector2f(To.X - From.X, To.Y - From.Y);

/// <summary>
/// Attempt to intersect two line segments.
/// </summary>
/// <remarks>
/// Even if the line segments do not intersect, <paramref name="t"/> and <paramref name="u"/> will be set.
/// If the lines are parallel, <paramref name="t"/> and <paramref name="u"/> are set to <see cref="float.NaN"/>.
/// </remarks>
/// <param name="other">The line to attempt intersection of this line with.</param>
/// <param name="intersectionPoint">The point of intersection if within the line segments, or empty..</param>
/// <param name="t">The distance along this line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
/// <param name="u">The distance along the other line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
/// <returns><c>true</c> if the line segments intersect, otherwise <c>false</c>.</returns>
public bool TryIntersect(LineSegment2f other, out Vector2f intersectionPoint, out float t, out float u)
{
var p = From;
var q = other.From;
var r = Delta;
var s = other.Delta;

// t = (q − p) × s / (r × s)
// u = (q − p) × r / (r × s)

var denom = Fake2DCross(r, s);

if (denom == 0)
{
// lines are collinear or parallel
t = float.NaN;
u = float.NaN;
intersectionPoint = default(Vector2f);
return false;
}

var tNumer = Fake2DCross(q - p, s);
var uNumer = Fake2DCross(q - p, r);

t = tNumer / denom;
u = uNumer / denom;

if (t < 0 || t > 1 || u < 0 || u > 1)
{
// line segments do not intersect within their ranges
intersectionPoint = default(Vector2f);
return false;
}

intersectionPoint = p + r * t;
return true;
}

private static float Fake2DCross(Vector2f a, Vector2f b)
{
return a.X * b.Y - a.Y * b.X;
}
}
``````

I read these algorithm from the book "multiple view geometry"

following text using

' as transpose sign

* as dot product

x as cross product, when using as operator

### 1. line definition

a point x_vec = (x, y)' lies on the line ax + by + c = 0

we denote L = (a, b, c)', the point as (x, y, 1)' as homogeneous coordinates

the line equation can be written as

(x, y, 1)(a, b, c)' = 0 or x' * L = 0

### 2. intersection of lines

we have two lines L1=(a1, b1, c1)', L2=(a2, b2, c2)'

assume x is a point, a vector, and x = L1 x L2 (L1 cross product L2).

be careful, x is always a 2D point, please read homogeneous coordinates if you are confused about (L1xL2) is a three elements vector, and x is a 2D coordinates.

according to triple product, we know that

L1 * ( L1 x L2 ) = 0, and L2 * (L1 x L2) = 0, because of L1,L2 co-plane

we substitute (L1xL2) with vector x, then we have L1*x=0, L2*x=0, which means x lie on both L1 and L2, x is the intersection point.

be careful, here x is homogeneous coordinates, if the last element of x is zero, it means L1 and L2 are parallel.

I think there is a much much simpler solution for this problem. I came up with another idea today and it seems to work just fine (at least in 2D for now). All you have to do, is to calculate the intersection between two lines, then check if the calculated intersection point is within the boundig boxes of both line segments. If it is, the line segments intersect. 而已。

This is how I calculate the intersection (I don't know anymore where I found this code snippet)

``````Point3D
``````

comes from

``````System.Windows.Media.Media3D

public static Point3D? Intersection(Point3D start1, Point3D end1, Point3D start2, Point3D end2) {

double a1 = end1.Y - start1.Y;
double b1 = start1.X - end1.X;
double c1 = a1 * start1.X + b1 * start1.Y;

double a2 = end2.Y - start2.Y;
double b2 = start2.X - end2.X;
double c2 = a2 * start2.X + b2 * start2.Y;

double det = a1 * b2 - a2 * b1;
if (det == 0) { // lines are parallel
return null;
}

double x = (b2 * c1 - b1 * c2) / det;
double y = (a1 * c2 - a2 * c1) / det;

return new Point3D(x, y, 0.0);
}
``````

and this is my (simplified for the purpose of the answer) BoundingBox class:

``````public class BoundingBox {
private Point3D min = new Point3D();
private Point3D max = new Point3D();

public BoundingBox(Point3D point) {
min = point;
max = point;
}

public Point3D Min {
get { return min; }
set { min = value; }
}

public Point3D Max {
get { return max; }
set { max = value; }
}

public bool Contains(BoundingBox box) {
bool contains =
min.X <= box.min.X && max.X >= box.max.X &&
min.Y <= box.min.Y && max.Y >= box.max.Y &&
min.Z <= box.min.Z && max.Z >= box.max.Z;
return contains;
}

public bool Contains(Point3D point) {
return Contains(new BoundingBox(point));
}

}
``````

I tried some of these answers, but they didnt work for me (sorry guys); after some more net searching I found this .

With a little modification to his code I now have this function that will return the point of intersection or if no intersection is found it will return -1,-1.

``````    Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
'//  Determines the intersection point of the line segment defined by points A and B
'//  with the line segment defined by points C and D.
'//
'//  Returns YES if the intersection point was found, and stores that point in X,Y.
'//  Returns NO if there is no determinable intersection point, in which case X,Y will
'//  be unmodified.

Dim distAB, theCos, theSin, newX, ABpos As Double

'//  Fail if either line segment is zero-length.
If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)

'//  Fail if the segments share an end-point.
If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)

'//  (1) Translate the system so that point A is on the origin.
bx -= ax
by -= ay
cx -= ax
cy -= ay
dx -= ax
dy -= ay

'//  Discover the length of segment A-B.
distAB = Math.Sqrt(bx * bx + by * by)

'//  (2) Rotate the system so that point B is on the positive X axis.
theCos = bx / distAB
theSin = by / distAB
newX = cx * theCos + cy * theSin
cy = cy * theCos - cx * theSin
cx = newX
newX = dx * theCos + dy * theSin
dy = dy * theCos - dx * theSin
dx = newX

'//  Fail if segment C-D doesn't cross line A-B.
If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)

'//  (3) Discover the position of the intersection point along line A-B.
ABpos = dx + (cx - dx) * dy / (dy - cy)

'//  Fail if segment C-D crosses line A-B outside of segment A-B.
If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)

'//  (4) Apply the discovered position to line A-B in the original coordinate system.
'*X=Ax+ABpos*theCos
'*Y=Ay+ABpos*theSin

'//  Success.
Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function
``````

If each side of the rectangle is a line segment, and the user drawn portion is a line segment, then you need to just check the user drawn segment for intersection with the four side line segments. This should be a fairly simple exercise given the start and end points of each segment.

There seems to be some interest in Gavin's answer for which cortijon proposed a javascript version in the comments and iMalc provided a version with slightly fewer computations . Some have pointed out shortcomings with various code proposals and others have commented on the efficiency of some code proposals.

The algorithm provided by iMalc via Gavin's answer is the one that I am currently using in a javascript project and I just wanted to provide a cleaned up version here if it may help anyone.

``````// Some variables for reuse, others may do this differently
var p0x, p1x, p2x, p3x, ix,
p0y, p1y, p2y, p3y, iy,
collisionDetected;

// do stuff, call other functions, set endpoints...

// note: for my purpose I use |t| < |d| as opposed to
// |t| <= |d| which is equivalent to 0 <= t < 1 rather than
// 0 <= t <= 1 as in Gavin's answer - results may vary

var lineSegmentIntersection = function(){
var d, dx1, dx2, dx3, dy1, dy2, dy3, s, t;

dx1 = p1x - p0x;      dy1 = p1y - p0y;
dx2 = p3x - p2x;      dy2 = p3y - p2y;
dx3 = p0x - p2x;      dy3 = p0y - p2y;

collisionDetected = 0;

d = dx1 * dy2 - dx2 * dy1;

if(d !== 0){
s = dx1 * dy3 - dx3 * dy1;
if((s <= 0 && d < 0 && s >= d) || (s >= 0 && d > 0 && s <= d)){
t = dx2 * dy3 - dx3 * dy2;
if((t <= 0 && d < 0 && t > d) || (t >= 0 && d > 0 && t < d)){
t = t / d;
collisionDetected = 1;
ix = p0x + t * dx1;
iy = p0y + t * dy1;
}
}
}
};
``````

This based on Gareth Ree's answer. It also returns the overlap of the line segments if they do. Coded in C++, V is a simple vector class. Where the cross product of two vectors in 2D returns a single scalar. It was tested and passed by my schools automatic testing system.

``````//Required input point must be colinear with the line
bool on_segment(const V& p, const LineSegment& l)
{
//If a point is on the line, the sum of the vectors formed by the point to the line endpoints must be equal
V va = p - l.pa;
V vb = p - l.pb;
R ma = va.magnitude();
R mb = vb.magnitude();
R ml = (l.pb - l.pa).magnitude();
R s = ma + mb;
bool r = s <= ml + epsilon;
return r;
}

//Compute using vector math
// Returns 0 points if the lines do not intersect or overlap
// Returns 1 point if the lines intersect
//  Returns 2 points if the lines overlap, contain the points where overlapping start starts and stop
std::vector<V> intersect(const LineSegment& la, const LineSegment& lb)
{
std::vector<V> r;

//http://.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
V oa, ob, da, db; //Origin and direction vectors
R sa, sb; //Scalar values
oa = la.pa;
da = la.pb - la.pa;
ob = lb.pa;
db = lb.pb - lb.pa;

if (da.cross(db) == 0 && (ob - oa).cross(da) == 0) //If colinear
{
if (on_segment(lb.pa, la) && on_segment(lb.pb, la))
{
r.push_back(lb.pa);
r.push_back(lb.pb);
dprintf("colinear, overlapping\n");
return r;
}

if (on_segment(la.pa, lb) && on_segment(la.pb, lb))
{
r.push_back(la.pa);
r.push_back(la.pb);
dprintf("colinear, overlapping\n");
return r;
}

if (on_segment(la.pa, lb))
r.push_back(la.pa);

if (on_segment(la.pb, lb))
r.push_back(la.pb);

if (on_segment(lb.pa, la))
r.push_back(lb.pa);

if (on_segment(lb.pb, la))
r.push_back(lb.pb);

if (r.size() == 0)
dprintf("colinear, non-overlapping\n");
else
dprintf("colinear, overlapping\n");

return r;
}

if (da.cross(db) == 0 && (ob - oa).cross(da) != 0)
{
dprintf("parallel non-intersecting\n");
return r;
}

//Math trick db cross db == 0, which is a single scalar in 2D.
//Crossing both sides with vector db gives:
sa = (ob - oa).cross(db) / da.cross(db);

//Crossing both sides with vector da gives
sb = (oa - ob).cross(da) / db.cross(da);

if (0 <= sa && sa <= 1 && 0 <= sb && sb <= 1)
{
dprintf("intersecting\n");
r.push_back(oa + da * sa);
return r;
}

dprintf("non-intersecting, non-parallel, non-colinear, non-overlapping\n");
return r;
}
``````

1. 端點a和b位於段CD的相對側。
2. 端點c和d位於段AB的另一側。

``````Intersect(a, b, c, d)
if CCW(a, c, d) == CCW(b, c, d)
return false;
else if CCW(a, b, c) == CCW(a, b, d)
return false;
else
return true;
``````

``````bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){
return (x >= x0) && (x <= x1);
}

bool NuGeometry::FindIntersection(const double& x0, const double& y0,
const double& x1, const double& y1,
const double& a0, const double& b0,
const double& a1, const double& b1,
double& xy, double& ab) {
// four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1
// returned values xy and ab are the fractional distance along xy and ab
// and are only defined when the result is true

bool partial = false;
double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1);
if (denom == 0) {
xy = -1;
ab = -1;
} else {
xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom;
partial = NuGeometry::IsBetween(0, xy, 1);
if (partial) {
// no point calculating this unless xy is between 0 & 1
ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom;
}
}
if ( partial && NuGeometry::IsBetween(0, ab, 1)) {
ab = 1-ab;
xy = 1-xy;
return true;
}  else return false;
}
``````

p + t r = q + u s

p + t r ）× s =（ q + u s ）× s

tr × s ）=（ q - p ）× s

t =（ q - p ）× s /（ r × s

p + t r ）× r =（ q + u s ）× r

us × r ）=（ p - q ）× r

u =（ p - q ）× r /（ s × r

u =（ q - p ）× r /（ r × s

1. 如果r × s = 0且（ q - p ）× r = 0，則兩條線共線。

在這種情況下，用第一條線段（ p + t r ）的公式表示第二段（ qq + s ）的端點：

t 0 =（ q - p ）· r /（ r · r

t 1 =（ q + s - p ）· r /（ r · r ）= t 0 + s · r /（ r · r

如果t 0t 1之間的間隔與區間[0,1]相交，則線段共線並重疊; 否則它們是共線的並且不相交。

請注意，如果sr指向相反方向，則s · r <0，因此要檢查的區間是[ t 1t 0 ]而非[ t 0t 1 ]。

2. 如果r × s = 0且（ q - p ）× r ≠0，那麼這兩條線是平行且不相交的。

3. 如果r × s ≠0且0≤t≤1且0≤u≤1，則兩條線段在點p + t r = q + u s處相遇。

4. 否則，兩條線段不平行，但不相交。

`````` // calculates intersection and checks for parallel lines.
// also checks that the intersection point is actually on
// the line segment p1-p2
Point findIntersection(Point p1,Point p2,
Point p3,Point p4) {
float xD1,yD1,xD2,yD2,xD3,yD3;
float dot,deg,len1,len2;
float segmentLen1,segmentLen2;
float ua,ub,div;

// calculate differences
xD1=p2.x-p1.x;
xD2=p4.x-p3.x;
yD1=p2.y-p1.y;
yD2=p4.y-p3.y;
xD3=p1.x-p3.x;
yD3=p1.y-p3.y;

// calculate the lengths of the two lines
len1=sqrt(xD1*xD1+yD1*yD1);
len2=sqrt(xD2*xD2+yD2*yD2);

// calculate angle between the two lines.
dot=(xD1*xD2+yD1*yD2); // dot product
deg=dot/(len1*len2);

// if abs(angle)==1 then the lines are parallell,
// so no intersection is possible
if(abs(deg)==1) return null;

// find intersection Pt between two lines
Point pt=new Point(0,0);
div=yD2*xD1-xD2*yD1;
ua=(xD2*yD3-yD2*xD3)/div;
ub=(xD1*yD3-yD1*xD3)/div;
pt.x=p1.x+ua*xD1;
pt.y=p1.y+ua*yD1;

// calculate the combined length of the two segments
// between Pt-p1 and Pt-p2
xD1=pt.x-p1.x;
xD2=pt.x-p2.x;
yD1=pt.y-p1.y;
yD2=pt.y-p2.y;
segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);

// calculate the combined length of the two segments
// between Pt-p3 and Pt-p4
xD1=pt.x-p3.x;
xD2=pt.x-p4.x;
yD1=pt.y-p3.y;
yD2=pt.y-p4.y;
segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);

// if the lengths of both sets of segments are the same as
// the lenghts of the two lines the point is actually
// on the line segment.

// if the point isn’t on the line, return null
if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01)
return null;

// return the valid intersection
return pt;
}

class Point{
float x,y;
Point(float x, float y){
this.x = x;
this.y = y;
}

void set(float x, float y){
this.x = x;
this.y = y;
}
}
``````

``````int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
s10_x = p1_x - p0_x;
s10_y = p1_y - p0_y;
s32_x = p3_x - p2_x;
s32_y = p3_y - p2_y;

denom = s10_x * s32_y - s32_x * s10_y;
if (denom == 0)
return 0; // Collinear
bool denomPositive = denom > 0;

s02_x = p0_x - p2_x;
s02_y = p0_y - p2_y;
s_numer = s10_x * s02_y - s10_y * s02_x;
if ((s_numer < 0) == denomPositive)
return 0; // No collision

t_numer = s32_x * s02_y - s32_y * s02_x;
if ((t_numer < 0) == denomPositive)
return 0; // No collision

if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
return 0; // No collision
// Collision detected
t = t_numer / denom;
if (i_x != NULL)
*i_x = p0_x + (t * s10_x);
if (i_y != NULL)
*i_y = p0_y + (t * s10_y);

return 1;
}
``````