Two drawn segments can cross, share an endpoint, overlap along a line or miss one another. A program must distinguish these cases from coordinates, including vertical segments and segments whose endpoints coincide. Computing slopes first introduces avoidable divisions and exceptional vertical-line cases. An orientation determinant gives the side information we need directly.
We will use integer coordinates and exact arithmetic. The main task is a predicate: classify the intersection, rather than necessarily construct its coordinates. Keeping those tasks separate lets the classification stay exact even when the actual intersection has noninteger coordinates.
Derive the orientation test from two displacement vectors
Definition 8.2.1
(Orientation in an ordinary Cartesian coordinate system)
For points , and , define
When , a positive result means that is to the left of directed line , a negative result means right, and zero means on the line. This convention assumes the usual axes: x increases to the right and y increases upward.
If , the expression is zero for every , but there is no uniquely directed supporting line. A zero-length segment therefore needs the membership conditions below, not an interpretation of this degenerate expression as a side test.
The formula is the determinant of the vectors and . Its absolute value is the area of the parallelogram they span, or twice the triangle area. Reversing the first direction changes its sign. Translating every point by the same vector changes neither displacement and hence leaves the result unchanged.
Orientation is not itself a signed distance. For , divide it by to obtain the signed perpendicular distance to the directed line. For example, , and give orientation 10 but signed distance . The determinant is enough for deciding sides; computing this distance is unnecessary for intersection classification.
Collinearity is only part of being on a segment
Definition 8.2.2
(Closed segment)
The closed segment includes both endpoints and consists of the points with . In particular, if , it contains just that one point.
Proposition 8.2.3
(Closed-segment membership)
A point belongs to closed segment exactly when its orientation is zero and both coordinate bounds hold:
Proof
(Zero orientation fixes the line, the bounds fix the parameter)
Membership clearly implies these conditions. Conversely, if , zero orientation puts on the supporting line, so for a real . At least one displacement coordinate is nonzero; the corresponding coordinate bound forces . If , the two bounds instead force . Thus the same test handles a point segment correctly.
Proof X-ray
Why one nonzero coordinate is enough
Each hypothesis is used exactly once. Zero orientation says that and are parallel; since , this gives a real parameter with . The coordinate bound is then applied to a coordinate in which is nonzero: , so , and the statement that lies between and is exactly . The other coordinate bound then follows automatically and is not an independent check. The non-routine move is choosing a coordinate in which the segment is not constant, which avoids slopes and vertical special cases. The argument splits at , where no parameter exists and the bounds pin instead. Without the bounds the argument stops at " is on the line".
Orientation alone is therefore never a membership test, as the next concrete case shows.
Counterexample mode
Zero orientation does not mean inside the endpoints
Points , and are collinear, so the third point has orientation zero relative to the first two. It is nevertheless outside their closed segment because its x coordinate exceeds two. Testing only zero orientation would mistake an infinite supporting line for a finite segment.
Use two side tests for a proper crossing
For segments and , define
A proper crossing means one intersection point strictly inside both noncollinear segments. It occurs exactly when have strictly opposite signs and have strictly opposite signs. Zero is not an opposite sign for this test; it belongs to the boundary cases.
Theorem 8.2.4
(Proper crossing criterion)
Let and be segments of positive length that do not lie on one line. They have a common point that is an interior point of both segments exactly when have strictly opposite signs and have strictly opposite signs.
Proof
(Orientation is affine along a segment)
Along , the orientation relative to equals .
Suppose have strictly opposite signs. Then this expression has a unique zero, at . The lines are not parallel, since parallel directions would make the two orientations equal. Thus the unique intersection of the two supporting lines is strictly inside segment . The opposite signs of give the same conclusion inside for the same unique line intersection, so that point is interior to both segments.
Conversely, let with be a common point that is also interior to . Then lies on line , so . Hence are either both zero or strictly opposite. Both zero would put and on line , contradicting that the segments are not on one line. So are strictly opposite, and the same argument with the roles exchanged gives the strict opposition of .
Proof X-ray
Each sign pair certifies only one segment
The engine of the proof is that orientation is affine along a segment, so its two endpoint values decide where it vanishes. Strictness is what places the zero in the open interval: a zero endpoint puts the intersection at an endpoint, which belongs to the boundary cases. Equal strict signs put the zero outside the segment or make the lines parallel. Non-collinearity is used only for necessity, to rule out . The first pair says that line cuts segment ; the second says that line cuts segment . The proof closes because both statements concern the same point, the unique intersection of the two lines. Dropping one pair keeps only half of the conclusion.
Each pair certifies one segment only, and the next example makes the gap concrete.
Counterexample mode
Straddling just one supporting line is insufficient
Let , , and . The values , show that crosses the line through .
But and have the same sign. The line intersection is , beyond the endpoint , so the segments are disjoint. The second pair of signs is what excludes this case.
Worked example 8.2.5
(An exact crossing without slope calculations)
Take , , and . The four orientations are
Both sign pairs are strictly opposite. The two segment parametrizations meet at parameter on each segment, giving point . The predicate itself needs only the signs, not the division used to construct that point.
Integer input does not imply an integer intersection: segments from to and from to properly cross at . Rounding this point to an integer coordinate is not part of the exact predicate.
Handle collinear and degenerate cases deliberately
If all four orientations are zero and at least one segment has nonzero length, all endpoints lie on its supporting line. Order the points lexicographically: compare x coordinates first, then y coordinates. On a nonvertical line, this order follows x along the line; on a vertical line, it follows y. Thus the overlap can be tested as an interval in that order.
Set the candidate overlap endpoints to
where minima and maxima use lexicographic order. If , the segments are disjoint. If , they share one point. If , they overlap along a positive-length segment.
Two point segments also have all four orientations zero, even when their points differ and no unique common supporting line is specified. Their lexicographic intervals are singletons, so this same overlap rule correctly decides whether the two points coincide.
If the four orientations are not all zero, a zero orientation may still indicate a shared endpoint or a point segment lying on the other segment. Apply the complete on_segment test to the corresponding endpoint. A zero orientation without its coordinate bounds is insufficient.
Worked example 8.2.6
(Boundary cases belong to the closed-segment contract)
The examples below lie on the x axis unless specified otherwise.
| First segment | Second segment | Classification |
|---|---|---|
| to | to | One-point contact |
| to | to | Positive-length overlap |
| to | to | Disjoint |
| Point | to | One-point contact |
| Point | to | Disjoint |
| Point | Point | One-point contact |
| Point | Point | Disjoint |
Here “point” means the segment whose two endpoints coincide. A one-point contact can occur in the interior of the other segment; it need not be an endpoint of both.
Worked example 8.2.7
(A T-junction needs zero orientation plus membership)
Take , , and . Then and , so the first pair is not strictly opposite and the segments do not cross properly. Also and , which are strictly opposite. Since , test against : its orientation is zero and , , so lies on segment . The classification is touch: the vertical segment ends in the interior of the horizontal one. Zero orientation alone would not have decided this; had been , the orientation would still be zero but the bounds would fail.
Proposition 8.2.8
(Exact classification of two closed segments)
Let and be closed segments, possibly of zero length, with orientations as above.
- If , the intersection is the lexicographic interval from to : empty if , one point if , and a segment of positive length if .
- Otherwise the intersection has at most one point. It is nonempty exactly when the segments cross properly, or when some endpoint with zero orientation passes the closed-segment membership test against the other segment.
Proof
(Split by the configuration of the supporting lines)
Suppose all four orientations are zero. If has positive length, then puts and on line ; if has positive length, then puts and on line ; if both are points, there are just two points. In every case all endpoints lie on one line, where lexicographic order agrees with position along the line, so each segment is the interval between its endpoints in that order. The intersection of two such intervals is , empty when .
Now suppose the four orientations are not all zero, and let be a common point. If one segment is a point, say , then lies on , which by the membership proposition means and passes the bounds test; the case is symmetric. If both have positive length and their lines are parallel, then either the lines differ, so there is no common point, or they coincide, so all four orientations would be zero. Otherwise the lines meet in exactly one point, so is that point and the intersection has at most one point. If is interior to both segments, the segments cross properly by the criterion above. If not, is an endpoint of one segment lying on the other, so that endpoint has zero orientation and passes the membership test. Conversely, each listed condition exhibits a common point, by the crossing criterion or by membership.
Common mistake
(Testing products with a non-strict inequality)
A tempting shortcut reports an intersection when and . For , , and , all four orientations are zero, so both products are zero and the shortcut reports contact. The closed segments are disjoint: and , so . The collinear case must be separated first and decided by the interval test.
Common mistake
(Comparing only x coordinates on a vertical line)
The segments from to and from to have the same single value , so an overlap test on alone sees equal intervals and reports contact. The segments are disjoint. Lexicographic order compares when the values tie, giving and , so .
An exact integer classification function
The input points are two-element integer tuples, as a precondition. The function does not validate coordinate types or tuple shapes. It returns cross for a proper crossing, touch for a one-point boundary/degenerate contact, overlap for a positive-length collinear intersection, and disjoint otherwise. These strings classify the intersection; they do not return its coordinates.
def orient(a, b, p):
return ((b[0] - a[0]) * (p[1] - a[1])
- (b[1] - a[1]) * (p[0] - a[0]))
def on_segment(a, b, p):
return (orient(a, b, p) == 0
and min(a[0], b[0]) <= p[0] <= max(a[0], b[0])
and min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))
def opposite(x, y):
return (x < 0 < y) or (y < 0 < x)
def segment_relation(a, b, c, d):
o1, o2 = orient(a, b, c), orient(a, b, d)
o3, o4 = orient(c, d, a), orient(c, d, b)
if o1 == o2 == o3 == o4 == 0:
lower = max(min(a, b), min(c, d))
upper = min(max(a, b), max(c, d))
if lower > upper:
return "disjoint"
return "touch" if lower == upper else "overlap"
if opposite(o1, o2) and opposite(o3, o4):
return "cross"
if ((o1 == 0 and on_segment(a, b, c))
or (o2 == 0 and on_segment(a, b, d))
or (o3 == 0 and on_segment(c, d, a))
or (o4 == 0 and on_segment(c, d, b))):
return "touch"
return "disjoint"
For example, segment_relation((0,0),(4,2),(1,3),(3,-1)) returns cross, while the one-sided straddling counterexample returns disjoint. Reversing either segment's endpoints or exchanging the two segments preserves the classification, although some orientation signs change.
The function also handles vertical segments, repeated endpoints and equal point segments directly. There is no division, slope comparison or chosen tolerance. This exact-integer contract does not justify replacing every zero test by an arbitrary floating-point : approximate coordinates require a separate numerical model and analysis.
Account for arithmetic before choosing a fixed-width type
The code uses a constant number of arithmetic operations and comparisons. With unbounded integer coordinates, that is an operation count, not a claim of constant bit-level runtime. If coordinate magnitudes are at most , each difference has magnitude at most , each product at most , and the determinant has the conservative bound
This is sufficient for reasoning about required range; it is not claimed sharp. For coordinates of bits, differences and determinants have bits, and the multiplication cost must be included. Python integers keep the calculations exact. A fixed-width port must use a sufficiently wide representation for the differences and products themselves, not widen a result only after overflow has already occurred.
Testing opposite signs by comparisons, as above, avoids multiplying merely to check whether that product is negative. Multiplying two determinants would require a larger intermediate range than either determinant alone. The geometry only needs their signs.
Exercises and worked solutions
Quick check
(For , and , calculate the orientation and signed distance to the directed line. Why is normalization unnecessary for deciding which side contains ?)
Divide by the length of only when a distance is needed.
Solution · Answer
The orientation is . Since , dividing by gives signed distance . The positive normalizing factor cannot change the sign, so orientation alone correctly reports the left side.
Quick check
(For , , and , give the four orientation values. Why does the first opposite-sign pair not prove segment intersection?)
Compute and as well as and .
Solution · Answer
They are . Segment crosses the infinite line through , but that intersection is at outside . The other sign pair is not opposite, so the complete proper-crossing test rejects the case.
Quick check
(On the axis, compare segments from to and from to , then compare segments from to and from to . What are and , and how do the classifications differ?)
Compute and as lexicographic maximum and minimum.
Solution · Answer
For the first pair, the candidate overlap runs from to , so it has positive length and returns overlap. For the second, , giving one-point touch. Strict versus equal endpoint order is what distinguishes the two.
Quick check
(When and the other segment runs from to , why are zero orientations not enough? What happens if the point is instead , or if both segments are that same point?)
Compare singleton intervals.
Solution · Answer
All orientations are zero, but the singleton interval at does not overlap the other endpoint interval, so the answer is disjoint. A point at gives touch. Two segments consisting of the same point also give touch; the bounding/ordered-interval conditions handle these cases without inventing a directed line for a point.
Quick check
(If every point is translated by one fixed vector, what happens to the four orientations? If and are exchanged, what happens to the first pair of signs and to the final intersection classification?)
Orientation is a determinant of two displacement vectors.
Solution · Answer
Translation changes no displacement vector, so every orientation value is unchanged. Reversing negates and exchanges . Opposite-sign, zero and segment membership conditions still describe the same geometric segments, so the classification is unchanged.
Quick check
(If every coordinate has magnitude at most , derive the displayed conservative determinant bound. Why can checking opposite signs directly be preferable to computing the product of two orientation values in a fixed-width implementation?)
Bound each difference, then each product.
Solution · Answer
Each coordinate difference is at most in magnitude. Each of the two products is at most , so their difference has magnitude at most . A product of two such determinants can need much more range; direct positive/negative comparisons avoid that extra product while making exactly the sign decision required by the predicate.