GlobalNavigation
Class Grid

java.lang.Object
  GlobalNavigation.Grid

All Implemented Interfaces:

java.lang.Iterable<Grid.Cell>

public class Grid
extends java.lang.Object
implements java.lang.Iterable<Grid.Cell>

Grid for path planning.

Nested Class Summary

class	Grid.Cell
protected class	Grid.GridIterator An iterator over cell.

Field Summary

protected Grid.Cell[][]	cell The grid cells.
protected int	cols Number of cols in the grid.
protected double	resolution Grid resolution.
protected int	rows Number of rows in the grid.
protected java.awt.geom.Rectangle2D.Double	worldBounds World boundary.

Constructor Summary

Grid(java.awt.geom.Rectangle2D.Double worldBounds, double resolution)
Create a new grid.

Method Summary

protected java.util.List<Grid.Cell>	collectNeighbors(Grid.Cell c, java.util.List<Grid.Cell> neighbors) Collect all the (Manhattan) neighbors of cell.
double	computeShortestPaths(java.awt.geom.Point2D.Double goalPoint) Compute and cache the shortest (Manhattan) paths (BFS) from each cell in the grid to the cell containing goalPoint.
Grid.Cell	getCell(java.awt.geom.Point2D.Double point) Get the cell containing point, or null if out of bounds.
java.util.Iterator<Grid.Cell>	iterator() Get a Grid.GridIterator over cell.
int	markObstacle(PolygonObstacle obstacle) Mark all the Grid.Cell that PolygonObstacle.intersects(double, double, double, double) obstacle not Grid.Cell.free.
int	numCells() Get the number of cells in this Grid.

Methods inherited from class java.lang.Object

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

Field Detail

worldBounds

protected java.awt.geom.Rectangle2D.Double worldBounds

World boundary.

resolution

protected double resolution

Grid resolution.

rows

protected int rows

Number of rows in the grid.

cols

protected int cols

Number of cols in the grid.

cell

protected Grid.Cell[][] cell

The grid cells.

Constructor Detail

Grid

public Grid(java.awt.geom.Rectangle2D.Double worldBounds,
            double resolution)

Create a new grid.

Parameters:

worldBounds - the world boundary

resolution - the grid resolution

Method Detail

markObstacle

public int markObstacle(PolygonObstacle obstacle)

Mark all the Grid.Cell that PolygonObstacle.intersects(double, double, double, double) obstacle not Grid.Cell.free.

Parameters:

obstacle - the obstacle

Returns:

the number of cells marked

computeShortestPaths

public double computeShortestPaths(java.awt.geom.Point2D.Double goalPoint)

Compute and cache the shortest (Manhattan) paths (BFS) from each cell in the grid to the cell containing goalPoint.

Only Grid.Cell.free cells are traversed.

Parameters:

goalPoint - the goal point

Returns:

the maximum path distance from any cell which can reach the goal to the goal, or Double.POSITIVE_INFINITY if goalPoint is out of bounds

collectNeighbors

protected java.util.List<Grid.Cell> collectNeighbors(Grid.Cell c,
                                                     java.util.List<Grid.Cell> neighbors)

Collect all the (Manhattan) neighbors of cell.

Parameters:

c - the cell

neighbors - the neighbors are collected here

Returns:

a ref to neighbors

getCell

public Grid.Cell getCell(java.awt.geom.Point2D.Double point)

Get the cell containing point, or null if out of bounds.

Parameters:

point - the query point

Returns:

the cell containing point, or null if out of bounds

iterator

public java.util.Iterator<Grid.Cell> iterator()

Get a Grid.GridIterator over cell.

Specified by:

iterator in interface java.lang.Iterable<Grid.Cell>

numCells

public int numCells()

Get the number of cells in this Grid.

Returns:

the number of cells in this Grid