gvSIG projects pool

/*

 * To change this license header, choose License Headers in Project Properties.

 * To change this template file, choose Tools | Templates

 * and open the template in the editor.

 */

package org.gvsig.online.lib.impl;

import java.awt.Dimension;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.HashSet;

import java.util.Iterator;

import java.util.List;

import java.util.Set;

import org.apache.commons.lang3.builder.HashCodeBuilder;

import org.gvsig.fmap.geom.Geometry;

import org.gvsig.fmap.geom.GeometryLocator;

import org.gvsig.fmap.geom.GeometryManager;

import org.gvsig.fmap.geom.GeometryUtils;

import org.gvsig.fmap.geom.exception.CreateEnvelopeException;

import org.gvsig.fmap.geom.operation.GeometryOperationException;

import org.gvsig.fmap.geom.operation.GeometryOperationNotSupportedException;

import org.gvsig.fmap.geom.primitive.Envelope;

import org.gvsig.tools.ToolsLocator;

import org.gvsig.tools.i18n.I18nManager;

import org.gvsig.tools.library.impl.DefaultLibrariesInitializer;

import org.gvsig.tools.task.SimpleTaskStatus;

import org.gvsig.tools.task.UserCancelTaskException;

/**

 *

 * @author jjdelcerro

 */

@SuppressWarnings("UseSpecificCatch")

public class TilesCalculator {

    public interface CalculatorData {

        public Envelope getEnvelope();

        public double getWidth();

        public double getHeight();

        public long getElements(Envelope envelope);

    }

    private class Cell implements Comparable<Cell>{

        int col;

        int row;

        int colspan;

        int rowspan;

        boolean removed;

        public Cell(int col,int row) {

            this.col = col;

            this.row = row;

            this.removed = false;

        }

        public boolean canSpanCol(Cell other) {

            return (this.row == other.row) && ( this.col+this.colspan+1 == other.col )  && (this.rowspan == other.rowspan);

        }

        public boolean canSpanRow(Cell other) {

            return (this.col == other.col) && ( this.row+this.rowspan+1 == other.row )  && (this.colspan == other.colspan);

        }

        @Override

        public int compareTo(Cell other) {

            int r = Integer.compare(this.row, other.row);

            if( r==0 ) {

                r = Integer.compare(this.col, other.col);

            }

            return r;

        }

        public Envelope getEnvelope(int cellsize) throws CreateEnvelopeException {

            Envelope env = getGeometryManager().createEnvelope(

                    (cellsize*col),

                    (cellsize*row),

                    (cellsize*(col+colspan+1)),

                    (cellsize*(row+rowspan+1)),

                    Geometry.SUBTYPES.GEOM2D

            );

            return env;

        }

        @Override

        public String toString() {

            return "row:"+row+",col:"+col+",colspan:"+colspan+",rowspan:"+rowspan+",removed:"+removed;

        }

        @Override

        public boolean equals(Object other0) {

            if( !(other0 instanceof Cell) ) {

                return false;

            }

            Cell other = (Cell)other0;

            return this.col == other.col 

                    && this.row == other.row 

                    && this.colspan == other.colspan 

                    && this.rowspan == other.rowspan;

        }

        @Override

        public int hashCode() {

            HashCodeBuilder builder = new HashCodeBuilder();

            return builder.append(this.getClass().hashCode())

                    .append(this.col)

                    .append(this.row)

                    .append(this.colspan)

                    .append(this.rowspan)

                    .toHashCode();                    

        }

    }

    private GeometryManager geometryManager ;

    public TilesCalculator() {

    }    

    private double getArea(Envelope env) throws GeometryOperationNotSupportedException, GeometryOperationException {

        return env.getGeometry().area();

    }

    private GeometryManager getGeometryManager() {

        if( this.geometryManager==null ) {

            this.geometryManager = GeometryLocator.getGeometryManager();

        }

        return this.geometryManager;

    }

    private Envelope[] getNextLevel(Envelope env) throws CreateEnvelopeException {

        double with = env.getLength(Geometry.DIMENSIONS.X) / 2.0;

        double height = env.getLength(Geometry.DIMENSIONS.Y) / 2.0;

        Envelope[] envs = new Envelope[] {

            this.getGeometryManager().createEnvelope(

                env.getMinimum(Geometry.DIMENSIONS.X),

                env.getMinimum(Geometry.DIMENSIONS.Y),

                env.getMinimum(Geometry.DIMENSIONS.X)+with,

                env.getMinimum(Geometry.DIMENSIONS.Y)+height,

                Geometry.SUBTYPES.GEOM2D

            ),

            this.getGeometryManager().createEnvelope(

                env.getMinimum(Geometry.DIMENSIONS.X),

                env.getMinimum(Geometry.DIMENSIONS.Y)+height,

                env.getMinimum(Geometry.DIMENSIONS.X)+with,

                env.getMaximum(Geometry.DIMENSIONS.Y),

                Geometry.SUBTYPES.GEOM2D

            ),

            this.getGeometryManager().createEnvelope(

                env.getMinimum(Geometry.DIMENSIONS.X)+with,

                env.getMinimum(Geometry.DIMENSIONS.Y),

                env.getMaximum(Geometry.DIMENSIONS.X),

                env.getMinimum(Geometry.DIMENSIONS.Y)+height,

                Geometry.SUBTYPES.GEOM2D

            ),

            this.getGeometryManager().createEnvelope(

                env.getMinimum(Geometry.DIMENSIONS.X)+with,

                env.getMinimum(Geometry.DIMENSIONS.Y)+height,

                env.getMaximum(Geometry.DIMENSIONS.X),

                env.getMaximum(Geometry.DIMENSIONS.Y),

                Geometry.SUBTYPES.GEOM2D

            )

        };

        return envs;

    }

    private Dimension getDimension(Envelope env) throws GeometryOperationNotSupportedException, GeometryOperationException {

        double area = getArea(env);

        int cellSize = (int) Math.sqrt(area);

        return new Dimension(cellSize,cellSize);

    }

    public Dimension calculateCellSize(CalculatorData data) {

        return this.calculateCellSize(data, 1000, null);

    }

    public Dimension calculateCellSize(CalculatorData data, long maxElementsByCell, SimpleTaskStatus status) {

        I18nManager i18n = ToolsLocator.getI18nManager();

        if (status == null) {

            status = ToolsLocator.getTaskStatusManager().createDefaultSimpleTaskStatus(i18n.getTranslation("_Calculating_cell_size"));

            status.setAutoremove(true);

            status.add();

        } else {

            status.push();

        }

        try {

            status.setIndeterminate();

            status.setCurValue(0);

            Envelope curEnvelope = data.getEnvelope();

            long totalElements = data.getElements(curEnvelope);

            if( totalElements < maxElementsByCell ) {

                status.terminate();

                return getDimension(curEnvelope);

            }

            while(true) {

                if( status.isCancellationRequested() ) {

                    status.cancel();

                    throw new UserCancelTaskException();

                }

                long maxElements = 0;

                Envelope maxElementsEnvelope = null;

                for (Envelope envelope : getNextLevel(curEnvelope)) {

                    long numElements = data.getElements(envelope);

                    if( maxElements < numElements ) {

                        maxElements = numElements;

                        maxElementsEnvelope = envelope;

                    }

                }

                if( maxElements>0 && maxElements<=maxElementsByCell) {

                    status.terminate();

                    return getDimension(maxElementsEnvelope);

                }

                curEnvelope = maxElementsEnvelope;

            }

        } catch(Throwable t) {

            throw new RuntimeException("Can't calculate grid cell size", t);

        } finally {

            status.pop();

        }

    }

    private Cell calculateCell( int cellSize, double x, double y) {

//        Envelope fullenv = data.getEnvelope();

//        int cellx = (int) ((x - fullenv.getMinimum(Geometry.DIMENSIONS.X))/cellSize);

//        int celly = (int) ((y - fullenv.getMinimum(Geometry.DIMENSIONS.Y))/cellSize);

        int cellx = (int) (x/cellSize);

        int celly = (int) (y/cellSize);

        return new Cell(cellx,celly);

    }

    private List<Cell> calculateCell(int cellSize, Geometry geom) {

        Envelope geomenv = geom.getEnvelope();

        Cell upperLeftCell = calculateCell(

                cellSize, 

                geomenv.getMinimum(Geometry.DIMENSIONS.X),

                geomenv.getMinimum(Geometry.DIMENSIONS.Y)

        );

        Cell bottomRightCell = calculateCell(

                cellSize, 

                geomenv.getMaximum(Geometry.DIMENSIONS.X),

                geomenv.getMaximum(Geometry.DIMENSIONS.Y)

        );

        List<Cell> cells = new ArrayList<>();

        for (int i = upperLeftCell.col; i <= bottomRightCell.col; i++) {

            for (int j = upperLeftCell.row; j <= bottomRightCell.row; j++) {

                cells.add(new Cell(i,j));

            }            

        }

        return cells;

    }

    private List<Cell> calculateCells(int cellSize, Iterator<Geometry> geoms) {

        Set<Cell> cells = new HashSet<>();

        while (geoms.hasNext()) {

            Geometry g = geoms.next();

            if (g != null) {

                cells.addAll(calculateCell(cellSize, g));

            }

        }

        List<Cell> orderedCells = new ArrayList<>(cells);

        Collections.sort(orderedCells);

        return orderedCells;

    }

    private void joinCells(List<Cell> orderedCells) {

            for (Cell cell1 : orderedCells) {

                if( cell1.removed ) {

                    continue;

                }

                for (Cell cell2 : orderedCells) {

                    if( cell2.removed ) {

                        continue;

                    }

                    if( cell1.canSpanCol(cell2) ) {

                        cell1.colspan++;

                        cell2.removed = true;

                    }

                }        

            }

            for (Cell cell1 : orderedCells) {

                if( cell1.removed ) {

                    continue;

                }

                for (Cell cell2 : orderedCells) {

                    if( cell2.removed ) {

                        continue;

                    }

                    if( cell1.canSpanRow(cell2) ) {

                        cell1.rowspan++;

                        cell2.removed = true;

                    }

                }        

            }

    }

    public List<Envelope> calculateEnvelopes(int cellSize, List<Geometry> geoms) {

        return calculateEnvelopes(cellSize, geoms.iterator());

    }

    public List<Envelope> calculateEnvelopes(int cellSize, Iterator<Geometry> geoms) {

        try {

            List<Cell> orderedCells = calculateCells(cellSize, geoms);

            joinCells(orderedCells);

            List<Envelope> envs = new ArrayList<>();

            for (Cell cell : orderedCells) {

                if( cell.removed ) {

                    continue;

                }

                envs.add(cell.getEnvelope(cellSize));

            }

            return envs;

        } catch(Throwable t) {

            throw new RuntimeException("Can't calculate envelops of geometries", t);

        }

    }

    /*

cols 10

row  10

cellsize 100

env 0,0 1000,1000

r1c7 - 720,120 760,150

r1c8 - 820,120 860,150

r2c8 - 820,220 860,250

r3c7 - 720,320 760,350

r6c0 -

r6c1 -

r6c2 -

r7c0 -

r7c1 -

r7c2 -

r6c4 - 450,650 650,650

r6c5 - 450,650 650,650

r6c6 - 450,650 650,650

       c0 c1 c2 c3 c4 c5 c6 c7 c8 c9

    r0

    r1                      x  x

    r2                         x

    r3                      x

    r4

    r5

    r6  xxxxxx      xxxxxx

    r7  xxxxxx

    r8  

    r9  

    */

    public static void main(String[] args) {

        new DefaultLibrariesInitializer().fullInitialize();

        Geometry[] elements = new Geometry[] {

            GeometryUtils.createFrom("LINESTRING (720 120, 760 150)"),

            GeometryUtils.createFrom("LINESTRING (820 120, 860 150)"),

            GeometryUtils.createFrom("LINESTRING (820 220, 860 250)"),

            GeometryUtils.createFrom("LINESTRING (720 320, 760 350)"),

            GeometryUtils.createFrom("LINESTRING ( 50 650, 250 650)"),

            GeometryUtils.createFrom("LINESTRING (450 650, 650 650)"),

            GeometryUtils.createFrom("LINESTRING ( 50 750, 250 750)")

        };

        CalculatorData data = new CalculatorData() {

            @Override

            public Envelope getEnvelope() {

                return GeometryUtils.createEnvelope(0, 0, 1000, 1000, Geometry.SUBTYPES.GEOM2D);

            }

            @Override

            public double getWidth() {

                return 1000;

            }

            @Override

            public double getHeight() {

                return 1000;

            }

            @Override

            public long getElements(Envelope envelope) {

                int n = 0;

                for (Geometry geom : elements) {

                    if( envelope.intersects(geom) ) {

                        n++;

                    }

                }

                return n;

            }

        };

        TilesCalculator calculator = new TilesCalculator();

        Dimension dim = calculator.calculateCellSize(data,1,null);

        System.out.println(dim.width+", "+dim.height);

        System.out.println("Celdas con elementos:");

        List<Cell> cells = calculator.calculateCells(100, Arrays.asList(elements).iterator());

        for (Cell cell : cells) {

            System.out.println(cell);

        }

        System.out.println("Celdas con elementos conm los join:");

        calculator.joinCells(cells);

        for (Cell cell : cells) {

            System.out.println(cell);

        }

/*

62, 62

Celdas con elementos:

row:1,col:7,colspan:0,rowspan:0,removed:false

row:1,col:8,colspan:0,rowspan:0,removed:false

row:2,col:8,colspan:0,rowspan:0,removed:false

row:3,col:7,colspan:0,rowspan:0,removed:false

row:6,col:0,colspan:0,rowspan:0,removed:false

row:6,col:1,colspan:0,rowspan:0,removed:false

row:6,col:2,colspan:0,rowspan:0,removed:false

row:6,col:4,colspan:0,rowspan:0,removed:false

row:6,col:5,colspan:0,rowspan:0,removed:false

row:6,col:6,colspan:0,rowspan:0,removed:false

row:7,col:0,colspan:0,rowspan:0,removed:false

row:7,col:1,colspan:0,rowspan:0,removed:false

row:7,col:2,colspan:0,rowspan:0,removed:false

Celdas con elementos con los join:

row:1,col:7,colspan:1,rowspan:0,removed:false

row:1,col:8,colspan:0,rowspan:0,removed:true

row:2,col:8,colspan:0,rowspan:0,removed:false

row:3,col:7,colspan:0,rowspan:0,removed:false

row:6,col:0,colspan:2,rowspan:1,removed:false

row:6,col:1,colspan:0,rowspan:0,removed:true

row:6,col:2,colspan:0,rowspan:0,removed:true

row:6,col:4,colspan:2,rowspan:0,removed:false

row:6,col:5,colspan:0,rowspan:0,removed:true

row:6,col:6,colspan:0,rowspan:0,removed:true

row:7,col:0,colspan:2,rowspan:0,removed:true

row:7,col:1,colspan:0,rowspan:0,removed:true

row:7,col:2,colspan:0,rowspan:0,removed:true        

*/      

    }

}