Sort BoundingBoxes for Fun (in TypeScript)
Tags: typescript, programming
Published: 2022-11-06 20:07:32

There is no reason for this post other than that I wanted to code something fun again!

So come along and let us sort some boxes in a 2D-Plane based on their centers distance, shall we? 

## What Are We Doing?
We have boxes in a 2D-Plane. It looks a little bit like this:

```
 y
 ^
 |   __________
 |  |  Box 3   |
 |  |__________|
 |   __________
 |  |  Box 2   |
 |  |__________|
 |   __________
 |  |  Box 1   |
 |  |__________|
 |-----------------------------> x
Origin (0,0)
```
We want to sort them by their distance to the bottom left corner (0,0).

## Define the Type
A BoundingBox has a name for better identification after sorting, a center and the coordinates of all four corners.

```typescript
type BoundingBox = {
    name: string;
    center: {x: number; y: number};
    xmin: number;
    ymin: number;
    xmax: number;
    ymax: number;
}

// While we are at it: Define all the BoundingBoxes we need
let boundingBox0: BoundingBox = {
    name: "zero zero",
    center: {x: 0, y: 0},
    xmin: 0,
    ymin: 0,
    xmax: 0,
    ymax: 0
}

let boundingBox1: BoundingBox = {
    name: "first",
    center: {x: 0, y: 0},
    xmin: 0,
    ymin: 0,
    xmax: 6,
    ymax: 2
}

let boundingBox2: BoundingBox = {
    name: "second",
    center: {x: 0, y: 0},
    xmin: 0,
    ymin: 3,
    xmax: 6,
    ymax: 5
}

let boundingBox3: BoundingBox = {
    name: "third",
    center: {x: 0, y: 0},
    xmin: 0,
    ymin: 6,
    xmax: 6,
    ymax: 8
}
```

## Calculate the Center of a BoundingBox
Now it is time to calculate the center of a BoundingBox.
The formula for _x_ is `((xmax - xmin) / 2) + xmin`.
Repeat for _y_.

```typescript
function calculateCenter(bB: BoundingBox) {
    let c = {x: 0, y: 0};

    let xc = ((bB.xmax - bB.xmin) / 2) + bB.xmin;
    let yc = ((bB.ymax - bB.ymin) / 2) + bB.ymin;

    c.x = xc;
    c.y = yc;

    return c;
}

boundingBox1.center = calculateCenter(boundingBox1)
boundingBox2.center = calculateCenter(boundingBox2)
boundingBox3.center = calculateCenter(boundingBox3)

console.log(boundingBox1.center);
console.log(boundingBox2.center);
console.log(boundingBox3.center);
```

## Calculate the Distance Between Two Points
Now we finally need some math knowledge. The distance between two points is defined by the square root of both the distances of _x_ times two plus the distances of _y_ times two.

```typescript
function calculateDistance(bB1: BoundingBox, bB2: BoundingBox) {
    return Math.sqrt(Math.pow(bB1.center.x - bB2.center.x, 2) + Math.pow(bB1.center.y - bB2.center.y, 2))
}

console.log(calculateDistance(boundingBox1, boundingBox2));
console.log(calculateDistance(boundingBox1, boundingBox3));
console.log(calculateDistance(boundingBox2, boundingBox3));
```

## You Said We Are Sorting!
We will use `Array.prototype.sort()` which needs a _comparator_-function.

This is not the most elegant one I could come up with, but it is straight forward and understandable!

We are sorting ascending based on the distance to our origin `boundingBox0`. So when we sort a random array of our three _BoundingBoxes_ they should come out in the order **first, second, third**.

```typescript
function comparator(b1: BoundingBox, b2: BoundingBox): number {
    let d1 = calculateDistance(boundingBox0, b1);
    let d2 = calculateDistance(boundingBox0, b2);

    if (d1 > d2) return 1;
    if (d1 < d2) return -1;
    return 0;
}

let sortMe = [boundingBox1, boundingBox2, boundingBox3]
let sortMe2 = [boundingBox2, boundingBox3, boundingBox1]
sortMe.sort(comparator);
sortMe2.sort(comparator);

console.log(sortMe)
console.log(sortMe2)
```

## Did You Have Fun?
If not: Why read all of it ;).

Either way, I had a lot of fun coding this together and if you want to play around with the code. I got you covered: [Playground Link](https://www.typescriptlang.org/play?#code/C4TwDgpgBAQg9gVwHYBMCWSDm8AeUC8UA3gFBTlRICGAthAFxQDOwAThpgNxkUDGESYBFaMiORkgQ0ARsM5QQEqbNYBfbhSg4aGJTLk9yIHUj0qNFbVXGVlBzcetmDqkiQBmyXsDRwkUXioAG14EIKohAGEBIVYACmkYRnhkdCxcAEpiQyggiGAAgmIbAAYAGgVGEvU3TTyCnF4iuISYADorPABaKESOkyyAeigAJiyAal727QwLcnqFJsIWvsduqbbjDCHRiY2tpG4c3g6ixrmAzaKQXiPNVnyEVn9bklcSBelEVA5cEuTvmlsHA8IRSJpqHRGAAiABewjgUHhrDg0LKxxiwlEpQqiig1XRmhmpnxhIoByqZPInUpOTWVTebk+gN+IIAjADUqzQdkIbQGFBoe40KwWGiMYIscVKZV8aoqVoTLSHErSTkaVAAGwK+mjRkffK9FnpEEjTk-E088EUSEC6FMCC8PwocWafiSkTS0mygnq1XlOmqgDMCo12sDTigAFZ9cyuZag+agbgitbyLaYcAABYil0K92xbEyvG+on+nWq8NlyNV8k0SMADn1X3jwJwbLaBeERUCITCEQg0Q9CWNbbZGRILYtbZGncxrB7wVC4Si85HrdwY0no9wQbnHsXfZXg7XU+TIKDE5ITqQTDgeTaQTgmDi0K674-n6-3660InN7vB8nxfM9uQ7LtWAybgAPvCBH2fddp03fdYig68-EAuDgMQ88cD3CC0JgoCELfH8yO-P83E8JBvF8F4l37IQABE0BYKgaIgVoOVgHcQQqRIzR4jcQSyNMoAeYAnn8ABZCIszaJgAEdWGAOJZOzNowDgAB3LiUOEU4egE-TWA6CoxigSZ1PkrTdMScD5yuIyYFnCDNnMjIJ3eIisJI8j-I-SifPgl9e2XAcWLYjicLA-jeJwMZCIw2CQriMLGIgSLgHY-gYstNk4uEvDPOg5LiNChjjyynLONAy0RkKpCLxK9DbxS7DSIC8jKI8LwfD8AI4BoMAqFYCI4HiaRuJSJqcH4wSZtwjJnAXMSFhQNlD3C5jWOy6K6rbcpenHC51pGLaMuq-b4qO6QxjuCg0HcKA4g2qAAD4oBQCyJKkqA2QuJ6XregAeL6fseZ4oC6AGcl+qGSm4d4FjvFTpOgQgAG0DtwAqjSKhr8dmoMAF0DQKVHgHR86sZx01GtwkMidwtkycp9GFIm1SnWG0bxsg7h2YgWdKbSoaRrG4AJrQ1rMNSzqup-IKyt8l8hf-FXUqFsYgA)

UPDATE: I changed the ASCII coordinate system to be more understandable.