Subversion Repositories splitter

Rev

Rev 643 | Blame | Compare with Previous | Last modification | View Log | RSS feed

/*
 * Copyright (c) 2014, Gerd Petermann
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 3 as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 */


package uk.me.parabola.splitter.solver;

import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import it.unimi.dsi.fastutil.ints.IntArrayList;
import uk.me.parabola.splitter.Area;
import uk.me.parabola.splitter.SplitFailedException;
import uk.me.parabola.splitter.Utils;

/**
         * This class implements a "view" on a rectangle covering a part
         * of a {@link DensityMap}.
         * It contains the sum of all nodes in this area and has methods to
         * help splitting it into smaller parts.
         *
         * We want to keep the memory footprint of this class small as
         * many instances are kept in maps.
         * @author GerdP
         *
         */

        class Tile extends Rectangle{
                /**
                 *
                 */

                private final EnhancedDensityMap densityInfo;
                private final long count;
               
                /**
                 * Create tile for whole density map.
                 * @param densityInfo
                 */

                public Tile(EnhancedDensityMap densityInfo) {
                        this(densityInfo, 0, 0, densityInfo.getDensityMap().getWidth(),
                                        densityInfo.getDensityMap().getHeight(),
                                        densityInfo.getNodeCount());
                }

                /**
                 * create a tile with unknown number of nodes
                 * @param r the rectangle
                 * @param densityInfo
                 */

                public Tile(EnhancedDensityMap densityInfo, Rectangle r) {
                        super(r);
                        if (r.x < 0 || r.y < 0 || r.x + r.width > densityInfo.getDensityMap().getWidth()
                                        || r.y + r.height > densityInfo.getDensityMap().getHeight())
                                throw new IllegalArgumentException("Rectangle doesn't fit into density map");
                       
                        this.densityInfo = densityInfo;
                        count = calcCount();
                }

                /**
                 * create a tile with a known number of nodes
                 * @param densityInfo
                 * @param x
                 * @param y
                 * @param width
                 * @param height
                 * @param count caller must ensure that this value is correct. See also verify()
                 */

                private Tile(EnhancedDensityMap densityInfo, int x,int y, int width, int height, long count) {
                        super(x,y,width,height);
                        this.densityInfo = densityInfo;
                        this.count = count;
//                      if (!verify()){
//                              System.out.println(count + " <> " + calcCount());
//                              assert false;
//                      }
                }

                public long getCount() {
                        return count;
                }

                /**
                 * @return true if the saved count value is correct.
                 */

                public boolean verify(){
                        return (getCount() == calcCount());
                }
               
                public static IntArrayList genTests(final int start, final int end) {
                        if (end - start < 0)
                                return new IntArrayList(0);
                        final int mid = (start + end) / 2;
                        final int toAdd = end - start + 1;
                        IntArrayList list = new IntArrayList(toAdd);
                        list.add(mid);
                        for (int i = 1; i < toAdd / 2; i++) {
                                list.add(mid + i);
                                list.add(mid - i);
                        }
                        if (list.size() < toAdd)
                                list.add(end);
                        if (list.size() < toAdd)
                                list.add(start);
                        return list;
                }

                /**
                 * calculate the number of nodes in this tile
                 * @return
                 */

                private long calcCount() {
                        long sum = 0;
                        for (int i = 0; i < height; i++) {
                                sum += getRowSum(i);
                        }
                        return sum;
                }
               
                /**
                 * Calculate the sum of all grid elements within a row
                 *
                 * @param row the row within the tile (0..height-1)
                 * @return
                 */

                public long getRowSum(int row) {
                        assert row >= 0 && row < height;
                        int mapRow = row + y;
                        long sum = 0;
                        int[] vector = densityInfo.getMapRow(mapRow);
                        if (vector != null) {
                                final int lastX = x + width;
                                for (int i = x; i < lastX; i++)
                                        sum += vector[i];
                        }
                        return sum;
                }

                private long getRowSum(int row, long[] rowSums) {
                        if (rowSums[row] < 0)
                                rowSums[row] = getRowSum(row);
                        return rowSums[row];
                }

                /**
                 * Calculate the sum of all grid elements within a column.
                 *
                 * @param col the column within the tile
                 * @return
                 */

                public long getColSum(int col) {
                        assert col >= 0 && col < width;
                        int mapCol = col + x;
                        long sum = 0;
                        int[] vector = densityInfo.getMapCol(mapCol);
                        if (vector != null) {
                                final int lastY = y + height;
                                for (int i = y; i < lastY; i++)
                                        sum += vector[i];
                        }
                        return sum;
                }

                private long getColSum(int col, long[] colSums) {
                        if (colSums[col] < 0)
                                colSums[col] = getColSum(col);
                        return colSums[col];
                }

                /**
                 * Find first y so that sums of columns for 0-y is > count/2
                 * Update corresponding fields in smi.
                 *
                 * @param smi fields firstNonZeroX, horMidPos and horMidSum may be updated
                 * @return true if the above fields are usable
                 */

                public int findHorizontalMiddle(TileMetaInfo smi) {
                        if (getCount() == 0 || width < 2)
                                smi.setHorMidPos(0);
                        else if (smi.getHorMidPos() < 0) {
                                int start = (smi.getFirstNonZeroX() > 0) ? smi.getFirstNonZeroX() : 0;
                                long sum = 0;
                                long lastSum = 0;
                                long target = getCount()/2;

                                for (int pos = start; pos <= width; pos++) {
                                        lastSum = sum;
                                        sum += getColSum(pos, smi.getColSums());
                                        if (sum == 0)
                                                continue;
                                        if (lastSum <= 0)
                                                smi.setFirstNonZeroX(pos);
                                        if (sum > target){
                                                if (sum - target < target - lastSum && pos + 1 < width){
                                                        smi.setHorMidPos(pos+1);
                                                        smi.setHorMidSum(sum);
                                                } else {
                                                        smi.setHorMidPos(pos);
                                                        smi.setHorMidSum(lastSum);
                                                }
                                                break;
                                        }
                                }
                        }
                        return smi.getHorMidPos();
                }

                /**
                 * Find first x so that sums of rows for 0-x is > count/2.
                 * Update corresponding fields in smi.
                 * @param smi fields firstNonZeroY, vertMidPos, and vertMidSum may be updated
                 * @return true if the above fields are usable
                 */

                public int findVerticalMiddle(TileMetaInfo smi) {
                        if (getCount() == 0 || height < 2)
                                smi.setVertMidPos(0);
                        else if (smi.getVertMidPos() < 0) {
                                long sum = 0;
                                long lastSum;
                                long target = getCount()/2;
                                int start = (smi.getFirstNonZeroY() > 0) ? smi.getFirstNonZeroY() : 0;
                                for (int pos = start; pos <= height; pos++) {
                                        lastSum = sum;
                                        sum += getRowSum(pos, smi.getRowSums());
                                        if (sum == 0)
                                                continue;
                                        if (lastSum <= 0)
                                                smi.setFirstNonZeroY(pos);
                                        if (sum > target) {
                                                if (sum - target < target - lastSum && pos + 1 < height) {
                                                        smi.setVertMidPos(pos + 1);
                                                        smi.setVertMidSum(sum);
                                                } else {
                                                        smi.setVertMidPos(pos);
                                                        smi.setVertMidSum(lastSum);
                                                }
                                                break;
                                        }
                                }
                        }
                        return smi.getVertMidPos();
                }              

                /**
                 * Split at the given horizontal position.
                 * @param splitX the horizontal split line
                 * @return true if result in smi is OK
                 */

                public boolean splitHoriz(int splitX, TileMetaInfo smi) {
                        if (splitX <= 0 || splitX >= width)
                                return false;
                        long sum = 0;
                       
                        if (splitX <= width / 2){
                                int start = (smi.getFirstNonZeroX() > 0) ? smi.getFirstNonZeroX() : 0;
                                for (int pos = start; pos < splitX; pos++) {
                                        sum += getColSum(pos, smi.getColSums());
                                }
                        } else {
                                int end = (smi.getLastNonZeroX() > 0) ? smi.getLastNonZeroX() + 1: width;
                                for (int pos = splitX; pos < end; pos++) {
                                        sum += getColSum(pos, smi.getColSums());
                                }
                                sum = getCount() - sum;
                        }
                        if (sum < smi.getMinNodes() || getCount() - sum < smi.getMinNodes())
                                return false;
                        assert splitX > 0 && splitX < width;
                        Tile[] parts = smi.getParts();
                        parts[0] = new Tile(densityInfo, x, y, splitX, height, sum);
                        parts[1] = new Tile(densityInfo, x + splitX, y, width - splitX,height, getCount() - sum);
                        assert smi.getParts()[0].width + smi.getParts()[1].width == this.width;
                        return true;
                }

                /**
                 * Split at the given vertical position.
                 * @param splitY the vertical split line
                 * @return true if result in smi is OK
                 */

                public boolean splitVert(int splitY, TileMetaInfo smi) {
                        if (splitY <= 0 || splitY >= height)
                                return false;
                        long sum = 0;
                       
                        if (splitY <= height / 2){
                                int start = (smi.getFirstNonZeroY() > 0) ? smi.getFirstNonZeroY() : 0;
                                for (int pos = start; pos < splitY; pos++) {
                                        sum += getRowSum(pos, smi.getRowSums());
                                }
                        } else {
                                int end = (smi.getLastNonZeroY() > 0) ? smi.getLastNonZeroY()+1 : height;
                                for (int pos = splitY; pos < end; pos++) {
                                        sum += getRowSum(pos, smi.getRowSums());
                                }
                                sum = getCount() - sum;
                        }

                        if (sum < smi.getMinNodes() || getCount() - sum < smi.getMinNodes())
                                return false;
                        assert splitY > 0 && splitY < height;
                        Tile[] parts = smi.getParts();
                        parts[0] = new Tile(densityInfo, x, y, width, splitY, sum);
                        parts[1] = new Tile(densityInfo, x, y + splitY, width, height- splitY, getCount()- sum);
                        assert parts[0].height + parts[1].height == this.height;
                       
                        return true;
                }

                /**
                 *
                 * @param smi
                 * @return lowest horizontal position at which a split will work regarding minNodes
                 */

                public int findValidStartX(TileMetaInfo smi) {
                        if (smi.getValidStartX() >= 0)
                                return smi.getValidStartX();
                        long sum = 0;
                        int start = (smi.getFirstNonZeroX() > 0) ? smi.getFirstNonZeroX() : 0;
                        for (int i = start; i < width; i++) {
                                sum += getColSum(i, smi.getColSums());
                                if (sum == 0)
                                        continue;
                                if (smi.getFirstNonZeroX() < 0)
                                        smi.setFirstNonZeroX(i);
                                if (sum >= smi.getMinNodes()) {
                                        int splitPos = i + 1;
                                        smi.setValidStartX(splitPos);
                                        return splitPos;
                                }
                        }
                        smi.setValidStartX(width);
                        return width;
                }

                /**
                 *
                 * @param smi
                 * @return highest position at which all columns on the right have a sum < minNodes
                 */

                public int findValidEndX(TileMetaInfo smi) {
                        if (smi.getValidEndX() < 0){
                                int end = smi.getLastNonZeroX() > 0 ? smi.getLastNonZeroX() : width - 1;
                                long sum = 0;
                                for (int i = end; i >= 0; --i) {
                                        sum += getColSum(i, smi.getColSums());
                                        if (sum > 0 && smi.getLastNonZeroX() < 0)
                                                smi.setLastNonZeroX(i);
                                        if (sum >= smi.getMinNodes()){
                                                smi.setValidEndX(i);
                                                break;
                                        }
                                }
                        }
                        return smi.getValidEndX();
                }
               
                /**
                 *
                 * @param smi
                 * @return lowest vertical position at which a split will work regarding minNodes
                 * or height if no such position exists
                 */

                public int findValidStartY(TileMetaInfo smi) {
                        if (smi.getValidStartY() > 0)
                                return smi.getValidStartY();
                        long sum = 0;
                        int start = (smi.getFirstNonZeroY() > 0) ? smi.getFirstNonZeroY() : 0;
                        for (int i = start; i < height; i++) {
                                sum += getRowSum(i, smi.getRowSums());
                                if (sum == 0)
                                        continue;
                                if (smi.getFirstNonZeroY() < 0)
                                        smi.setFirstNonZeroY(i);
                                if (sum >= smi.getMinNodes()){
                                        int splitPos = i+1;
                                        smi.setValidStartY(splitPos);
                                        return splitPos;
                                }
                        }
                        smi.setValidStartY(height);
                        return height;
                }

                /**
                 *
                 * @param smi
                 * @return highest position at which all upper rows have a sum < minNodes
                 */

                public int findValidEndY(TileMetaInfo smi) {
                        if (smi.getValidEndY() < 0){
                                int end = smi.getLastNonZeroY() > 0 ? smi.getLastNonZeroY() : height - 1;
                                long sum = 0;
                                for (int i = end; i >= 0; --i) {
                                        sum += getRowSum(i, smi.getRowSums());
                                        if (sum > 0 && smi.getLastNonZeroY() < 0)
                                                smi.setLastNonZeroY(i);
                                        if (sum >= smi.getMinNodes()){
                                                smi.setValidEndY(i);
                                                break;
                                        }
                                }
                        }
                        return smi.getValidEndY();
                }
               
                public int findFirstXHigher(TileMetaInfo smi, long limit) {
                        long sum = 0;
                        int start = (smi.getFirstNonZeroX() > 0) ? smi.getFirstNonZeroX() : 0;
                        for (int i = start; i < width; i++) {
                                sum += getColSum(i, smi.getColSums());
                                if (sum == 0)
                                        continue;
                                if (smi.getFirstNonZeroX() < 0)
                                        smi.setFirstNonZeroX(i);
                                if (sum > limit) {
                                        return i;
                                }
                        }
                        return height;
                }

                public int findFirstYHigher(TileMetaInfo smi, long limit) {
                        long sum = 0;
                        int start = (smi.getFirstNonZeroY() > 0) ? smi.getFirstNonZeroY() : 0;
                        for (int i = start; i < height; i++) {
                                sum += getRowSum(i, smi.getRowSums());
                                if (sum == 0)
                                        continue;
                                if (smi.getFirstNonZeroY() < 0)
                                        smi.setFirstNonZeroY(i);
                                if (sum > limit) {
                                        return i;
                                }
                        }
                        return height;
                }
               
                public int findFirstHigher(int axis, TileMetaInfo smi, long limit) {
                        return axis == SplittableDensityArea.AXIS_HOR ? findFirstXHigher(smi, limit) : findFirstYHigher(smi, limit);
                }
                /**
                 *  
                 * @return aspect ratio of this tile
                 */

                public double getAspectRatio() {
                        return densityInfo.getAspectRatio(this);
                }
               
                /**
                 * Calculate the trimmed tile so that it has no empty outer rows or columns.
                 * Does not change the tile itself.
                 * @return the trimmed version of the tile.
                 */

                public Tile trim() {
                        long sumRemovedColCounts = 0;
                        long sumRemovedRowCounts = 0;
                        int minX = -1;
                        for (int i = 0; i < width; i++) {
                                long colSum = getColSum(i);
                                boolean needed = (densityInfo.getPolygonArea() == null) ? colSum > 0 : !colOutsidePolygon(i);
                                if (needed) {
                                        minX = x + i;
                                        break;
                                }
                                sumRemovedColCounts += colSum;
                        }
                        int maxX = -1;
                        for (int i = width - 1; i >= 0; i--) {
                                long colSum = getColSum(i);
                                boolean needed = (densityInfo.getPolygonArea() == null) ? colSum > 0 : !colOutsidePolygon(i);
                                if (needed) {
                                        maxX = x + i;
                                        break;
                                }
                                sumRemovedColCounts += colSum;
                        }
                        int minY = -1;
                        for (int i = 0; i < height; i++) {
                                long rowSum = getRowSum(i);
                                boolean needed = (densityInfo.getPolygonArea() == null) ? rowSum > 0 : !rowOutsidePolygon(i);
                                if (needed) {
                                        minY = y + i;
                                        break;
                                }
                                sumRemovedRowCounts += rowSum;
                        }
                        int maxY = -1;
                        for (int i = height - 1; i >= 0; i--) {
                                long rowSum = getRowSum(i);
                                boolean needed = (densityInfo.getPolygonArea() == null) ? rowSum > 0 : !rowOutsidePolygon(i);
                                if (needed) {
                                        maxY = y + i;
                                        break;
                                }
                                sumRemovedRowCounts += rowSum;
                        }
                        if (minX > maxX || minY > maxY || maxX < 0 || maxY < 0) {
                                return new Tile(densityInfo, x, y, 0, 0, 0);
                        }
                        long newCount = getCount();
                        int modWidth = maxX - minX + 1;
                        int modHeight = maxY - minY + 1;
                        if (densityInfo.getPolygonArea() != null) {
                                if (modWidth != width || modHeight != height) {
                                        // tile was trimmed, try hard to avoid a new costly calculation of the count
                                        // value
                                        if (width == modWidth) {
                                                newCount = getCount() - sumRemovedRowCounts;
                                        } else if (height == modHeight) {
                                                newCount = getCount() - sumRemovedColCounts;
                                        } else {
                                                // worst case: recalculate
                                                return new Tile(densityInfo, new Rectangle(minX, minY, modWidth, modHeight));
                                        }
                                }
                        }
                        return new Tile(densityInfo, minX, minY, modWidth, modHeight, newCount);
                }

                private boolean rowOutsidePolygon(int row) {
                        if (densityInfo.getPolygonArea() == null)
                                return false;
                        // performance critical part, check corners first
                        if (densityInfo.isGridElemInPolygon(x, y + row) || densityInfo.isGridElemInPolygon(x + width-1, y + row))
                                return false;
                        // check rest of row
                        for (int i = 1; i < width-1; i++) {
                                if (densityInfo.isGridElemInPolygon(x + i, y + row))
                                        return false;
                        }
                        return true;
                }

                private boolean colOutsidePolygon(int col) {
                        if (densityInfo.getPolygonArea() == null)
                                return false;
                        // performance critical part, check corners first
                        if (densityInfo.isGridElemInPolygon(x + col, y) || densityInfo.isGridElemInPolygon(x + col, y + height - 1))
                                return false;
                        // check rest of column
                        for (int i = 1; i < height - 1; i++) {
                                if (densityInfo.isGridElemInPolygon(x + col, y + i))
                                        return false;
                        }
                        return true;
                }

                public boolean outsidePolygon(){
                        java.awt.geom.Area polygonArea = densityInfo.getPolygonArea();
                        return  polygonArea != null && !polygonArea.intersects(getRealBBox());
                }

                /**
                 *
                 * Check if enough grid elements are inside the polygon.
                 * @param maxOutsideRatio the wanted ratio
                 * @return true if the ratio inside/outside is greater than the given value
                 */

                public boolean outsideRatioIsOK(final double maxOutsideRatio) {
                        if (densityInfo.allInsidePolygon())
                                return true;
                        Rectangle realBBox = getRealBBox();
                        // check special case: tile may contain the polygon
                        Rectangle polyBBox = densityInfo.getPolygonArea().getBounds();
                        if (realBBox.contains(polyBBox)) {
                                return true;
                        }
                        final long maxOutsde = (long) (maxOutsideRatio * (width * height));
                        final long neededInside = width * height - maxOutsde;
                        int countInside = 0;
                        int countOutside= 0;
                        for (int i = x; i < x + width; i++) {
                                for (int j = y; j < y + height; j++) {
                                        if (densityInfo.isGridElemInPolygon(i, j)) {
                                                if (++countInside >= neededInside)
                                                        return true;
                                        } else {
                                                if (++countOutside >= maxOutsde)
                                                        return false;
                                        }
                                }
                        }
                        return false;
                }
               
                public Rectangle getRealBBox(){
                        int shift = densityInfo.getDensityMap().getShift();
                        int polyYPos = densityInfo.getDensityMap().getBounds().getMinLat() + (y << shift);
                        int polyXPos = densityInfo.getDensityMap().getBounds().getMinLong() + (x << shift);
                        return new Rectangle(polyXPos, polyYPos, width<<shift, height<<shift);
                }

                @Override
                public int hashCode() {
                        return x << 24 | y << 16 | width << 8 | height;
                }
               
                @Override
                public String toString(){
                        Area area = densityInfo.getDensityMap().getArea(x,y,width,height);
                        return  (area.toString() + " with " + Utils.format(getCount()) + " nodes");
//                      StringBuilder sb = new StringBuilder();
//                      sb.append("(");
//                      sb.append(x);
//                      sb.append(",");
//                      sb.append(y);
//                      sb.append(",");
//                      sb.append(width);
//                      sb.append(",");
//                      sb.append(height);
//                      sb.append(") with ");
//                      sb.append(Utils.format(count));
//                      sb.append(" nodes and ratio ");
//                      sb.append(getAspectRatio());
//                      return sb.toString();          
                }

                /**
                 * return minimum number of parts when tile is split with the given maximum.
                 *
                 * @param maxNodes the maximum
                 * @return minimum number of parts for the given maximum
                 */

                public int getMinParts(long maxNodes) {
                        long minCount = countInside();
                        int nMin = (int) (minCount / maxNodes);
                        if (nMin * maxNodes < minCount)
                                nMin++;
                        return nMin;
                }
               
                public long countInside() {
                        long minCount = 0;
                        if (densityInfo.getPolygonArea() == null || densityInfo.allInsidePolygon())
                                return count;
                        for (int i = 0; i < width; i++) {
                                final int[] col = densityInfo.getMapCol(x + i);
                                if (col != null) {
                                        for (int k = 0; k < height; k++) {
                                                if (densityInfo.isGridElemInPolygon(x + i, y + k))
                                                        minCount += col[y + k];
                                        }
                                }
                        }
                        return minCount;
                }

                public int countElemsOutside() {
                        if (densityInfo.getPolygonArea() == null || densityInfo.allInsidePolygon())
                                return 0;
                        int num = 0;
                        for (int i = 0; i < width; i++) {
                                for (int k = 0; k < height; k++) {
                                        if (!densityInfo.isGridElemInPolygon(x + i, y + k))
                                                num++;
                                }
                        }
                        return num;
                }

                public List<Tile> divide(long maxNodes) {
                        if (getCount() < maxNodes)
                                return Arrays.asList(this);
                        List<Tile> parts = new ArrayList<>(2);
                        TileMetaInfo smi = new TileMetaInfo(this, null, null);
                        smi.setMinNodes(1); // don't create tiles with 0 nodes
                        boolean ok = false;
                        if (width > height) {
                                int start = findValidStartX(smi);
                                int end = findValidEndX(smi);
                                int mid = (start + end) / 2;
                                ok = splitHoriz(mid, smi);
                        } else {
                                int start = findValidStartY(smi);
                                int end = findValidEndY(smi);
                                int mid = (start + end) / 2;
                                ok = splitVert(mid, smi);
                        }
                        if (ok) {
                                for (Tile part : smi.getParts()) {
                                        parts.addAll(part.divide(maxNodes));
                                }
                        } else {
                                parts.add(this);
                        }
                        return parts;
                }
               
                public double getFillRatio() {
                        return (double)getCount() / (width * height);
                }
               
                /**
                 * Find largest count in single grid element. Might be outside of the polygon.
                 * @return largest count in single grid element
                 */

                int getLargestInfo() {
                        int largest = 0;
                        for (int i = 0; i < width; i++) {
                                final int[] col = densityInfo.getMapCol(x + i);
                                if (col != null) {
                                        for (int k = 0; k < height; k++) {
                                                int n = col[y+k];
                                                if (n > largest) {
                                                        largest = n;
                                                }
                                        }
                                }
                        }
                        return largest;
                }
        }