# Vector math for line-to-line intersection

While learning about vectors, I worked through this to better understand line-to-line intersection math instead of simply using it “because it works”.

``````final int N = 4; // Fixed number to make two segments
int MAX_DIST = 20;

// Control points
PVector[] p = new PVector[N];

boolean held = false;
int nearest = -1;
float startx = 0;
float starty = 0;
float DIV_TOO_FAR = 0.00001;

// Calculates the intersection with vectors.
// Surely this uses the same math as solving the equations.
// Input:
//   Two line segments defined by points "a-b" and "c-d"
//   A PVector instance to hold the location of the intersection
// Returns:
//   True if segments cross, else false
//   Result vector is updated with the intersection point
boolean intersection(PVector a, PVector b, PVector c, PVector d, PVector result)
{
// center everything on point "d"
PVector axis = c.copy().sub(d);
float axLen = axis.mag();
axis.normalize();
PVector workingA = a.copy().sub(d);
PVector workingB = b.copy().sub(d);

// create a perpendicular vector to "c-d"
PVector rightang = new PVector(-axis.y, axis.x);

// In short: rotate everything so "c-d" becomes the y-axis
//   rightang becomes x-axis
PVector mappedA = new PVector(workingA.dot(rightang), workingA.dot(axis));
PVector mappedB = new PVector(workingB.dot(rightang), workingB.dot(axis));
// More detail: mappedA and -B are projections of "a" and "b" onto the lines
//   "c-d" and "rightang", creating Axis Aligned 2D coordinates

// Get the axis-aligned segment
PVector dir = mappedA.sub(mappedB);

// This is the same math used for 2D axis-aligned-bounding-boxes but only used
//   for one intersection instead of two edges
// In other words:
//   "How much do we change segment 'a-b's length to reach segment 'c-d'?"
// Result can be +/- INF, meaning segments are parallel
// Relying on the floating point to handle div by 0.0 --> INF
//   is implementation dependant. Your hardware may vary.
float tx = 1.0 / DIV_TOO_FAR;
if (abs(dir.x) > DIV_TOO_FAR)
tx = -mappedB.x / dir.x;

// when the original line segment "a-b" is extended/shortened by tx,
//   the end of that segment is the intersecting point
result.set(inters);

// Segment/segment intersection:
// Logic is that if the first segment would have to expand or reverse to
//   reach the point at 'inters', then the segments do not cross
float ty = inters.sub(d).dot(axis);
boolean intersecting = (tx >= 0) && (tx <= 1.0) && (ty >= 0) && (ty <= axLen);

return intersecting;
}

void setup()
{
size(800,600,P2D);

// Initial points, this setup is parallel
p = new PVector(width/4, height/4);
p = new PVector(width - (width/4), height/4);
p = new PVector(width/4, height - (height/4));
p = new PVector(width - (width/4), height - (height/4));

noFill();
frameRate(60);
background(0);
}

void mouseMoved()
{
float neardist = width + height;
for (int i=0; i<N; i++)
{
float nd = dist(p[i].x,p[i].y, mouseX,mouseY);
if (nd < neardist)
{
nearest = i;
neardist = nd;
}
}
if (MAX_DIST < neardist)
{
nearest = -1;
}
}

void mousePressed()
{
if (-1 != nearest)
{
held = true;
startx = mouseX - p[nearest].x;
starty = mouseY - p[nearest].y;
}
}

void mouseReleased()
{
held = false;
}

void draw()
{
// This section allows you to move the control points
if (held)
{
p[nearest].x = constrain(mouseX-startx,0,width); // suggested by jeremydouglass
p[nearest].y = constrain(mouseY-starty,0,height);
background(0);
}

// Show control points
for (int i=0; i<N; i++)
{
if (i == nearest)
{
stroke(0,255,0);
}
else
{
stroke(0,0,255);
}
ellipse( p[i].x,p[i].y, MAX_DIST,MAX_DIST );
}

PVector cros = new PVector();
boolean test = intersection(p, p, p ,p, cros);

int col = test ? color(255,0,0) : color(255,0,255);
stroke(col);
line(p.x,p.y, p.x,p.y);
line(p.x,p.y, p.x,p.y);

stroke(0,255,0);
ellipse(cros.x,cros.y, 4,4);
}``````
3 Likes

Nice. I did something similar but this is better. Will be using this soon for a printmaking project!