cesiumDemo/Source/Core/TileAvailability.js

import binarySearch from './binarySearch.js';
import Cartographic from './Cartographic.js';
import defined from './defined.js';
import defineProperties from './defineProperties.js';
import Rectangle from './Rectangle.js';

    /**
     * Reports the availability of tiles in a {@link TilingScheme}.
     *
     * @alias TileAvailability
     * @constructor
     *
     * @param {TilingScheme} tilingScheme The tiling scheme in which to report availability.
     * @param {Number} maximumLevel The maximum tile level that is potentially available.
     */
    function TileAvailability(tilingScheme, maximumLevel) {
        this._tilingScheme = tilingScheme;
        this._maximumLevel = maximumLevel;

        this._rootNodes = [];
    }

    var rectangleScratch = new Rectangle();

    function findNode(level, x, y, nodes) {
        var count = nodes.length;
        for (var i = 0; i < count; ++i) {
            var node = nodes[i];
            if (node.x === x && node.y === y && node.level === level) {
                return true;
            }
        }

        return false;
    }

    /**
     * Marks a rectangular range of tiles in a particular level as being available.  For best performance,
     * add your ranges in order of increasing level.
     *
     * @param {Number} level The level.
     * @param {Number} startX The X coordinate of the first available tiles at the level.
     * @param {Number} startY The Y coordinate of the first available tiles at the level.
     * @param {Number} endX The X coordinate of the last available tiles at the level.
     * @param {Number} endY The Y coordinate of the last available tiles at the level.
     */
    TileAvailability.prototype.addAvailableTileRange = function(level, startX, startY, endX, endY) {
        var tilingScheme = this._tilingScheme;

        var rootNodes = this._rootNodes;
        if (level === 0) {
            for (var y = startY; y <= endY; ++y) {
                for (var x = startX; x <= endX; ++x) {
                    if (!findNode(level, x, y, rootNodes)) {
                        rootNodes.push(new QuadtreeNode(tilingScheme, undefined, 0, x, y));
                    }
                }
            }
        }

        tilingScheme.tileXYToRectangle(startX, startY, level, rectangleScratch);
        var west = rectangleScratch.west;
        var north = rectangleScratch.north;

        tilingScheme.tileXYToRectangle(endX, endY, level, rectangleScratch);
        var east = rectangleScratch.east;
        var south = rectangleScratch.south;

        var rectangleWithLevel = new RectangleWithLevel(level, west, south, east, north);

        for (var i = 0; i < rootNodes.length; ++i) {
            var rootNode = rootNodes[i];
            if (rectanglesOverlap(rootNode.extent, rectangleWithLevel)) {
                putRectangleInQuadtree(this._maximumLevel, rootNode, rectangleWithLevel);
            }
        }
    };

    /**
     * Determines the level of the most detailed tile covering the position.  This function
     * usually completes in time logarithmic to the number of rectangles added with
     * {@link TileAvailability#addAvailableTileRange}.
     *
     * @param {Cartographic} position The position for which to determine the maximum available level.  The height component is ignored.
     * @return {Number} The level of the most detailed tile covering the position.
     * @throws {DeveloperError} If position is outside any tile according to the tiling scheme.
     */
    TileAvailability.prototype.computeMaximumLevelAtPosition = function(position) {
        // Find the root node that contains this position.
        var node;
        for (var nodeIndex = 0; nodeIndex < this._rootNodes.length; ++nodeIndex) {
            var rootNode = this._rootNodes[nodeIndex];
            if (rectangleContainsPosition(rootNode.extent, position)) {
                node = rootNode;
                break;
            }
        }

        if (!defined(node)) {
            return -1;
        }

        return findMaxLevelFromNode(undefined, node, position);
    };

    var rectanglesScratch = [];
    var remainingToCoverByLevelScratch = [];
    var westScratch = new Rectangle();
    var eastScratch = new Rectangle();

    /**
     * Finds the most detailed level that is available _everywhere_ within a given rectangle.  More detailed
     * tiles may be available in parts of the rectangle, but not the whole thing.  The return value of this
     * function may be safely passed to {@link sampleTerrain} for any position within the rectangle.  This function
     * usually completes in time logarithmic to the number of rectangles added with
     * {@link TileAvailability#addAvailableTileRange}.
     *
     * @param {Rectangle} rectangle The rectangle.
     * @return {Number} The best available level for the entire rectangle.
     */
    TileAvailability.prototype.computeBestAvailableLevelOverRectangle = function(rectangle) {
        var rectangles = rectanglesScratch;
        rectangles.length = 0;

        if (rectangle.east < rectangle.west) {
            // Rectangle crosses the IDL, make it two rectangles.
            rectangles.push(Rectangle.fromRadians(-Math.PI, rectangle.south, rectangle.east, rectangle.north, westScratch));
            rectangles.push(Rectangle.fromRadians(rectangle.west, rectangle.south, Math.PI, rectangle.north, eastScratch));
        } else {
            rectangles.push(rectangle);
        }

        var remainingToCoverByLevel = remainingToCoverByLevelScratch;
        remainingToCoverByLevel.length = 0;

        var i;
        for (i = 0; i < this._rootNodes.length; ++i) {
            updateCoverageWithNode(remainingToCoverByLevel, this._rootNodes[i], rectangles);
        }

        for (i = remainingToCoverByLevel.length - 1; i >= 0; --i) {
            if (defined(remainingToCoverByLevel[i]) && remainingToCoverByLevel[i].length === 0) {
                return i;
            }
        }

        return 0;
    };

    var cartographicScratch = new Cartographic();

    /**
     * Determines if a particular tile is available.
     * @param {Number} level The tile level to check.
     * @param {Number} x The X coordinate of the tile to check.
     * @param {Number} y The Y coordinate of the tile to check.
     * @return {Boolean} True if the tile is available; otherwise, false.
     */
    TileAvailability.prototype.isTileAvailable = function(level, x, y) {
        // Get the center of the tile and find the maximum level at that position.
        // Because availability is by tile, if the level is available at that point, it
        // is sure to be available for the whole tile.  We assume that if a tile at level n exists,
        // then all its parent tiles back to level 0 exist too.  This isn't really enforced
        // anywhere, but Cesium would never load a tile for which this is not true.
        var rectangle = this._tilingScheme.tileXYToRectangle(x, y, level, rectangleScratch);
        Rectangle.center(rectangle, cartographicScratch);
        return this.computeMaximumLevelAtPosition(cartographicScratch) >= level;
    };

    /**
     * Computes a bit mask indicating which of a tile's four children exist.
     * If a child's bit is set, a tile is available for that child.  If it is cleared,
     * the tile is not available.  The bit values are as follows:
     * <table>
     *     <tr><th>Bit Position</th><th>Bit Value</th><th>Child Tile</th></tr>
     *     <tr><td>0</td><td>1</td><td>Southwest</td></tr>
     *     <tr><td>1</td><td>2</td><td>Southeast</td></tr>
     *     <tr><td>2</td><td>4</td><td>Northwest</td></tr>
     *     <tr><td>3</td><td>8</td><td>Northeast</td></tr>
     * </table>
     *
     * @param {Number} level The level of the parent tile.
     * @param {Number} x The X coordinate of the parent tile.
     * @param {Number} y The Y coordinate of the parent tile.
     * @return {Number} The bit mask indicating child availability.
     */
    TileAvailability.prototype.computeChildMaskForTile = function(level, x, y) {
        var childLevel = level + 1;
        if (childLevel >= this._maximumLevel) {
            return 0;
        }

        var mask = 0;

        mask |= this.isTileAvailable(childLevel, 2 * x, 2 * y + 1) ? 1 : 0;
        mask |= this.isTileAvailable(childLevel, 2 * x + 1, 2 * y + 1) ? 2 : 0;
        mask |= this.isTileAvailable(childLevel, 2 * x, 2 * y) ? 4 : 0;
        mask |= this.isTileAvailable(childLevel, 2 * x + 1, 2 * y) ? 8 : 0;

        return mask;
    };

    function QuadtreeNode(tilingScheme, parent, level, x, y) {
        this.tilingScheme = tilingScheme;
        this.parent = parent;
        this.level = level;
        this.x = x;
        this.y = y;
        this.extent = tilingScheme.tileXYToRectangle(x, y, level);

        this.rectangles = [];
        this._sw = undefined;
        this._se = undefined;
        this._nw = undefined;
        this._ne = undefined;
    }

    defineProperties(QuadtreeNode.prototype, {
        nw: {
            get: function() {
                if (!this._nw) {
                    this._nw = new QuadtreeNode(this.tilingScheme, this, this.level + 1, this.x * 2, this.y * 2);
                }
                return this._nw;
            }
        },

        ne: {
            get: function() {
                if (!this._ne) {
                    this._ne = new QuadtreeNode(this.tilingScheme, this, this.level + 1, this.x * 2 + 1, this.y * 2);
                }
                return this._ne;
            }
        },

        sw: {
            get: function() {
                if (!this._sw) {
                    this._sw = new QuadtreeNode(this.tilingScheme, this, this.level + 1, this.x * 2, this.y * 2 + 1);
                }
                return this._sw;
            }
        },

        se: {
            get: function() {
                if (!this._se) {
                    this._se = new QuadtreeNode(this.tilingScheme, this, this.level + 1, this.x * 2 + 1, this.y * 2 + 1);
                }
                return this._se;
            }
        }
    });

    function RectangleWithLevel(level, west, south, east, north) {
        this.level = level;
        this.west = west;
        this.south = south;
        this.east = east;
        this.north = north;
    }

    function rectanglesOverlap(rectangle1, rectangle2) {
        var west = Math.max(rectangle1.west, rectangle2.west);
        var south = Math.max(rectangle1.south, rectangle2.south);
        var east = Math.min(rectangle1.east, rectangle2.east);
        var north = Math.min(rectangle1.north, rectangle2.north);
        return south < north && west < east;
    }

    function putRectangleInQuadtree(maxDepth, node, rectangle) {
        while (node.level < maxDepth) {
            if (rectangleFullyContainsRectangle(node.nw.extent, rectangle)) {
                node = node.nw;
            } else if (rectangleFullyContainsRectangle(node.ne.extent, rectangle)) {
                node = node.ne;
            } else if (rectangleFullyContainsRectangle(node.sw.extent, rectangle)) {
                node = node.sw;
            } else if (rectangleFullyContainsRectangle(node.se.extent, rectangle)) {
                node = node.se;
            } else {
                break;
            }
        }

        if (node.rectangles.length === 0 || node.rectangles[node.rectangles.length - 1].level <= rectangle.level) {
            node.rectangles.push(rectangle);
        } else {
            // Maintain ordering by level when inserting.
            var index = binarySearch(node.rectangles, rectangle.level, rectangleLevelComparator);
            if (index <= 0) {
                index = ~index;
            }
            node.rectangles.splice(index, 0, rectangle);
        }
    }

    function rectangleLevelComparator(a, b) {
        return a.level - b;
    }

    function rectangleFullyContainsRectangle(potentialContainer, rectangleToTest) {
        return rectangleToTest.west >= potentialContainer.west &&
               rectangleToTest.east <= potentialContainer.east &&
               rectangleToTest.south >= potentialContainer.south &&
               rectangleToTest.north <= potentialContainer.north;
    }

    function rectangleContainsPosition(potentialContainer, positionToTest) {
        return positionToTest.longitude >= potentialContainer.west &&
               positionToTest.longitude <= potentialContainer.east &&
               positionToTest.latitude >= potentialContainer.south &&
               positionToTest.latitude <= potentialContainer.north;
    }

    function findMaxLevelFromNode(stopNode, node, position) {
        var maxLevel = 0;

        // Find the deepest quadtree node containing this point.
        var found = false;
        while (!found) {
            var nw = node._nw && rectangleContainsPosition(node._nw.extent, position);
            var ne = node._ne && rectangleContainsPosition(node._ne.extent, position);
            var sw = node._sw && rectangleContainsPosition(node._sw.extent, position);
            var se = node._se && rectangleContainsPosition(node._se.extent, position);

            // The common scenario is that the point is in only one quadrant and we can simply
            // iterate down the tree.  But if the point is on a boundary between tiles, it is
            // in multiple tiles and we need to check all of them, so use recursion.
            if (nw + ne + sw + se > 1) {
                if (nw) {
                    maxLevel = Math.max(maxLevel, findMaxLevelFromNode(node, node._nw, position));
                }
                if (ne) {
                    maxLevel = Math.max(maxLevel, findMaxLevelFromNode(node, node._ne, position));
                }
                if (sw) {
                    maxLevel = Math.max(maxLevel, findMaxLevelFromNode(node, node._sw, position));
                }
                if (se) {
                    maxLevel = Math.max(maxLevel, findMaxLevelFromNode(node, node._se, position));
                }
                break;
            } else if (nw) {
                node = node._nw;
            } else if (ne) {
                node = node._ne;
            } else if (sw) {
                node = node._sw;
            } else if (se) {
                node = node._se;
            } else {
                found = true;
            }
        }

        // Work up the tree until we find a rectangle that contains this point.
        while (node !== stopNode) {
            var rectangles = node.rectangles;

            // Rectangles are sorted by level, lowest first.
            for (var i = rectangles.length - 1; i >= 0 && rectangles[i].level > maxLevel; --i) {
                var rectangle = rectangles[i];
                if (rectangleContainsPosition(rectangle, position)) {
                    maxLevel = rectangle.level;
                }
            }

            node = node.parent;
        }

        return maxLevel;
    }

    function updateCoverageWithNode(remainingToCoverByLevel, node, rectanglesToCover) {
        if (!node) {
            return;
        }

        var i;
        var anyOverlap = false;
        for (i = 0; i < rectanglesToCover.length; ++i) {
            anyOverlap = anyOverlap || rectanglesOverlap(node.extent, rectanglesToCover[i]);
        }

        if (!anyOverlap) {
            // This node is not applicable to the rectangle(s).
            return;
        }

        var rectangles = node.rectangles;
        for (i = 0; i < rectangles.length; ++i) {
            var rectangle = rectangles[i];

            if (!remainingToCoverByLevel[rectangle.level]) {
                remainingToCoverByLevel[rectangle.level] = rectanglesToCover;
            }

            remainingToCoverByLevel[rectangle.level] = subtractRectangle(remainingToCoverByLevel[rectangle.level], rectangle);
        }

        // Update with child nodes.
        updateCoverageWithNode(remainingToCoverByLevel, node._nw, rectanglesToCover);
        updateCoverageWithNode(remainingToCoverByLevel, node._ne, rectanglesToCover);
        updateCoverageWithNode(remainingToCoverByLevel, node._sw, rectanglesToCover);
        updateCoverageWithNode(remainingToCoverByLevel, node._se, rectanglesToCover);
    }

    function subtractRectangle(rectangleList, rectangleToSubtract) {
        var result = [];
        for (var i = 0; i < rectangleList.length; ++i) {
            var rectangle = rectangleList[i];
            if (!rectanglesOverlap(rectangle, rectangleToSubtract)) {
                // Disjoint rectangles.  Original rectangle is unmodified.
                result.push(rectangle);
            } else {
                // rectangleToSubtract partially or completely overlaps rectangle.
                if (rectangle.west < rectangleToSubtract.west) {
                    result.push(new Rectangle(rectangle.west, rectangle.south, rectangleToSubtract.west, rectangle.north));
                }
                if (rectangle.east > rectangleToSubtract.east) {
                    result.push(new Rectangle(rectangleToSubtract.east, rectangle.south, rectangle.east, rectangle.north));
                }
                if (rectangle.south < rectangleToSubtract.south) {
                    result.push(new Rectangle(Math.max(rectangleToSubtract.west, rectangle.west), rectangle.south, Math.min(rectangleToSubtract.east, rectangle.east), rectangleToSubtract.south));
                }
                if (rectangle.north > rectangleToSubtract.north) {
                    result.push(new Rectangle(Math.max(rectangleToSubtract.west, rectangle.west), rectangleToSubtract.north, Math.min(rectangleToSubtract.east, rectangle.east), rectangle.north));
                }
            }
        }

        return result;
    }
export default TileAvailability;