Line and Curve Intersection

The Central Idea

Two geometric objects intersect wherever the same point belongs to both.

If one object is described by

and another by

then an intersection point satisfies both equations:

Computational intersection is therefore a combination of geometry, algebra, and verification.

Intersection Is a Set

Two objects do not always meet in exactly one point.

Their intersection may contain:

• no points;
• one point;
• several isolated points;
• a whole segment or curve;
• infinitely many points when the objects coincide.

A correct intersection algorithm must distinguish these possibilities.

Lines, Rays, and Segments Are Different Objects

A line extends infinitely in both directions.

A ray starts at one endpoint and extends infinitely in one direction.

A segment is restricted to the points between two endpoints.

Two supporting lines may intersect even when the corresponding segments do not. For that reason, solving the line equations is often only the first stage of a segment-intersection algorithm.

Parametric Form of a Line

A line through a point \(P\) in direction \(\mathbf{r}\ne\mathbf{0}\) can be written

In coordinates,

so

Parametric form is especially useful because the parameter tells us where the point lies along the geometric object.

Parametric Form of a Segment

The segment from \(P\) to \(Q\) can be represented as

with the restriction

The same formula represents the entire supporting line if \(t\) is allowed to range over all real numbers.

The parameter restriction is what turns a line computation into a segment computation.

Line-Line Intersection in Parametric Form

Suppose two lines are

and

At an intersection,

Rearranging gives

This is a \(2\times2\) linear system for the unknown parameters \(t\) and \(u\).

Using the Two-Dimensional Cross Product

Let

If

then the two direction vectors are not parallel and the supporting lines intersect in exactly one point.

The parameters are

and

Why the Cross-Product Formula Works

Begin with

Rearrange:

Take the two-dimensional cross product with \(\mathbf{s}\):

Since

the \(u\)-term disappears, giving the formula for \(t\).

Example: Intersecting Two Lines

Consider

and

Here,

The denominator is

Since it is nonzero, the lines meet in exactly one point.

Finishing the Line-Line Example

Compute

Then

Therefore,

The intersection point is

Parallel Lines

If

then the direction vectors are parallel.

There are then two possibilities:

• the lines are distinct and have no intersection;
• the lines are collinear and have infinitely many common points.

A second test is needed to distinguish them.

Testing Whether Parallel Lines Are Collinear

If the direction vectors are parallel, test whether

If this is also zero, \(Q\) lies on the line through \(P\) in direction \(\mathbf{r}\), so the two lines are collinear.

Otherwise, they are distinct parallel lines.

The Complete Line-Line Classification

For

compute

• If \(D\ne0\), the lines have exactly one intersection.
• If \(D=0\) and \((Q-P)\times\mathbf{r}\ne0\), they are parallel and distinct.
• If \(D=0\) and \((Q-P)\times\mathbf{r}=0\), they are collinear.

Segment-Segment Intersection

Let

and

with

If the supporting lines meet at parameters \(t\) and \(u\), then the segments intersect at that point exactly when both parameters lie within their allowed intervals.

Segment Parameters Are Membership Tests

Suppose the supporting lines intersect at

The point lies on the second segment because

but it lies beyond the endpoint of the first segment because

Therefore, the lines intersect but the segments do not.

Orientation-Based Segment Intersection

Another important method uses orientation predicates.

For segments \(AB\) and \(CD\), compute

In the noncollinear case, the segments properly cross when \(C\) and \(D\) lie on opposite sides of line \(AB\), and \(A\) and \(B\) lie on opposite sides of line \(CD\).

The Proper-Crossing Test

When no orientation value is zero, a proper intersection occurs when

The first inequality says \(C\) and \(D\) lie on opposite sides of the supporting line through \(A\) and \(B\).

The second says the corresponding statement is true in the other direction.

Endpoint and Collinear Cases

If one orientation value is zero, an endpoint may lie directly on the other segment.

For example, if

then \(A\), \(B\), and \(C\) are collinear. We must still check whether \(C\) lies between \(A\) and \(B\).

Collinearity alone does not guarantee segment membership.

Point-on-Segment Test

A point \(R=(x_R,y_R)\) lies on segment \(PQ\) when two conditions hold.

First, the three points are collinear:

Second, the coordinates of \(R\) fall within the bounding ranges:

Together, these conditions distinguish the segment from its infinite supporting line.

Collinear Segment Overlap

When two segments are collinear, their intersection may be:

• empty;
• a single shared endpoint;
• a nonzero-length overlapping segment;
• the entirety of one segment if it lies inside the other.

This is qualitatively different from an ordinary single-point intersection.

Reducing Collinear Overlap to One Dimension

Once collinearity is known, overlap can be tested using one coordinate axis along which the segment has nonzero extent.

For intervals

and

overlap exists when

Geometric overlap has been reduced to interval overlap.

Bounding Boxes as an Early Rejection Test

Before performing a more detailed segment-intersection calculation, compare the axis-aligned bounding boxes of the segments.

If the boxes do not overlap, the segments cannot intersect.

This is a necessary condition, not a sufficient one.

Bounding-box rejection is useful because it is inexpensive and can eliminate many impossible cases quickly.

Line Intersection in Implicit Form

A line may also be written

Two lines

and

form a linear system.

Its determinant is

Solving Two Implicit Lines

When

the lines intersect at exactly one point:

and

This is Cramer's rule applied to the line-intersection system.

Vertical Lines Cause No Special Problem in Implicit Form

A vertical line

can be written

The implicit and parametric methods therefore avoid the division-by-zero difficulty that appears when all lines are forced into slope-intercept form.

Line-Circle Intersection

Consider a circle with center \(C\) and radius \(r\):

Let a line be

Substitute the line into the circle equation:

This produces a quadratic equation in \(t\).

Deriving the Line-Circle Quadratic

Define

Then

Expanding with dot products gives

Therefore,

with

The Discriminant Classifies Line-Circle Intersection

For

compute

• If \(\Delta<0\), the line misses the circle.
• If \(\Delta=0\), the line is tangent to the circle.
• If \(\Delta>0\), the line crosses the circle in two points.

One algebraic quantity classifies the geometric relationship.

Example: Horizontal Line through a Circle

Consider the circle

and the horizontal line

Substitute:

Then

so

The two intersection points are

Tangency as a Repeated Solution

A tangent line touches a circle at exactly one point.

Algebraically, the corresponding quadratic has a repeated root:

This is an important recurring connection: geometric tangency often appears algebraically as a repeated solution.

Segment-Circle Intersection

If the object is a segment rather than an infinite line, solve the same quadratic using

but retain only solutions satisfying

A supporting line may intersect a circle twice while the finite segment intersects once or not at all.

Circle-Circle Intersection

Consider two circles:

and

Let

be the distance between their centers.

The value of \(d\) relative to \(r_1\) and \(r_2\) determines the intersection type.

Classifying Two Circles by Center Distance

• If \(d>r_1+r_2\), the circles are separate.
• If \(d=r_1+r_2\), they are externally tangent.
• If \(|r_1-r_2|
• If \(d=|r_1-r_2|\) and \(d\ne0\), they are internally tangent.
• If \(0
• If \(d=0\) and \(r_1=r_2\), the circles coincide.

The coincident case contains infinitely many intersection points.

Constructing the Circle-Circle Intersection Points

Let

be the unit vector from \(C_1\) to \(C_2\).

The distance from \(C_1\) to the chord midpoint along this direction is

The half-chord length is

Finishing the Circle-Circle Construction

The midpoint of the common chord is

If

choose a perpendicular unit vector

The two intersection points are

and

When \(h=0\), the two formulas produce the same tangent point.

Curves Can Be Represented in Several Ways

A curve may be given explicitly:

It may be implicit:

Or it may be parametric:

The best intersection method depends strongly on the representation.

Intersection of Two Explicit Curves

If

and

then intersection points occur where

Equivalently, define

and solve

Curve intersection has become a root-finding problem.

Example: A Line and a Parabola

Find the intersections of

and

Set the expressions equal:

Rearranging gives

Factor:

Finishing the Line-Parabola Example

The \(x\)-coordinates are

and

Substituting into \(y=x+2\) gives

and

Therefore, the intersections are

Intersection of Parametric Curves

Suppose

and

An intersection satisfies

and

This produces two equations in the two unknown parameters \(t\) and \(u\).

Different Parameters Can Describe the Same Point

At a parametric intersection, it is not generally necessary that

The two curves may reach the same geometric point at different parameter values.

The correct condition is equality of positions:

Root Finding for General Curve Intersections

Many intersection equations cannot be solved conveniently with elementary algebra.

Then the task becomes numerical root finding.

Common methods include:

• bisection;
• Newton's method;
• secant methods;
• subdivision;
• hybrid methods that combine bracketing with faster local iteration.

These methods approximate the parameter or coordinate values at which the curves meet.

Bisection for an Intersection Equation

Suppose curve intersection has been reduced to

If

and \(h\) is continuous on \([a,b]\), then a root lies between \(a\) and \(b\).

Bisection repeatedly halves the interval and retains a subinterval that still brackets a sign change.

Newton's Method for an Intersection Equation

If \(h\) is differentiable and an initial estimate \(x_0\) is available, Newton's method uses

Near a suitable simple root, this can converge very rapidly.

However, Newton's method is not guaranteed to converge from every starting point, and it requires special care when \(h'(x_n)\) is zero or very small.

Tangent Intersections Are Numerically Delicate

If two curves merely touch, the difference function

may have a repeated root.

In such a case, \(h(x)\) may touch zero without changing sign.

Therefore, a sign-change search alone can miss tangential intersections.

Subdivision and Bounding Regions

A practical strategy for complex curves is to enclose pieces of each curve in simple bounding regions.

If two bounding regions do not overlap, the enclosed curve pieces cannot intersect.

If they do overlap, subdivide the curve pieces into smaller pieces and test again.

Repeated subdivision narrows the search to small regions that may contain intersections.

Broad Phase and Narrow Phase

Many geometric systems use two stages.

The broad phase uses inexpensive tests such as bounding boxes to eliminate pairs that clearly cannot intersect.

The narrow phase applies the more exact intersection test only to the surviving candidates.

This pattern is fundamental in collision detection, graphics, CAD, and spatial databases.

Candidate Generation and Verification

Intersection algorithms often have two conceptual stages:

1. generate candidate intersection points or parameters;
2. verify that each candidate satisfies the original geometric constraints.

For example, solving two supporting lines may produce a candidate point, while the parameter restrictions determine whether that point belongs to the actual segments.

Exact and Approximate Intersections

In symbolic mathematics, an intersection may be represented exactly:

In numerical software, the same point may be stored approximately:

The representation affects how equality, tangency, parallelism, and boundary membership should be tested.

Near-Parallel Lines

The line-line formulas divide by

If this quantity is extremely small, the lines are nearly parallel.

Small denominator values can amplify numerical error, so robust software should not treat every nonzero floating-point denominator as equally safe.

Using Tolerances Carefully

In approximate arithmetic, one may replace

with a test such as

But the appropriate \(\varepsilon\) depends on coordinate scale and the quantities being compared.

A tolerance is a numerical policy, not a mathematical identity.

Duplicate Intersections

A numerical or subdividing algorithm may discover the same geometric intersection more than once.

This commonly occurs near:

• shared endpoints;
• subdivision boundaries;
• tangent contacts;
• overlapping curve pieces.

A complete implementation may therefore need a deduplication step.

Intersection Multiplicity

Algebra can record more than the location of an intersection.

If

has a repeated root, the intersection has higher algebraic multiplicity.

For example,

has a double root at \(x=2\).

This often corresponds to tangential contact rather than an ordinary crossing.

Intersection versus Crossing

Two objects can intersect without crossing through one another.

A tangent line and a circle share one point, but the line does not pass through the circle at that point in the same way a secant does.

Similarly, two curves may touch and reverse relative position rather than crossing.

Computational systems often need to classify the type of contact, not just detect that contact occurred.

Intersection versus Overlap

A point intersection has zero geometric length.

An overlapping pair of collinear segments may share an entire interval of points.

Therefore, returning only a single point for every successful intersection can lose important information.

The output type should match the possible geometry.

Degenerate Inputs

Intersection algorithms must account for degenerate objects.

Examples include:

• a segment whose endpoints are identical;
• a line direction vector equal to zero;
• a circle with radius zero;
• two coincident lines;
• two coincident circles;
• curves whose parameter intervals collapse to a point.

These cases should be classified explicitly rather than allowed to create accidental division by zero.

A Zero-Length Segment Is a Point

If

then

becomes

The segment has collapsed to one point.

Intersecting it with another object becomes a point-membership test.

Verification by Substitution

Once a candidate point \(X\) is found, substitute it into the defining equations whenever practical.

For a line-circle intersection, verify that

and

Verification catches algebraic mistakes and invalid candidates introduced by transformations or numerical approximation.

Common Error: Solving the Supporting Lines but Ignoring Segment Bounds

A solution of

proves that the supporting lines meet.

For segments, it is still necessary to check

and

Common Error: Treating Parallel as Automatically Disjoint

If

the lines are parallel in direction, but they may also be collinear.

The additional test

distinguishes coincident support from distinct parallel lines.

Common Error: Using Only Bounding Boxes

Overlapping bounding boxes do not prove that the underlying objects intersect.

Bounding boxes are excellent rejection tests, but they generally provide only a necessary condition for intersection.

A more specific geometric test must follow.

Common Error: Missing Tangency with a Sign-Change Test

A root-finding scan that looks only for

can miss a repeated root because the function may touch zero and remain the same sign on both sides.

Tangent intersections require additional detection strategies.

Common Error: Returning One Point for an Overlap

Collinear segments can share an entire interval.

Coincident lines can share infinitely many points.

An intersection routine should distinguish a single-point result from an overlapping result when the application needs that information.

Common Error: Ignoring Numerical Scale

A fixed absolute tolerance may behave poorly when coordinates vary by many orders of magnitude.

Robust intersection code should consider:

• coordinate scale;
• relative error;
• near-parallel configurations;
• near-tangent configurations;
• whether exact predicates are required.

A Reliable Procedure for Two-Line Intersection

1. Represent each line as a point plus a direction vector.
2. Compute \(D=\mathbf{r}\times\mathbf{s}\).
3. If \(D\ne0\), solve for \(t\) and \(u\).
4. Construct the intersection point from either line.
5. If \(D=0\), test whether the lines are collinear.
6. Classify the result as unique, parallel-distinct, or coincident.
7. Use scale-aware numerical comparisons when arithmetic is approximate.

A Reliable Procedure for Segment Intersection

1. Reject pairs whose bounding boxes do not overlap.
2. Compute orientation values or solve the supporting-line parameters.
3. Handle ordinary crossings.
4. Check endpoint-on-segment cases.
5. Handle collinear overlap separately.
6. Distinguish no intersection, one point, and overlapping segment.
7. Verify numerical boundary cases carefully.

A Reliable Procedure for Line-Curve Intersection

1. Choose a convenient representation of the line and curve.
2. Substitute one representation into the other when possible.
3. Reduce the problem to an equation in one parameter or coordinate.
4. Solve exactly when practical.
5. Otherwise use an appropriate numerical root-finding method.
6. Retain only roots within any required parameter interval.
7. Construct the corresponding points.
8. Verify each candidate against the original geometry.
9. Deduplicate repeated numerical detections when necessary.

Practice 1: Two Lines

Find the intersection of

and

Practice 2: Parallel or Collinear?

Classify

and

Practice 3: Segment Parameters

Two supporting lines meet at

Do the corresponding segments intersect at that point?

Practice 4: Point on Segment

Determine whether

lies on the segment from

to

Practice 5: Line and Circle

Find the intersections of

and

Practice 6: Tangent Line

Determine how many points of intersection are shared by

and

Practice 7: Two Explicit Curves

Find the intersection points of

and

Practice 8: Circle Classification

Two circles have radii

and their centers are \(8\) units apart. Classify their intersection.

Practice 9: Collinear Overlap

On a common horizontal line, one segment spans

and another spans

Find their overlap.

Practice 10: Why a Sign Change Can Fail

Explain why checking only for a sign change can miss the root of

Practice Answers

Practice 1

Here,

Therefore,

Practice 2

The direction vectors are parallel because

Also,

which is itself a multiple of \((2,4)\). Therefore, the lines are

Practice 3

The first parameter satisfies

but

Therefore,

Practice 4

The points are collinear, and \(3\) lies between \(1\) and \(5\) in both coordinates.

Practice 5

Substitute \(y=4\):

Therefore,

Practice 6

Substitute \(y=3\):

There is one intersection:

The line is tangent to the circle.

Practice 7

Set the equations equal:

Thus \(x=1\) or \(x=2\). The corresponding \(y\)-values are \(1\) and \(4\).

Practice 8

Since

the circles are

They share exactly one point.

Practice 9

The overlap begins at

and ends at

Therefore, the shared interval is

Practice 10

The function

is nonnegative on both sides of \(x=2\).

It reaches zero at \(x=2\) but does not change sign. Therefore, a search that detects roots only by sign changes can miss this repeated root.

What to Remember

Intersection algorithms solve the same basic problem in many different forms: find points that satisfy the conditions of two geometric objects at once.

• parametric lines convert intersection into parameter solving;
• cross products classify parallelism and support efficient line-line formulas;
• segment intersection adds parameter or boundary restrictions;
• orientation predicates provide a powerful segment-crossing test;
• collinear overlap must be handled separately from ordinary crossings;
• line-circle intersection reduces to a quadratic equation;
• the discriminant distinguishes no contact, tangency, and two crossings;
• curve intersection often reduces to root finding;
• bounding regions provide efficient early rejection;
• candidate points should be verified against the original geometry;
• near-parallel, tangent, overlapping, and degenerate cases require special care.

The computational habit is to separate geometry into representation, candidate generation, classification, and verification.

Where We Go Next

Line and curve intersection asks whether two geometric objects share a point. The next lesson reverses the perspective and asks whether a single point belongs to a larger bounded region.

Point-in-Region Tests develops methods for deciding whether a point lies inside, outside, or on the boundary of polygons and other spatial regions.