Introduction

While working on my 'Searching, generating, validating and rendering Euclidean tilings' project, I wanted to draw some annotations for representing geometric reflection transforms (!!! Fig 404 !!!). I thought "I want the reflection line to extend across the whole render area" - and that sent me on a little journey to figure out how. Writing this article is my way of remembering what I learned.

Fig. - Live rendered example of an annotated reflective transform

Wasm loading...

Terminology

Before we get to the maths, let's learn some concepts. Here's a quick glossary of some things we'll be using:

Line segment: When we say 'a line' this actually refers to a line that goes on forever in both directions. A line segment is a line that has a start and an end point.
slope: The slope of a line is the ratio of the vertical change (y2 - y1) to the horizontal change (x2 - x1). It's the gradient of the line and we'll refer to this below with the letter m. There's 2 things to note about the slope. When a line is completely horizontal the slope is 0, and when a line is completely vertical the slope is Infinity.
y-intercept: This is the point where a line crosses the y-axis or in other words it's the value of y when x == 0 and we'll refer to it with the letter b.

Line intersection

In this section, we're going to look at finding the intersection of 2 lines first. The information we'll be working with is the endpoints of 2 line segments.

y = m * x + b

This equation is a useful one to remember. Given an x value, the slope and y-intercept we can find any y value on a line. We can also rearrange this equation to find the x value given a y value (!!! Fig 404 !!!).

It's useful to also take the time to understand what this equation is doing. m represents the rate of change, it's simply a scalar value that for every 1 unit of x changes, how many units of y change. However, this assumes that the line is flat. The b part of the equation is the offset of the line from the origin.

Fig. - The components of the equation for a line, in Rust

// slope
let m = (y2 - y1) / (x2 - x1);

// y-intercept
let b = y1 - m * x1;

// function to find x given y
let x = |y: f64| (y - b) / m;

// function to find y given x
let y = |x: f64| m * x + b;

To find the intersection of 2 lines we need to find the x and y values where the lines cross. We can do this by setting the equations of the lines equal to each other and solving for x. We can then use this x value to find the y value.

Let's say we have 2 line segments. The first line segment is defined by the points (x1, y1) and (x2, y2). The second line segment is defined by the points (x3, y3) and (x4, y4) (!!! Fig 404 !!!).

Fig. - A breakdown of the components of the equation for finding the intersection of 2 lines

// Slopes of the lines
let m1 = (y2 - y1) / (x2 - x1);
let m2 = (y4 - y3) / (x4 - x3);

// Y-intercepts of the lines
let b1 = y1 - m1 * x1;
let b2 = y3 - m2 * x3;

// X value of the intersection
let ix = (b2 - b1) / (m1 - m2);

// Y value of the intersection using our original equation
let iy = m1 * x + b1;

Even if the slopes of the lines are so gradual that they are effectively parallel they will eventually intersect at some point, however precisely parallel lines never will so we need to handle this case. Luckily, this is easy to check for by comparing the slopes of the lines !!! Fig 404 !!!.

Fig. - Amended code to check if the lines are parallel before finding the intersection point

// Slopes of the lines
let m1 = (y2 - y1) / (x2 - x1);
let m2 = (y4 - y3) / (x4 - x3);

if ((m1 - m2).abs() < f64::EPSILON) {
  // The lines are parallel
  return None;
}

Bounds intersection

Back to the main problem of this article which is working with a line segment that exists within a bounded area (a rectangle). We're not going to think of this area as a rectangle but as 4 separate line segments. With this in mind, it's now easy to use what we've learned above to find the intersection of this line with the lines of the bounding area.

Something that you may have realised is that a continuous line drawn within the bounds of 4 other continuous lines will always intersect with all 4 lines (unless it's parallel to one of them).

This is a fairly trivial problem to solve, by finding the intersection points of all 4 lines and then checking which intersection points are within the bounds of the rectangle (!!! Fig 404 !!!).

Fig. - Checking if a point is within the bounds of a rectangle

let within_x = x >= min_x && x <= max_x;
let within_y = y >= min_y && y <= max_y;
let within_bounds = within_x && within_y;

In fact, because of this property and because the lines we'll be working with are perfectly horizontal or vertical, we can simplify the problem further. All we need to do is plug in the parallel axis value to the line equation to find the intersection point. For example (!!! Fig 404 !!!).

Fig. - Checking if a point is within the bounds of a rectangle

let m = (y2 - y1) / (x2 - x1);
let b = y1 - m * x1;
let x = |y: f64| (y - b) / m;
let y = |x: f64| m * x + b;

// The points of intersection with the bounds lines
let x_for_min_y = x(min_y);
let x_for_max_y = x(max_y);
let y_for_min_x = y(min_x);
let y_for_max_x = y(max_x);

// Find which bound line segments the line segment intersects with
let intercepts_min_y = x_for_min_y >= min_x && x_for_min_y <= max_x;
let intercepts_max_y = x_for_max_y >= min_x && x_for_max_y <= max_x;
let intercepts_min_x = y_for_min_x >= min_y && y_for_min_x <= max_y;
let intercepts_max_x = y_for_max_x >= min_y && y_for_max_x <= max_y;

With the above code, we can now find the intersection points on a bounds line segments. For example when intercepts_min_y is true, then we know our ix1 value is x_for_min_y and iy1 value is min_y.

A rotational bug

In the code above, we used the y1 and x1 as the starting point of the line segment. This is fine and produces the same result as using the y2 and x2 but the now inferred direction of the line has some implications.

To not introduce any graphical and animation bugs down the line by accidentally flipping the line segment, we need to make sure that the extended line segment points returned are in the given direction.

In fact, as well as annotating a reflective transform, I needed to annotate rotational transforms too (!!! Fig 404 !!!). The problem with this is that I only needed to extend the line segment in one direction and therefor needed to control which point was the point that extended.

Fig. - Live rendered example of an annotated rotational transform

Wasm loading...

I figured two ways to solve this problem, and I think it's matter of preference which one you choose.

Method 1: Using distance alone by determining whichever points is closest. A point that extended away in the direction from another point will always be closer than the point at the end of the line segment. This is because the point at the end of the line segment is the same distance away plus the length of the line segment.

Method 2: Using angles by determining the angle between the center of the line segment and the points, we can then know which bounding line segment they are pointing at.

I went with Method 2, because I had already implemented this before I thought of Method 1. I plan to benchmark the two methods to see which is faster, and maybe I'll come back and swap these. But they essentially do the same thing.

atan2

This mathematical function gives us the angular value of a point relative to another point. This other point we can think of as the center of a circle. Unlike when we think of a clock face, where 12 o'clock is 0 degrees, in atan2, 3 o'clock is 0 degrees. Going clockwise decreasing from 0 to a bounded value of -π, and anticlockwise increases from 0 to a bounded value of π. At 9 o'clock it jumps from -π to π.

Fig. - Checking if a point is within the bounds of a rectangle

// The mid point of the line segment
let cx = (x1 + x2) * 0.5;
let cy = (y1 + y2) * 0.5;

// The angular values of the points relative to the center
let a1 = (y1 - cy).atan2(x1 - cx);

// For the top bounding line intersection
if intercepts_min_y {
  // Check to see if the first point we were
  // given is the point that extends upwards
  if atan_p1 < 0.0 {
    ix1 = x_for_min_y;
    iy1 = min_y;
  } else {
    ix2 = x_for_min_y;
    iy2 = min_y;
  }
}

Those assigning conditions need to be done for each of the 4 bounding lines. The code above is just a snippet, but essentially we need to just check that the direction of the point and the line segment match up.

Summary

That's it! The full implementation can be found here, and you can play around with the example on this page that uses that Rust implementation through Wasm.

Introduction

Fig. - Live rendered example of an annotated reflective transform

Wasm loading...

Terminology

Before we get to the maths, let's learn some concepts. Here's a quick glossary of some things we'll be using:

Line segment: When we say 'a line' this actually refers to a line that goes on forever in both directions. A line segment is a line that has a start and an end point.
slope: The slope of a line is the ratio of the vertical change (y2 - y1) to the horizontal change (x2 - x1). It's the gradient of the line and we'll refer to this below with the letter m. There's 2 things to note about the slope. When a line is completely horizontal the slope is 0, and when a line is completely vertical the slope is Infinity.
y-intercept: This is the point where a line crosses the y-axis or in other words it's the value of y when x == 0 and we'll refer to it with the letter b.

Line intersection

In this section, we're going to look at finding the intersection of 2 lines first. The information we'll be working with is the endpoints of 2 line segments.

y = m * x + b

Fig. - The components of the equation for a line, in Rust

// slope
let m = (y2 - y1) / (x2 - x1);

// y-intercept
let b = y1 - m * x1;

// function to find x given y
let x = |y: f64| (y - b) / m;

// function to find y given x
let y = |x: f64| m * x + b;

Fig. - A breakdown of the components of the equation for finding the intersection of 2 lines

// Slopes of the lines
let m1 = (y2 - y1) / (x2 - x1);
let m2 = (y4 - y3) / (x4 - x3);

// Y-intercepts of the lines
let b1 = y1 - m1 * x1;
let b2 = y3 - m2 * x3;

// X value of the intersection
let ix = (b2 - b1) / (m1 - m2);

// Y value of the intersection using our original equation
let iy = m1 * x + b1;

Fig. - Amended code to check if the lines are parallel before finding the intersection point

// Slopes of the lines
let m1 = (y2 - y1) / (x2 - x1);
let m2 = (y4 - y3) / (x4 - x3);

if ((m1 - m2).abs() < f64::EPSILON) {
  // The lines are parallel
  return None;
}

Bounds intersection

Something that you may have realised is that a continuous line drawn within the bounds of 4 other continuous lines will always intersect with all 4 lines (unless it's parallel to one of them).

This is a fairly trivial problem to solve, by finding the intersection points of all 4 lines and then checking which intersection points are within the bounds of the rectangle (!!! Fig 404 !!!).

Fig. - Checking if a point is within the bounds of a rectangle

let within_x = x >= min_x && x <= max_x;
let within_y = y >= min_y && y <= max_y;
let within_bounds = within_x && within_y;

Fig. - Checking if a point is within the bounds of a rectangle

let m = (y2 - y1) / (x2 - x1);
let b = y1 - m * x1;
let x = |y: f64| (y - b) / m;
let y = |x: f64| m * x + b;

// The points of intersection with the bounds lines
let x_for_min_y = x(min_y);
let x_for_max_y = x(max_y);
let y_for_min_x = y(min_x);
let y_for_max_x = y(max_x);

// Find which bound line segments the line segment intersects with
let intercepts_min_y = x_for_min_y >= min_x && x_for_min_y <= max_x;
let intercepts_max_y = x_for_max_y >= min_x && x_for_max_y <= max_x;
let intercepts_min_x = y_for_min_x >= min_y && y_for_min_x <= max_y;
let intercepts_max_x = y_for_max_x >= min_y && y_for_max_x <= max_y;

A rotational bug

Fig. - Live rendered example of an annotated rotational transform

Wasm loading...

I figured two ways to solve this problem, and I think it's matter of preference which one you choose.

Method 2: Using angles by determining the angle between the center of the line segment and the points, we can then know which bounding line segment they are pointing at.

atan2

Fig. - Checking if a point is within the bounds of a rectangle

// The mid point of the line segment
let cx = (x1 + x2) * 0.5;
let cy = (y1 + y2) * 0.5;

// The angular values of the points relative to the center
let a1 = (y1 - cy).atan2(x1 - cx);

// For the top bounding line intersection
if intercepts_min_y {
  // Check to see if the first point we were
  // given is the point that extends upwards
  if atan_p1 < 0.0 {
    ix1 = x_for_min_y;
    iy1 = min_y;
  } else {
    ix2 = x_for_min_y;
    iy2 = min_y;
  }
}

Summary

That's it! The full implementation can be found here, and you can play around with the example on this page that uses that Rust implementation through Wasm.