This repository has been archived by the owner on May 7, 2021. It is now read-only.
forked from tensorflow/tfjs-models
/
minAreaRect.ts
96 lines (90 loc) · 3.55 KB
/
minAreaRect.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
* @license
* Copyright 2019 Google LLC. All Rights Reserved.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
* =============================================================================
*/
import {convexHull} from './convexHull';
import {Point, Vector} from './geometry';
import {Box} from './types';
function dot(first: number[], second: number[]) {
const add = (firstAddend: number, secondAddend: number) => {
return firstAddend + secondAddend;
};
const mul = (_: number, idx: number) => {
return first[idx] * second[idx];
};
if (first.length !== second.length) {
throw Error('The arrays must have the same length');
}
return first.map(mul).reduce(add, 0);
}
type RotationMatrix = [[number, number], [number, number]];
const computeBackwardsRotationMatrix = (angle: number): RotationMatrix => [
[Math.cos(angle), Math.cos(angle - Math.PI / 2)],
[Math.cos(angle + Math.PI / 2), Math.cos(angle)]];
const inverseRotation = (rotation: RotationMatrix): RotationMatrix => {
return [[rotation[0][0], rotation[1][0]], [rotation[0][1], rotation[1][1]]];
};
const rotate = (rotation: RotationMatrix, vector: Vector): Vector => {
return rotation.map(row => {
return dot(row, vector);
}) as Vector;
};
export function minAreaRect(points: Point[]): Box {
const convexHullPoints = convexHull(points);
const edgeAngles = new Set<number>();
for (let idx = 0; idx < convexHullPoints.length - 1; ++idx) {
const edgeX = convexHullPoints[idx + 1].x - convexHullPoints[idx].x;
const edgeY = convexHullPoints[idx + 1].y - convexHullPoints[idx].y;
edgeAngles.add(Math.abs(Math.atan2(edgeY, edgeX) % (Math.PI / 2)));
}
// rotation angle, area, min x, max x, min y, max y
let minBoundingBox = Array.from(new Array<number>(6), () => 0);
// area
minBoundingBox[1] = Number.MAX_VALUE;
for (const angle of Array.from(edgeAngles)) {
const backwardsRotation = computeBackwardsRotationMatrix(angle);
const rotatedConvexHull = convexHullPoints.map(point => {
const rotatedVector = rotate(backwardsRotation, [point.x, point.y]);
return new Point(rotatedVector[0], rotatedVector[1]);
});
let minX = Number.MAX_VALUE;
let maxX = Number.MIN_VALUE;
let minY = Number.MAX_VALUE;
let maxY = Number.MIN_VALUE;
for (const point of rotatedConvexHull) {
const {x, y} = point;
minX = Math.min(minX, x);
maxX = Math.max(maxX, x);
minY = Math.min(minY, y);
maxY = Math.max(maxY, y);
}
const width = maxX - minX;
const height = maxY - minY;
const area = width * height;
if (area < minBoundingBox[1]) {
minBoundingBox = [angle, area, minX, maxX, minY, maxY];
}
}
const [angle, , minX, maxX, minY, maxY] = minBoundingBox;
const backwardsRotation = computeBackwardsRotationMatrix(angle);
const rotation = inverseRotation(backwardsRotation);
const box: Box = [
new Point(...rotate(rotation, [maxX, maxY])),
new Point(...rotate(rotation, [minX, maxY])),
new Point(...rotate(rotation, [minX, minY])),
new Point(...rotate(rotation, [maxX, minY])),
];
return box;
}