Line–line intersection
Given two points on each line segment

The intersection point above is for the infinitely long lines defined by the points, rather than the line segments between the points, and can produce an intersection point not contained in either of the two line segments. In order to find the position of the intersection in respect to the line segments, we can define lines L and L in terms of first degree Bézier parameters:

(where t and u are real numbers). The intersection point of the lines is found with one of the following values of t or u, where

and

with

There will be an intersection if 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1. The intersection point falls within the first line segment if 0 ≤ t ≤ 1, and it falls within the second line segment if 0 ≤ u ≤ 1. These inequalities can be tested without the need for division, allowing rapid determination of the existence of any line segment intersection before calculating its exact point.
keywords:letter_frequency