# 04.16.2022 - Math/Circle and Ray Intersection

Let $P$ be the intersection point, $A$ is the anchor point of the ray, $B$ is the endpoint of the ray (assuming the ray is length-limited) and $C$ is the circle's center point, with radius $r$.

$$
\\begin{align}
a &= (B_x - A_x) ^ 2 + (B_y - A_y) ^ 2 \\\\
b &= 2((B_x - A_x)(A_x - C_x) + (B_y - A_y)(A_y - C_y)) \\\\
c &= (A_x - C_x) ^ 2 + (A_y - C_y) ^ 2 - r ^ 2 \\\\
\\Delta &= b ^ 2 - 4ac
\\end{align}
$$

Now we have 3 cases:

- $\Delta < 0$: ray does not intersect the circle
- $\Delta = 0$: ray intersects the circle in one point (tangent)
- $\Delta > 0$: ray intersects the circle in two points (secant)

If $\Delta = 0$, we have $t = \tfrac{-b}{2a}$, and if $t \geq 0$, we can calculate the position of $P$ as:

$$\\begin{align}
  P_x &= t(B_x - A_x) + A_x \\\
  P_y &= t(B_y - A_y) + A_y
\\end{align}$$

If $\Delta > 0$, we have:

$$\\begin{align}
  t_1 &= \\tfrac{-b -\\sqrt{\\Delta}}{2a} \\\\
  t_2 &= \\tfrac{-b +\\sqrt{\\Delta}}{2a} \\\\
\\end{align}$$

In this case, if $t_i \geq 0$ then the two intersection points can be calculated as:

$$\\begin{align}
  P_{i_x} &= t_i(B_x - A_x) + A_x \\\\
  P_{i_y} &= t_i(B_y - A_y) + A_y
\\end{align}$$

Implementation in JavaScript:

```javascript
function getIntersectionPoint(ray, circle) {
  const [A, B] = ray;
  const C = { x: circle.x, y: circle.y };
  const r = circle.radius;

  const a = (B.x - A.x) ** 2 + (B.y - A.y) ** 2;
  const b = 2 * ((B.x - A.x) * (A.x - C.x) + (B.y - A.y) * (A.y - C.y));
  const c = (A.x - C.x) ** 2 + (A.y - C.y) ** 2 - r ** 2;
  const discriminant = b ** 2 - 4 * a * c;

  const result = [];
  
  if(discriminant === 0) {
    const t = -b / (2 * a);

    if(t >= 0) {
      const x = t * (B.x - A.x) + A.x;
      const y = t * (B.y - A.y) + A.y;

      result.push({ x, y });
    }
  } else if(discriminant > 0) {
    const discriminantSqrt = Math.sqrt(discriminant);
    const t1 = (-b + discriminantSqrt) / (2 * a);
    const t2 = (-b - discriminantSqrt) / (2 * a);

    if(t1 >= 0) {
      const x = t1 * (B.x - A.x) + A.x;
      const y = t1 * (B.y - A.y) + A.y;

      result.push({ x, y })
    }

    if(t2 >= 0) {
      const x = t2 * (B.x - A.x) + A.x;
      const y = t2 * (B.y - A.y) + A.y;

      result.push({ x, y });
    }
  }

  return result;
}
```

**References:**

- https://sszczep.github.io/ray-casting-in-2d-game-engines/
- https://sszczep.github.io/ray-casting-in-2d-game-engines/cheatsheet.html
- https://mathworld.wolfram.com/Circle-LineIntersection.html

Circle and Ray Intersection

# 04.15.2022 - Math/Prime Factorization Uniqueness

In mathematics, the [fundamental theorem of arithmetic](https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic) states that: **"Any integer number larger than 1 can be written as a product of prime numbers in one and only one way".**

![](_meta/prime-factorization.png)

No matter how you come up with the *prime factorization*, the set of *prime factors* might have a different order, but they are always the same set.

In algorithm problem solving, the uniqueness of a prime factorization can be applied in some situations, for example, to check if two strings are made up from the same set of characters, with a different arrangement (anagram).

The idea to solve this kind of problem is, to map the characters in each string to a prime number: 

![](_meta/prime-anagram-map.png)

Then multiply them together, if they made up the same integer number, then they're anagram.

![](_meta/prime-anagram-multiply.png)

---

The proof of the uniqueness can be found on [Page 16, Section 2](https://www.google.com/books/edition/Elementary_Number_Theory/tr7SzBTsk1UC?hl=en&gbpv=1&pg=PA16&printsec=frontcover) of the **Elementary Number Theory: Second Edition** book. But Wikipedia has a [great summarization](https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic#Uniqueness):

Suppose we have an integer $n$ that has two distinct prime factorizations $n = p_1 \times p_2 \times p_3 \times \cdots \times p_j$ and $n = q_1 \times q_2 \times q_3 \times \cdots \times q_k$, where each $p_i$ and $q_i$ is a prime.

We see that $p_1$ divides $n$, so $p_1$ divides $q_1 \times q_2 \times q_3 \times \cdots \times q_k$. By [Euclid's lemma](https://en.wikipedia.org/wiki/Euclid%27s_lemma), we have that $p_1$ divides some $q_i$, let's say $q_1$.

Since $p_1$ and $q_1$ are both prime, they must be the same, so $p_1 = q_1$. Cancel both $p_1$ and $q_1$ from the two prime factorizations, we get:

$$
p_2 \times p_3 \times \cdots \times p_j = q_2 \times q_3 \times \cdots \times q_k
$$

Continue the process, eventually, we will find that each $p$ is a $q$. After each cancellation, we cannot run out of $p$ before all the $q$ are gone. This means, $p_1 \times p_2 \times p_3 \times \cdots \times p_j$ are just a rearrangement of $q_1 \times q_2 \times q_3 \times \cdots \times q_k$. The two factorizations are just differ in the order of the factors.



Prime Factorization

# 02.02.2022 - Math/Interpolation Methods

**Interpolation** is a type of estimation method for finding new data points based on the range of a discrete set of known data points.

The most basic kind of interpolation is **Linear Interpolation** (Lerp), it transitions from one value to another at a constant rate. Defined by:

$$
\text{lerp}(a, b, t) = a (1 - t) + b t
$$

It's implementation in Rust should look like this:

```rust
fn lerp(a: f32, b: f32, t: f32) -> f32 {
    return a * (1.0 - t) + b * t;
}
```

The interpolated points between two points A and B should form a straight line, and if we animate the object along the line, it should look like this:

![](_meta/lerp-anim.gif)

**Cosine Interpolation** is the interpolation method that can generate a smooth acceleration and deceleration between the two data points, can be defined by:

$$
\text{cosine}(a, b, t) = \text{lerp}(a, b, \frac{1-\cos(\pi t)}{2})
$$

Implemented in Rust:

```rust
fn cosine(a: f32, b: f32, t: f32) -> f32 {
    let t2 = (1.0 - (t * PI).cos()) / 2.0;
    return lerp(a, b, t2);
}
```

The acceleration should happen from the beginning of the line, and slow down at the end of the line:

![](_meta/cosine-anim.gif)

If we want to control the **acceleration** on just one end of the line, we can use different formulas:

$$
\text{acceleration}(a, b, t) = \text{lerp}(a, b, t^2)
$$

Implemented in Rust:

```rust
fn acceleration(a: f32, b: f32, t: f32) -> f32 {
    let t2 = t * t;
    return lerp(a, b, t2);
}
```

Here's how it look when animated:

![](_meta/acce-anim.gif)

Or **deceleration** at the end of the line:

$$
\text{deceleration}(a, b, t) = \text{lerp}(a, b, 1-(1-t)^2)
$$

Implemented in Rust:

```rust
fn deceleration(a: f32, b: f32, t: f32) -> f32 {
    let t2 = 1.0 - (1.0 - t) * (1.0 - t);
    return lerp(a, b, t2);
}
```

Animated result:

![](_meta/dece-anim.gif)

Above are just some common interpolation methods, for more, please check http://paulbourke.net/miscellaneous/interpolation/

Aside from animation, we can use interpolation functions to generate color, or dynamically generate font size on the web page, create a dynamic layout,... See more details about web-related techniques with interpolation at https://www.smashingmagazine.com/2017/05/fluid-responsive-typography-css-poly-fluid-sizing/

---

Demo source can be found here: https://github.com/huytd/interpolation-demo

Interpolation Methods

# 01.21.2022 - Math/Count number of digits with Logarithm

Suppose that a number $n$ has $d$ digits, then:

$$
10^{d-1} \leq n \lt 10^{d}
$$

Because $10^d$ is the smallest integer with $d + 1$ digits.

Now, take logs base 10 of this relation:

$$
log_{10}{(10^{d-1})} \leq log_{10}{n} \lt log_{10}{(10^d)}
$$

This becomes:

$$
d-1 \leq log_{10}{n} \lt d
$$

If you now take the integer part of $log_{10}{n}$, throwing away everything to the right of the decimal point, you will get $\lfloor log_{10}{n} \rfloor = d-1$. Thus, $d = \lfloor log_{10}{n} \rfloor + 1$.

For example, $234$ is a $3$ digits number, take the logs base 10:

$$
log_{10}{(234)} \approx 2.369215
$$

If we take the integer part and throw away everything to the right of the decimal point, it's $2$.

The calculation can be done programmatically like this:

```cpp
#include <math>

int digits = log10(n) + 1;
```

**Source:** [Proof: How many digits does a number have? - StackExchange Mathematics](https://math.stackexchange.com/questions/231742/proof-how-many-digits-does-a-number-have-lfloor-log-10-n-rfloor-1)

