Created
February 11, 2019 18:53
-
-
Save johnrjj/3c4a7ddbb946a353e418a8f11893b5a3 to your computer and use it in GitHub Desktop.
marzullo algo
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // https://en.wikipedia.org/wiki/Marzullo%27s_algorithm | |
| const calculateIntersectingRanges = (ranges: Array<[number, number, any?]>, userOptions = {}) => { | |
| let START = 1; | |
| let END = -1; | |
| let points: Array<{ | |
| value: number; | |
| rangeIndex: number; | |
| type: number; | |
| count?: number; | |
| index?: number; | |
| }> = []; | |
| const options = Object.assign({ omitEmpty: true, withData: false }, userOptions); | |
| // Break range intervals into start/end values | |
| ranges.forEach((range, index) => { | |
| points.push({ value: range[0], rangeIndex: index, type: START }); | |
| points.push({ value: range[1], rangeIndex: index, type: END }); | |
| }); | |
| // Sort on value, then on type | |
| // Invert type sorting if comparing two points in the same range | |
| points.sort((a, b) => { | |
| var valueDiff = a.value - b.value; | |
| if (valueDiff !== 0) { | |
| return valueDiff; | |
| } else { | |
| return a.type - b.type * (a.rangeIndex === b.rangeIndex ? -1 : 1); | |
| } | |
| }); | |
| // For each point add the count of intersecting ranges | |
| let count = 0; | |
| points = points.map((p, index) => { | |
| count += p.type; | |
| return Object.assign({}, p, { count: count, index: index }); | |
| }); | |
| // Get the max number of simultaneous intersecting ranges | |
| let maxCount = points.reduce((max, p) => { | |
| return Math.max(max, p.count!); | |
| }, 0); | |
| if (options.omitEmpty && ranges.length > 1 && maxCount === 1) { | |
| return []; | |
| } | |
| // Remove all starting points that are not at the max intersection count, | |
| // then create interval with starting value and its next neigbor as end value | |
| const result = points | |
| .filter(p => { | |
| return p.count === maxCount; | |
| }) | |
| .map(p => { | |
| return [p.value, points[p.index! + 1].value]; | |
| }); | |
| if (!options.withData) { | |
| return result; | |
| } | |
| // Populate intersections with data from the input ranges | |
| return result.map(([start, end]) => { | |
| const data: any = ranges | |
| .filter(([r1, r2]) => Math.max(start, r1) < Math.min(end, r2)) | |
| .reduce((obj, point) => Object.assign({}, obj, point[2]), {}); | |
| const range = [start, end]; | |
| if (Object.keys(data).length > 0) { | |
| range.push(data); | |
| } | |
| return range; | |
| }); | |
| }; | |
| // Duck type for DOMRect & Custom types | |
| interface MinimalRect { | |
| left: number; | |
| right: number; | |
| top: number; | |
| bottom: number; | |
| } | |
| interface MinimalXAxis { | |
| left: number; | |
| right: number; | |
| } | |
| const intersectRect = (rectA: MinimalRect, cursor: MinimalRect) => { | |
| return ( | |
| cursor.left >= rectA.left && | |
| cursor.right <= rectA.right && | |
| (cursor.top >= rectA.top && cursor.bottom <= rectA.bottom) | |
| ); | |
| }; | |
| const intersectInterval = (existingAxis: MinimalXAxis, newAxis: MinimalXAxis) => | |
| existingAxis.left < newAxis.right && newAxis.left < existingAxis.right; | |
| export { calculateIntersectingRanges, intersectRect, intersectInterval }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment