/
classify_rings.js
52 lines (38 loc) · 1.38 KB
/
classify_rings.js
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
// @flow
import quickselect from 'quickselect';
import {calculateSignedArea} from './util';
import type Point from '@mapbox/point-geometry';
// classifies an array of rings into polygons with outer rings and holes
export default function classifyRings(rings: Array<Array<Point>>, maxRings: number) {
const len = rings.length;
if (len <= 1) return [rings];
const polygons = [];
let polygon,
ccw;
for (let i = 0; i < len; i++) {
const area = calculateSignedArea(rings[i]);
if (area === 0) continue;
(rings[i]: any).area = Math.abs(area);
if (ccw === undefined) ccw = area < 0;
if (ccw === area < 0) {
if (polygon) polygons.push(polygon);
polygon = [rings[i]];
} else {
(polygon: any).push(rings[i]);
}
}
if (polygon) polygons.push(polygon);
// Earcut performance degrades with the # of rings in a polygon. For this
// reason, we limit strip out all but the `maxRings` largest rings.
if (maxRings > 1) {
for (let j = 0; j < polygons.length; j++) {
if (polygons[j].length <= maxRings) continue;
quickselect(polygons[j], maxRings, 1, polygons[j].length - 1, compareAreas);
polygons[j] = polygons[j].slice(0, maxRings);
}
}
return polygons;
}
function compareAreas(a, b) {
return b.area - a.area;
}