skyline algorithm

How do I find the vertices of the broken line that surrounds the silhouette in this image?

A possible input for the example above is:

WIDTH  HEIGHT  POSITION
  3       9       17
  5       9        9
 12       4        8
  3 开发者_JS百科     11        3
 10       7        1
  2       3       19

So for this example the solution would be

[(1, 0), (1, 7), (3, 7), (3, 11), (6, 11), (6, 7), 
 (9, 7), (9, 9), (14, 9), (14, 4), (17, 4), (17, 9), 
 (20, 9), (20, 3), (21, 3), (21, 0)]

This is pretty simple. Make an array that is the length of the X axis, initialize to 0. As you read in the inputs, write the heights into this array if the height is >= the current value at that location in the array.

Then just loop over the array, and every time the value changes it is a vertex.

Basically:

int heights[SIZE] = {0};
int i, width, pos, height, prev = -1;
while (scanf("%d %d %d", &width, &height, &pos) == 3) {
    for (i = 0; i < width; ++i) {
        if (heights[pos+i] < height)
            heights[pos+i] = height;
    }
}

for (i = 0; i < SIZE; ++i) {
    if (heights[i] != prev) {
        printf("(%d,%d) ", i+1, heights[i]);
        prev = heights[i];
    }
}
printf("\n");

In the naive case, this doesn't seem like a very difficult algorithm. Do you know if the input size will get large/how large?

My initial attempt: Try to move from left to right. First pick the block with the leftmost edge that exists on the origin line. Climb to its top. Find all blocks with a left edge between the current point and the upper right point of the current block. Of that set, pick the closest (but check for edge cases, pun not intended). If the set is empty, start working your way down the right side of the block, looking for other blocks you may intercept.

Basically this is just how you'd trace it with your eye.

You can do some simple optimization by keeping sorted lists and then searching the lists rather than finding sets and digging around. For example, you might keep 4 sorted lists of the blocks, each sorted by the x or y coordinate of one of the sides.

If you have many, many blocks, you could consider using a multi-dimensional data structure to further organize the information.

I solved this problem using the sweep-line algorithm. This is a python class solution.

there two keys: 1) using the variable "points" to save all the left and right points and their heights and the sign of the height to indicate whether the points are left or right. 2) the variable "active" is used to save all the active lines that has been scanned.

class Solution: # @param {integer[][]} buildings # @return {integer[][]} def getSkyline(self, buildings): if len(buildings)==0: return [] if len(buildings)==1: return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]

    points=[]
    for building in buildings:
        points+=[[building[0],building[2]]]
        points+=[[building[1],-building[2]]] # the negative sign means this point is a right point
    points=sorted(points, key=lambda x: x[0])

    moving, active, res, current=0, [0], [],-1

    while moving<len(points):
        i=moving
        while i<=len(points):
            if i<len(points) and points[i][0]==points[moving][0]:
                if points[i][1]>0:
                    active+=[points[i][1]]
                    if points[i][1]>current:
                        current=points[i][1]
                        if len(res)>0 and res[-1][0]==points[i][0]: 
                            res[-1][1]=current
                        else:
                            res+=[[points[moving][0], current]]
                else:
                    active.remove(-points[i][1]) #remove height of the lines than have been finished with scanning
                i+=1
            else:
                break
        if max(active)<current:
            current=max(active)
            res+=[[points[moving][0], current]] 
        moving=i
    return res 

I made a Java class to try and solve this. The class includes methods for generating, solving and printing data-sets. I haven't tested extensively, there may be a few bugs remaining. Also, my solution may be needlessly complicated, but it's designed to work (in theory) for non-discrete height and coordinate values.

import java.util.Random;

public class Skyline {

    private int[][] buildings;
    private int[][] skyline;

    private int maxLength;
    private int maxHeight;

    public Skyline(int buildings, int maxLength, int maxHeight) {
        this.maxLength = maxLength;
        this.maxHeight = maxHeight;
        makeRandom(buildings);
    }

    public Skyline(int[][] buildings, int dimensions) {
        this.maxLength = maxLength;
        this.maxHeight = maxHeight;
        this.buildings = buildings;
    }

    public void makeRandom(int buildings) {
        this.buildings = new int[buildings][3];

        Random rand = new Random();

        for(int i = 0; i < buildings; i++) {
            int start = rand.nextInt(maxLength-3);
            int end = rand.nextInt(maxLength - start - 1) + start + 1;
            int height = rand.nextInt(maxHeight-1) + 1;

            this.buildings[i][0] = start;
            this.buildings[i][1] = height;
            this.buildings[i][2] = end; 
        }

        boolean swapped = true;
        while(swapped) {
            swapped = false;
            for(int i = 0; i < this.buildings.length-1; i++) {
                if(this.buildings[i][0] > this.buildings[i+1][0]) {
                    swapped = true;
                    int[] temp = this.buildings[i];
                    this.buildings[i] = this.buildings[i+1];
                    this.buildings[i+1] = temp;
                }
            }
        }

//        this.buildings[0][0] = 2;
//        this.buildings[0][1] = 3;
//        this.buildings[0][2] = 8;
    }

    public void printBuildings() {
        print(this.buildings, false);
    }
    public void printSkyline() {
        print(this.buildings, true);
    }

    public void print(int[][] buildings, boolean outline) {
        char[][] str = new char[this.maxLength][this.maxHeight];
        for(int i = 0; i < this.maxLength; i++) {
            for(int j = 0; j < this.maxHeight; j++) {
                str[i][j] = '.';
            }
        }

        for(int i = 0; i < buildings.length; i++) {
            int start = buildings[i][0];
            int height = buildings[i][1];
            int end = buildings[i][2];

            //print the starting vertical
            for(int j = 0; j < height; j++) {
                if(outline) str[start][j] =  str[start][j] == '|' ? '.' : '|';
                else str[start][j] = '|';
            }

            //print the ending vertical
            for(int j = 0; j < height; j++) {
                if(outline) str[end][j] = str[end][j] == '|' ? '.' : '|';
                else str[end][j] =  '|';
            }

            //print the horizontal
            if(height > 0) {
                for(int j = start; j <= end; j++) {
                    str[j][height] = str[j][height] == '|' ? '|' : '-';
                }
            }

        }

        for(int i = maxHeight-1; i >= 0; i--) {
            for(int j = 0; j < maxLength; j++) {
                System.out.print(str[j][i]);
            }
            System.out.println();
        }

        System.out.println();
    }

    public void solveSkyline() {

        for(int i = 0; i < buildings.length; i++) {
            boolean reduced = true;
            while(reduced) {
                reduced = false;
                for(int j = i+1; j < buildings.length; j++) {
                    if(buildings[j][0] < buildings[i][2] && buildings[j][1] > buildings[i][1] && buildings[j][2] >= buildings[i][2]) { //if intersecting building is taller, and longer
                        buildings[i][2] = buildings[j][0];  
                        reduced = true;
                        break;
                    } else if(buildings[j][0] < buildings[i][2] && buildings[j][1] <= buildings[i][1] && buildings[j][2] >= buildings[i][2]) { //intersecting building is shorter, but longer
                        buildings[j][0] = buildings[i][2]; 
                        reduced = true;
                        break;
                    } else if(buildings[j][0] < buildings[i][2] && buildings[j][1] > 0 && buildings[j][1] < buildings[i][1] && buildings[j][2] <= buildings[i][2]) {  //building is invisible, so ignore it
                        buildings[j][1] = 0;
                        reduced = true;
                        break;
                    } else if(buildings[j][0] < buildings[i][2] && buildings[j][2] <= buildings[i][2] && buildings[j][1] > buildings[i][1]) {
                        int[] newBuilding = new int[]{buildings[j][2], buildings[i][1], buildings[i][2]};
                        int[][] newBuildings = new int[buildings.length+1][3];
                        boolean inserted = false;
                        buildings[i][2] = buildings[j][0];       
                        for(int k = 0; k < buildings.length; k++) {
                            if(inserted == false) {
                                if(newBuilding[0] < buildings[k][0]) {
                                    newBuildings[k] = newBuilding;
                                    newBuildings[k+1] = buildings[k];
                                    inserted = true;
                                } else {
                                    newBuildings[k] = buildings[k];
                                }
                            } 
                            if(inserted == false && k == buildings.length - 1) {
                                newBuildings[k+1] = newBuilding;
                            } else {
                                newBuildings[k+1] = buildings[k];
                            }
                        }
                        buildings = newBuildings;
                        reduced = true;
                        break;
                    }
                }
            }
        }
    }

    public static void main(String args[]) {
        Skyline s = new Skyline(5, 100, 10);

        s.printBuildings();
        s.solveSkyline();
        s.printBuildings();

        s.printSkyline();
    } 
}

My solution to the problem as described here https://leetcode.com/problems/the-skyline-problem/ it iterates the list of buildings twice, however this could be combined into a single iteration. However, there are more optimal approaches if you consider the pure algorithm solution explained here http://www.algorithmist.com/index.php/UVa_105

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        // The final result.
        vector<pair<int, int>> result;

        // To hold information about the buildings
        std::set<BuildingInformation> buildingInformation;

        // Go through each building, and store information about the start and end heights.
        for ( vector<vector<int>>::iterator buildingIt = buildings.begin( ); buildingIt != buildings.end( ); ++buildingIt ) {
            BuildingInformation buildingStart;
            buildingStart.x = (*buildingIt)[0];
            buildingStart.h = (*buildingIt)[2];
            buildingStart.StartOrEnd = Start;
            buildingInformation.insert(buildingStart);
            buildingStart.x = (*buildingIt)[1];
            buildingStart.StartOrEnd = End;
            buildingInformation.insert(buildingStart);
        }

        // Keep track of the current height.
        int currentHeight = 0;

        // A map of active building heights against number of buildings (to handle multiple buildings overlapping with same height).
        // As it is a map, it'll be sorted by key, which is the height.
        std::map<int, int> heights;

        // Go through each building information that we generated earlier.
        for ( std::set<BuildingInformation>::iterator it = buildingInformation.begin( ); it != buildingInformation.end( ); ++it ) {
            if ( it->StartOrEnd == Start ) {
                // This is a start point, do we have this height already in our map?
                if ( heights.find( it->h ) != heights.end( ) ) {
                    // Yes, increment count of active buildings with this height/
                    heights[ it->h ] += 1;    
                } else {
                    // Nope, add this building to our map.
                    heights[ it->h ] = 1;  
                }

                // Check if building height is taller than current height.
                if ( it->h > currentHeight ) {
                    // Update current height and add marker to results.
                    currentHeight = it->h;
                    result.push_back( pair<int, int>( it->x, currentHeight ) );
                }
            } else {
                // This is an end point, get iterator into our heights map.
                std::map<int, int>::iterator heightIt = heights.find( it->h );

                // Reduce by one.
                heightIt->second -= 1;

                // If this was the last building of the current height in the map...
                if ( heightIt->second == 0 ) {
                    // Remove from heights map.
                    heights.erase( heightIt );

                    // If our height was the current height...
                    if ( it->h == currentHeight ) {
                        // If we have no more active buildings...
                        if ( heights.size( ) == 0 ) {
                            // Current height is zero.
                            currentHeight = 0;
                        } else {
                            // Otherwise, get iterator to one past last.
                            heightIt = heights.end( );

                            // Go back to get last valid iterator.
                            --heightIt;

                            // Store current height.
                            currentHeight = heightIt->first;
                        }

                        // Add marker to results.
                        result.push_back( pair<int, int>( it->x, currentHeight ) );
                    }
                }
            }
        }

        return result;
    }
private:
    // Is this a building start or end?
    enum BuildingStartOrEnd
    {
        Start = 0,
        End
    };

    // Information about building, there are two of these for each building, one for start, one for end.
    struct BuildingInformation
    {
        int x;
        int h;
        BuildingStartOrEnd StartOrEnd;

        // The ordering algorithm for the key, the rules we want to implement is keys are put in X order, and
        // in the case of a tie (x values the same), we want Start pieces to come before End pieces (this is
        // to handle cases where an old building ends and a new building begins on same X index, in which case
        // we want to process the new start before processing the old end), however if we have two Start pieces
        // at the same index, we wish to favour taller pieces (in this scenario we want to add a marker for the
        // tallest building), finally if we have two End pieces at the same index, we wish to prefer lower
        // pieces, as when multiple buildings end, we only want to add one result for the ultimate lowest point.
        bool operator < ( const BuildingInformation & rhs ) const
        {
            if ( x == rhs.x )
            {
                if ( StartOrEnd == rhs.StartOrEnd ) {
                    if ( StartOrEnd == Start )
                        return h > rhs.h;
                    else
                        return h < rhs.h;
                } else {
                    return StartOrEnd < rhs.StartOrEnd;
                }
            }

            return x < rhs.x;
        }
    };
};