Finding 2D points

I am going to post some basic geometry solutions that I will reference in future posts. These are solutions I've used in several games for a variety of cameras.

Some problems with game cameras can be solved by projecting points into a horizontal plane, and here are planar line intersection and constructing a circle from three points.



Intersection of two lines in a plane

Given two lines, L0 and L1

L0 = P0 + s D0

L1 = P1 +  t D1

Find a point along both lines s and t where L0 and L1 intersects.

P0 + s D0 = P1 + t D1

An intersection between two lines in the plane is a point.

Replacing P0 and P1 with Pd = P1 - P0 and solving this for x and y gives:

denominator = D0y D1x - D0x D1y

s = (Pdy D1x - Pdx D1y) / denominator

t = (Pdx D0y - Pdy D0x) / denominator

Constructing a circle from 3 points in the plane

Finding the minimal cylinder that fits a set of points is a good way to collect a number of camera targets into a single volume. Taking the farthest two points projected into a horizontal 2D plane easily generates a cylinder but points can still be outside. If a point is outside a new cylinder can be generated from the original two points and the new point until all points have been tested.

Finding the circle from three points on the circumference.

The solution to this comes from a compass and ruler solution. The idea is to construct two lines from the three points and then find the intersection of the perpendicular lines passing through the midpoints of the original lines.

The reason that this works is fairly simple; the center of the circle is the same distance from any two points on the circumference so the middle of the two points must be on a line intersects with the center point and that is perpendicular to the line between the two points.

From this point it is easy to construct an intersection between two lines to find the center and the distance from the center to any of the points is the radius.

Given three points A, B, C we can form two lines:

D0 = (By - Ay,  Ax - Bx)

L0 = (A + B) / 2 + s D0

D1 = (Cy - By,  Bx - Cx)

L1 = (B + C) / 2 + t D1

Which can be used to find the center O by finding the line intersection in the plane:

P = (B + C) / 2 - (A + B) / 2 = (C - A) / 2

denom = (By - Ay) * (Bx - Cx) - (Ax - Bx) * (Cy - By)

If the denominator is 0 then the points line on a line and can not form a circle.

s = (Py (Cy - By) - Px (Bx - Cx)) / denom

t = (Px (Ax - Bx) - Py (By - Ay)) / denom

Either s or t can be used to find the center:

O = L0 + s * D0

O is the circle center and the radius can be trivially calculated by the length from the center to any of the original points.