com.partnersoft.geometry.xy

Class XyGrid

java.lang.Object

com.partnersoft.geometry.xy.XyGrid

All Implemented Interfaces:

Immutable

Direct Known Subclasses:

XyGridSystem

public class XyGrid
extends java.lang.Object
implements Immutable

A quantization grid or tiling in (x, y) space.

Applying a grid to a geometric space is just like drawing the space on graph paper. The grid is oriented with the cartesian axes such that lines are horizontal and vertical. It may be offset from the (0, 0) origin by its own originX and originY parameters.

A cell width and height is specified; this is the width and height of all cells in the grid. A given cell can be described as a rectangle with minimum and maximum x and y parameters; the cell is understood to contain all values from (minX, minY) inclusive to (maxX, maxY) exclusive. Cells have their own coordinates within the grid, with consists of the number of cells to the left or west and the number of cells beneath or to the south of the cell. This is represented by an XyGridCell object.

As an example, let's present an integer quantization grid with cell width and height of 1.0, and originX and originY of 0.0.

Consider the following four points: (0.5, 0.5), (1.0, 1.0), (3.2, 9.6), and (-8.0, 5.0).

• The cell for (0.5, 0.5) is (0, 0); indeed it is the center of that cell.
• The cell for (1.0, 1.0) is (1, 1); it is the origin of that cell.
• The cell for (3.2, 9.6) is (3, 9).
• The cell for (-8.0, 5.0) is (-8, 5).

Mathematically, to find the cell for a given coordinate, you subtract the origin, divide by the width or height, and take the integer portion of the result. The offset within the cell is then equal to the remainder times the width or height.

 double dividedX = (x - originX) / width;
 double dividedY = (y - originY) / height;
 int cellX = (int) Math.floor(dividedX);
 int cellY = (int) Math.floor(dividedY);
 double cellOffsetX = (dividedX - cellX) * width;
 double cellOffsetY = (dividedY - cellY) * height;
 

Copyright 2007 Partner Software, Inc.

Author:

Paul Reavis

Constructor Summary

Constructors

Constructor and Description
XyGrid(double cellSize) Creates a grid with origin (0, 0) and square cells with the given size.
XyGrid(double cellWidth, double cellHeight) Creates a grid with origin (0, 0) and cells with the given width and height.
XyGrid(double originX, double originY, double cellSize) Creates a grid with origin (originX, originY) and square cells with the given size.
XyGrid(double originX, double originY, double cellWidth, double cellHeight) Creates a grid with origin (originX, originY) and cells with the given size.
XyGrid(XyPoint origin, XySize cellSize) Creates a grid with passed origin and cell size.
XyGrid(XySize cellSize) Creates a grid with origin 0,0 with the given cell size.

Method Summary

Methods

Modifier and Type	Method and Description
XyGridCell	cellContainingPoint(double x, double y) Returns the XyGridCell containing the passed point (x, y).
XyGridCell	cellContainingPoint(XyPoint point) Returns the XyGridCell containing the passed point.
java.util.Map<XyGridCell,java.util.List<XyLineSegment>>	chop(XyLineSegment segment) Splits the passed XyLineSegment into a Map of XyGridCells keyed to Lists of XyLineSegment pieces that the cell contains.
java.util.Map<XyGridCell,java.util.List<XyPolygon>>	chop(XyPolygon polygon) Splits the passed XyPolygon into a Map of XyGridCells keyed to Lists of XyPolygon pieces that the cell contains.
java.util.Map<XyGridCell,java.util.List<XyLineSegment>>	chop(XyPolyline polyline) Splits the passed XyPolyline into a Map of XyGridCells keyed to Lists of XyLineSegment pieces that the cell contains.
double	columnToX(int columnNumber) Returns the absolute origin X coordinate of a cell in the passed column number.
XySize	getCellSize() Returns an XySize describing this grid's cell size.
XyPoint	getOrigin() Returns this grid's origin point.
java.util.List<XyGridCell>	listCellsIntersecting(XyBounds bounds) Returns a List of XyGridCells intersected by the passed XyBounds
double	rowToY(int rowNumber) Returns the absolute origin Y coordinate of a cell in the passed row number.
int	xToColumn(double x) Returns the integer column number the passed x coordinate would fall within.
int	yToRow(double y) Returns the integer row number the passed y coordinate would fall within.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

XyGrid

public XyGrid(double cellSize)

Creates a grid with origin (0, 0) and square cells with the given size.

Parameters:

cellSize - - Size of grid's cells.

XyGrid

public XyGrid(double cellWidth,
      double cellHeight)

Creates a grid with origin (0, 0) and cells with the given width and height.

Parameters:

cellWidth - - Width of grid's cells.

cellHeight - - Height of grid's cells.

XyGrid

public XyGrid(double originX,
      double originY,
      double cellSize)

Creates a grid with origin (originX, originY) and square cells with the given size.

Parameters:

originX - origin of grid (x)

originY - origin of grid (y)

cellSize - width and height of cells

XyGrid

public XyGrid(double originX,
      double originY,
      double cellWidth,
      double cellHeight)

Creates a grid with origin (originX, originY) and cells with the given size.

Parameters:

originX - - Origin of grid (x)

originY - - Origin of grid (y)

cellWidth - - Width of grid's cells.

cellHeight - - Height of grid's cells.

XyGrid

public XyGrid(XySize cellSize)

Creates a grid with origin 0,0 with the given cell size.

Parameters:

cellSize - - XySize for grid's cells.

XyGrid

public XyGrid(XyPoint origin,
      XySize cellSize)

Creates a grid with passed origin and cell size.

Parameters:

origin - - XyPoint for grid's origin.

cellSize - - XySize for cell size.

Method Detail

cellContainingPoint

public XyGridCell cellContainingPoint(XyPoint point)

Returns the XyGridCell containing the passed point.

Parameters:

point - - XyPoint to find containing cell for.

Returns:

XyGridCell containing passed point.

cellContainingPoint

public XyGridCell cellContainingPoint(double x,
                             double y)

Returns the XyGridCell containing the passed point (x, y).

Parameters:

x - - X coordinate of point to find container cell for

y - - Y coordinate of point to find container cell for

Returns:

XyGridCell containing point

listCellsIntersecting

public java.util.List<XyGridCell> listCellsIntersecting(XyBounds bounds)

Returns a List of XyGridCells intersected by the passed XyBounds

Parameters:

bounds - - XyBounds to find intersecting cells for

Returns:

List of XyGridCells

chop

public java.util.Map<XyGridCell,java.util.List<XyPolygon>> chop(XyPolygon polygon)

Splits the passed XyPolygon into a Map of XyGridCells keyed to Lists of XyPolygon pieces that the cell contains.

Returned Map will not contain any key cells in coordinate space less than this grid's origin.

Parameters:

polygon - - XyPolygon to split

Returns:

Map of XyGridCells keyed to Lists of XyPolygons.

chop

public java.util.Map<XyGridCell,java.util.List<XyLineSegment>> chop(XyLineSegment segment)

Splits the passed XyLineSegment into a Map of XyGridCells keyed to Lists of XyLineSegment pieces that the cell contains.

Returned Map will not contain any key cells in coordinate space less than this grid's origin.

Parameters:

segment - - XyLineSegment to split

Returns:

Map of XyGridCells keyed to Lists of XyLineSegments.

chop

public java.util.Map<XyGridCell,java.util.List<XyLineSegment>> chop(XyPolyline polyline)

Splits the passed XyPolyline into a Map of XyGridCells keyed to Lists of XyLineSegment pieces that the cell contains.

Returned Map will not contain any key cells in coordinate space less than this grid's origin.

Parameters:

polyline - - XyPolyline to split

Returns:

Map of XyGridCells keyed to Lists of XyLineSegments.

xToColumn

public int xToColumn(double x)

Returns the integer column number the passed x coordinate would fall within. First column is 0.

Passed value should be absolute to coordinate system.

Parameters:

x - - X coordinate to find column number for

Returns:

0 based integer column number containing passed x.

yToRow

public int yToRow(double y)

Returns the integer row number the passed y coordinate would fall within. First row is 0.

Passed value should be absolute to coordinate system.

Parameters:

y - - Y coordinate to find row number for

Returns:

0 based integer row number containing passed y.

columnToX

public double columnToX(int columnNumber)

Returns the absolute origin X coordinate of a cell in the passed column number.

Parameters:

columnNumber - - 0 based index of column origin to retrieve.

Returns:

Absolute x coordinate for requested column.

rowToY

public double rowToY(int rowNumber)

Returns the absolute origin Y coordinate of a cell in the passed row number.

Parameters:

rowNumber - - 0 based index of row origin to retrieve.

Returns:

Absolute y coordinate for requested row.

getOrigin

public XyPoint getOrigin()

Returns this grid's origin point.

Returns:

grid origin point

getCellSize

public XySize getCellSize()

Returns an XySize describing this grid's cell size.

Returns:

XySize describing cell size.