public class PolygonGrid extends java.lang.Object implements Graph<PointI>
RegularPolygon
which must have either four or six
RegularPolygon.sides
.
Each polygonal element within the PolygonGrid
corresponds to a coordinate pair
within an integer rectangle. That is, coordinates range from zero to a user-defined
width and height. The exact mapping of elements to coordinates depends on the underlying
RegularPolygon
and on the associated PolygonGridShift
value.
PolygonGrid
supports generic graph algorithms through its implementation of the
Graph
interface. The graph nodes are the PointI
coordinates of all grid
locations. Two nodes are considered connected if they correspond to neighboring grid
locations. The distance measure is the number of intervening grid locations.
Other methods provide topological information on grid locations, conversion to and from
Graph
world coordinates defined by the size of the supplied RegularPolygon
,
and the creation of a read-only wrapper.
Note: PolygonGrid
defines its location by Integer
indices but unlike
geometric primitives, calculations do not check for Integer
overflow. We assume that
PolygonGrid
always has a fairly moderate size so that overflow cannot occur.
Modifier and Type | Field and Description |
---|---|
static PointI |
INVALID_LOCATION
Represents an invalid
PolygonGrid location. |
boolean |
isReadOnly
Indicates whether the
PolygonGrid is read-only. |
Constructor and Description |
---|
PolygonGrid(PolygonGrid grid)
Creates a
PolygonGrid that is a copy of the specified instance. |
PolygonGrid(RegularPolygon element)
Creates a
PolygonGrid with the specified element() . |
PolygonGrid(RegularPolygon element,
PolygonGridShift gridShift)
|
Modifier and Type | Method and Description |
---|---|
static boolean |
areCompatible(RegularPolygon element,
PolygonGridShift gridShift)
Determines whether the specified
RegularPolygon is compatible
with the specified PolygonGridShift for a PolygonGrid . |
PolygonGrid |
asReadOnly()
Creates a read-only view of the
PolygonGrid . |
SizeD |
centerDistance()
Gets the world distance between the center points of neighboring
element() shapes. |
int |
connectivity()
Gets the maximum number of direct neighbors for any
Graph node. |
boolean |
contains(int column,
int row)
Determines whether the
PolygonGrid contains the specified column and row indices. |
boolean |
contains(PointI node)
Determines whether the
Graph contains the specified node. |
boolean |
contains(RectI rect)
Determines whether the
PolygonGrid entirely contains the specified RectI . |
<T> T[][] |
createArray(java.lang.Class<T> clazz)
Creates a two-dimensional array with the same
size() as the PolygonGrid . |
PointI[][] |
edgeNeighborOffsets()
Gets all coordinate offsets to reach a neighboring location on a shared edge.
|
RegularPolygon |
element()
Gets the
RegularPolygon that constitutes a PolygonGrid element. |
PointI |
findNearestNode(PointD location)
|
double |
getDistance(PointI source,
PointI target)
Gets the distance between two specified
Graph nodes. |
PointI[] |
getEdgeNeighborOffsets(PointI location)
Gets the inner array of
edgeNeighborOffsets() that matches the specified location. |
RectD |
getElementBounds(int column,
int row)
Gets the bounding rectangle of the
element() at the specified column and row indices. |
RectD |
getElementBounds(PointI location)
Gets the bounding rectangle of the
element() at the specified location. |
RectD |
getElementBounds(RectI region)
|
PointD[] |
getElementVertices(int column,
int row)
Gets the polygon vertices of the
element() at the specified column and row indices. |
PointI |
getNeighbor(PointI location,
int index)
Gets the location that borders the specified location on the specified edge or vertex.
|
int |
getNeighborIndex(PointI location,
PointI neighbor)
Gets the edge or vertex on which the specified location borders another neighboring location.
|
PointI[] |
getNeighborOffsets(PointI location)
Gets the inner array of
neighborOffsets() that matches the specified location. |
java.util.List<PointI> |
getNeighbors(PointI node)
Gets all direct neighbors of the specified
Graph node. |
java.util.List<PointI> |
getNeighbors(PointI node,
int steps)
Gets all neighbors of the specified
Graph node within the specified step distance. |
int |
getStepDistance(PointI source,
PointI target)
Determines the distance between two specified locations, in movement steps.
|
PointD |
getWorldLocation(PointI node)
Gets the world location of the specified
Graph node. |
PointD[] |
getWorldRegion(PointI node)
Gets the world region covered by the specified
Graph node. |
PolygonGridShift |
gridShift()
Gets a
PolygonGridShift value indicating how rows and columns are shifted. |
PointD |
gridToWorld(int column,
int row)
Converts the specified column and row indices to world coordinates.
|
PointD |
gridToWorld(PointI location)
Converts the specified
PointI location to world coordinates. |
boolean |
isValid(int column,
int row)
Determines whether the specified column and row indices are valid.
|
boolean |
isValid(PointI location)
Determines whether the specified
PointI location is valid. |
PointI[][] |
neighborOffsets()
Gets all coordinate offsets to reach a neighboring location.
|
int |
nodeCount()
|
java.util.List<PointI> |
nodes()
Gets all nodes in the
Graph . |
void |
setElement(RegularPolygon element)
Sets the
RegularPolygon that constitutes a PolygonGrid element. |
void |
setGridShift(PolygonGridShift gridShift)
Sets a
PolygonGridShift value indicating how rows and columns are shifted. |
void |
setSize(SizeI size)
Sets the number of rows and columns in the
PolygonGrid . |
SizeI |
size()
Gets the number of rows and columns in the
PolygonGrid . |
RectD |
worldBounds()
Gets the world bounds of the
PolygonGrid . |
PointI |
worldToGrid(double x,
double y)
Converts the specified world coordinates to a
PointI location. |
PointI |
worldToGrid(PointD location)
|
PointI |
worldToGridClipped(double x,
double y)
|
PointI |
worldToGridClipped(PointD location)
|
public static final PointI INVALID_LOCATION
PolygonGrid
location.
Holds a PointI
whose PointI.x
and PointI.y
components are both -1.
This represents a location outside of any PolygonGrid
since column and row indices
are always zero-based.
Various PolygonGrid
methods return INVALID_LOCATION
to indicate that a
valid PolygonGrid
location could not be found. Clients are encouraged to use this
read-only field for the same purpose.
public final boolean isReadOnly
PolygonGrid
is read-only.
Attempting to modify a read-only PolygonGrid
will throw an IllegalStateException
.
Use asReadOnly()
to create a read-only wrapper around a given PolygonGrid
.public PolygonGrid(RegularPolygon element)
PolygonGrid
with the specified element()
.
gridShift()
is set to an appropriate default value for element
.
size()
is set to a default value of (1,1).element
- the RegularPolygon
that constitutes an element of the PolygonGrid
java.lang.IllegalArgumentException
- if element
is neither a square nor a hexagonjava.lang.NullPointerException
- if element
is null
public PolygonGrid(RegularPolygon element, PolygonGridShift gridShift)
PolygonGrid
with the specified element()
and gridShift()
.
size()
is set to a default value of (1,1).element
- the RegularPolygon
that constitutes an element of the PolygonGrid
gridShift
- a PolygonGridShift
value indicating the shifting of rows or columns
in the PolygonGrid
java.lang.IllegalArgumentException
- if element
is neither a square nor a hexagon,
or gridShift
is incompatible with element
java.lang.NullPointerException
- if element
or gridShift
is null
public PolygonGrid(PolygonGrid grid)
PolygonGrid
that is a copy of the specified instance.
The two PolygonGrid
instances share no mutable data and can be altered independently.grid
- the PolygonGrid
whose data to copy to the new instancejava.lang.NullPointerException
- if grid
is null
public SizeD centerDistance()
element()
shapes.
SizeD.width
holds the horizontal distance between neighboring elements
within the same row, and SizeD.height
holds the vertical distance between
neighboring elements within the same column.SizeD
indicating the distance, in world coordinates, between the center
points of neighboring element()
shapes, given the current gridShift()
public PointI[][] edgeNeighborOffsets()
neighborOffsets()
except that inner arrays never contain offsets
to neighboring locations on shared vertices, even if RegularPolygon.vertexNeighbors
is true
for the current element()
. Use getEdgeNeighborOffsets(org.kynosarges.tektosyne.geometry.PointI)
to determine the correct inner array for a given location.
Note: For better performance, each PolygonGrid
instance directly returns its
own copy of this array, rather than making another copy on each edgeNeighborOffsets()
call. Do not change the array contents!
PointI
instances
whose coordinates range from -1 to +1 in both dimensionspublic final RegularPolygon element()
RegularPolygon
that constitutes a PolygonGrid
element.
Always either a square or a hexagon.RegularPolygon
that constitutes a PolygonGrid
elementpublic final PolygonGridShift gridShift()
PolygonGridShift
value indicating how rows and columns are shifted.
Automatically reset to an appropriate default value by setElement(org.kynosarges.tektosyne.geometry.RegularPolygon)
if the new
element()
is incompatible with the current value. The following table shows the
default gridShift()
values for all possible element()
shapes:
element | gridShift |
---|---|
Square on Edge | PolygonGridShift.NONE |
Square on Vertex | PolygonGridShift.ROW_RIGHT |
Hexagon on Edge | PolygonGridShift.COLUMN_DOWN |
Hexagon on Vertex | PolygonGridShift.ROW_RIGHT |
PolygonGridShift
value indicating how rows and columns are shiftedpublic PointI[][] neighborOffsets()
gridShift()
is null
,
or two arrays for any other gridShift()
value. In that case, the first inner array
contains offsets for left-shifted rows or up-shifted columns, and the second inner array
contains offsets for right-shifted rows or down-shifted columns.
The inner arrays contain the number of index positions indicated by the
RegularPolygon.connectivity
of the current element()
.
The array element at index position [i][j] contains the coordinate offsets
to reach the neighboring location on edge j when the current location resides in an
odd- or even-numbered row or column, as indicated by i. Counting starts at the topmost
edge if RegularPolygon.hasTopIndex
is true
and with the edge to the right
of the topmost vertex otherwise, continuing clockwise.
If RegularPolygon.vertexNeighbors
is true
for the current element()
,
the inner arrays instead contain the offsets to the neighboring locations on all edges
and vertices in an alternating sequence. Counting starts with the topmost edge for
PolygonOrientation.ON_EDGE
orientation and with the topmost vertex otherwise,
continuing clockwise.
Use getNeighborOffsets(org.kynosarges.tektosyne.geometry.PointI)
to determine the correct inner array for a given location.
Use getNeighbor(org.kynosarges.tektosyne.geometry.PointI, int)
and getNeighbors(org.kynosarges.tektosyne.geometry.PointI)
to directly find one or more neighbors
of a given location.
Note: For better performance, each PolygonGrid
instance directly returns its
own copy of this array, rather than making another copy on each neighborOffsets()
call.
Do not change the array contents!
PointI
instances
whose coordinates range from -2 to +2 in both dimensionspublic final SizeI size()
PolygonGrid
.
Each dimension is always at equal to or greater than one.SizeI
whose SizeI.height
indicates the number of rows
and whose SizeI.width
indicates the number of columnspublic RectD worldBounds()
PolygonGrid
.
RectD.min
is always (0,0). RectD.max
defines a size that
exactly covers the PolygonGrid
, translated to world coordinates.RectD
indicating the bounds of the PolygonGrid
in world coordinates,
given the current element()
, gridShift()
, and size()
public static boolean areCompatible(RegularPolygon element, PolygonGridShift gridShift)
RegularPolygon
is compatible
with the specified PolygonGridShift
for a PolygonGrid
.
element | gridShift |
---|---|
Square on Edge | PolygonGridShift.NONE |
Square on Vertex, Hexagon on Edge | PolygonGridShift.COLUMN_UP , PolygonGridShift.COLUMN_DOWN |
Square on Vertex, Hexagon on Vertex | PolygonGridShift.ROW_LEFT , PolygonGridShift.ROW_RIGHT |
element
- the RegularPolygon
to testgridShift
- the PolygonGridShift
to testtrue
if element
and gridShift
are compatible as the element()
and gridShift()
values of the same PolygonGrid
, else false
java.lang.IllegalArgumentException
- if element
is neither a square nor a hexagonjava.lang.NullPointerException
- if element
or gridShift
is null
public PolygonGrid asReadOnly()
PolygonGrid
.
Returns the current instance if isReadOnly
is already true
.
The read-only view is a PolygonGrid
whose isReadOnly
flag is true
and whose data is shared with the original instance. Any changes to the original instance
will be reflected by the read-only view, whereas attempting to modify the read-only view
throws an IllegalStateException
.
PolygonGrid
public boolean contains(int column, int row)
PolygonGrid
contains the specified column and row indices.column
- the zero-based index of a PolygonGrid
columnrow
- the zero-based index of a PolygonGrid
rowtrue
if the PolygonGrid
contains the location
at the specified column
and row
, else false
public boolean contains(RectI rect)
PolygonGrid
entirely contains the specified RectI
.rect
- the RectI
to examinetrue
if the PolygonGrid
contains all locations
within rect
, else false
public <T> T[][] createArray(java.lang.Class<T> clazz)
size()
as the PolygonGrid
.
Convenience wrapper for the reflection method Array.newInstance(java.lang.Class<?>, int)
.T
- the type of all array elementsclazz
- the Class
object for T (required for array creation)SizeI.width
and whose second dimension equals the SizeI.height
of size()
java.lang.IllegalArgumentException
- if clazz
is Void.TYPE
java.lang.NullPointerException
- if clazz
is null
public PointI[] getEdgeNeighborOffsets(PointI location)
edgeNeighborOffsets()
that matches the specified location.
Does not check whether location
is actually within the PolygonGrid
.
See edgeNeighborOffsets()
and neighborOffsets()
for a description
of the storage format used for neighbor coordinate offsets.
Note: For better performance, each PolygonGrid
instance directly returns its
own copy of this array, rather than making another copy on each getEdgeNeighborOffsets(org.kynosarges.tektosyne.geometry.PointI)
call. Do not change the array contents!
location
- the PointI
location to examineedgeNeighborOffsets()
that matches location
java.lang.NullPointerException
- if location
is null
public RectD getElementBounds(int column, int row)
element()
at the specified column and row indices.
Always returns a region within the current worldBounds()
if column
and
row
are within the PolygonGrid
, but does not check whether that is the case.column
- the zero-based index of a PolygonGrid
columnrow
- the zero-based index of a PolygonGrid
rowRectD
that circumscribes the element()
shape
at the specified column
and row
public RectD getElementBounds(PointI location)
element()
at the specified location.
Always returns a region within the current worldBounds()
if location
is within the PolygonGrid
, but does not check whether that is the case.public RectD getElementBounds(RectI region)
element()
shapes within the specified RectI
.
Always returns a region within the current worldBounds()
if region
is
fully within the PolygonGrid
, but does not check whether that is the case.region
- a RectI
comprising all locations to examineRectD
that circumscribes all element()
shapes within region
java.lang.IllegalArgumentException
- if region
has a zero RectI.width()
or RectI.height()
java.lang.NullPointerException
- if region
is null
public PointD[] getElementVertices(int column, int row)
element()
at the specified column and row indices.
Shifts all RegularPolygon.vertices
of the element()
by the result
of gridToWorld(int, int)
for the specified column
and row
.
The grid location is not checked against the bounds of the PolygonGrid
.column
- the zero-based index of a PolygonGrid
columnrow
- the zero-based index of a PolygonGrid
rowRegularPolygon.vertices
of the element()
shape
at the specified column
and row
public PointI getNeighbor(PointI location, int index)
location
or the returned coordinates are actually within
the PolygonGrid
. You must perform your own coordinate validation if desired.
The specified index
is taken Fortran.modulo(double, double)
the length of the inner
arrays within neighborOffsets()
, and may therefore be negative or greater than
the maximum index. See neighborOffsets()
for a description of the index order.
location
- the PointI
location whose neighbor to returnindex
- the zero-based index for the inner arrays within neighborOffsets()
indicating an edge or vertex of location
PointI
coordinates of the location that borders location
on the edge or vertex indicated by index
java.lang.NullPointerException
- if location
is null
public int getNeighborIndex(PointI location, PointI neighbor)
location
or neighbor
are actually within the
PolygonGrid
. You must perform your own coordinate validation if desired.
getNeighborIndex
is the inverse of getNeighbor(org.kynosarges.tektosyne.geometry.PointI, int)
. That is,
the following relations hold for all locations p with valid neighbors
q and neighbor indices i:
getNeighbor(p, getNeighborIndex(p, q)).equals(q);
getNeighborIndex(p, getNeighbor(p, i)) == i;
See neighborOffsets()
for a description of the index order.
location
- the PointI
location whose edge or vertex to returnneighbor
- a PointI
location neighboring location
neighborOffsets()
, indicating
the edge or vertex of location
on which it borders neighbor
java.lang.IllegalArgumentException
- if location
and neighbor
are not neighboring locations in the PolygonGrid
java.lang.NullPointerException
- if location
or neighbor
is null
public PointI[] getNeighborOffsets(PointI location)
neighborOffsets()
that matches the specified location.
Does not check whether location
is actually within the PolygonGrid
.
See neighborOffsets()
for a description of the storage format used for
neighbor coordinate offsets.location
- the PointI
location to examineneighborOffsets()
that matches location
java.lang.NullPointerException
- if location
is null
public int getStepDistance(PointI source, PointI target)
source
and target
are equal, and the minimum number of
location transitions required to move from source
to target
otherwise.
Does not check whether the PolygonGrid
actually contains source
and target
.
All distance calculations are O(1) operations, regardless of the concrete values of
source
and target
. The calculations for hexagon grids were adopted
from a Usenet post by Matthew V. Jessick.
public PointD gridToWorld(int column, int row)
worldBounds()
if the specified
indices are within the PolygonGrid
, but does not check whether that is the case.column
- the zero-based index of a PolygonGrid
columnrow
- the zero-based index of a PolygonGrid
rowPointD
world coordinates of the center of the element()
shape at the specified column
and row
in the PolygonGrid
public PointD gridToWorld(PointI location)
PointI
location to world coordinates.
Always returns coordinates within the current worldBounds()
if location
is within the PolygonGrid
, but does not check whether that is the case.location
- the PointI
location to convertPointD
world coordinates of the center of the element()
shape at the specified location
in the PolygonGrid
java.lang.NullPointerException
- if location
is null
public boolean isValid(int column, int row)
column
- the PolygonGrid
column index to examinerow
- the PolygonGrid
row index to examinetrue
if column
and row
are both equal to or greater than zero
and strictly less than the corresponding size()
dimension, else false
public boolean isValid(PointI location)
PointI
location is valid.
Always fails for INVALID_LOCATION
.location
- the PointI
location to examinetrue
if location
is not null
and isValid(int, int)
succeeds for its components, else false
public final void setElement(RegularPolygon element)
RegularPolygon
that constitutes a PolygonGrid
element.
Also resets gridShift()
to an appropriate default value if the current value
is incompatible with element
, as determined by areCompatible(org.kynosarges.tektosyne.geometry.RegularPolygon, org.kynosarges.tektosyne.geometry.PolygonGridShift)
.element
- the RegularPolygon
that constitutes a PolygonGrid
elementjava.lang.IllegalArgumentException
- if element
is neither a square nor a hexagonjava.lang.IllegalStateException
- if isReadOnly
is true
java.lang.NullPointerException
- if element
is null
public final void setGridShift(PolygonGridShift gridShift)
PolygonGridShift
value indicating how rows and columns are shifted.
See gridShift()
for default values depending on element()
.gridShift
- a PolygonGridShift
value indicating how rows and columns are shiftedjava.lang.IllegalArgumentException
- if gridShift
is incompatible with element()
java.lang.IllegalStateException
- if isReadOnly
is true
java.lang.NullPointerException
- if gridShift
is null
public final void setSize(SizeI size)
PolygonGrid
.size
- a SizeI
whose SizeI.height
indicates the number of rows
and whose SizeI.width
indicates the number of columnsjava.lang.IllegalArgumentException
- if any dimension of size
is less than onejava.lang.IllegalStateException
- if isReadOnly
is true
java.lang.NullPointerException
- if size
is null
public PointI worldToGrid(double x, double y)
PointI
location.
Returns coordinates between (0,0) and one less than the current size()
in either dimension if the specified world coordinates are within
worldBounds()
, and the constant value INVALID_LOCATION
otherwise.x
- the x-coordinate to converty
- the y-coordinate to convertPointI
location of the element()
whose shape contains
(x
,y
), if any, else INVALID_LOCATION
public PointI worldToGrid(PointD location)
PointD
world location to a PointI
location.
Returns coordinates between (0,0) and one less than the current size()
in
either dimension if the specified location
is within worldBounds()
,
and the constant value INVALID_LOCATION
otherwise.location
- the PointD
world location to convertPointI
location of the element()
whose shape contains
location
, if any, else INVALID_LOCATION
java.lang.NullPointerException
- if location
is null
public PointI worldToGridClipped(double x, double y)
PointI
location,
clipping to the nearest element()
if necessary.
Always returns coordinates between (0,0) and one less than the current
size()
in either dimension, regardless of whether the specified
world coordinates are within worldBounds()
.public PointI worldToGridClipped(PointD location)
PointD
world location to a PointI
location,
clipping to the nearest element()
if necessary.
Always returns coordinates between (0,0) and one less than the current size()
in
either dimension, regardless of whether location
is within worldBounds()
.public int connectivity()
Graph
node.
Returns the RegularPolygon.connectivity
of the current element()
.connectivity
in interface Graph<PointI>
Graph
nodepublic int nodeCount()
nodes()
in the Graph
.
Returns the product of SizeI.width
and SizeI.height
for the current size()
.public java.util.List<PointI> nodes()
public boolean contains(PointI node)
Graph
contains the specified node.
Returns the result of contains(int, int)
for the PointI.x
and PointI.y
coordinates of node
.public PointI findNearestNode(PointD location)
Graph
node nearest to the specified PointD
world location.
Returns the result of worldToGridClipped(PointD)
for location
.findNearestNode
in interface Graph<PointI>
location
- the PointD
location, in world coordinates, to examineGraph
node whose getWorldLocation(org.kynosarges.tektosyne.geometry.PointI)
result
is nearest to the specified location
java.lang.NullPointerException
- if location
is null
public double getDistance(PointI source, PointI target)
Graph
nodes.
Returns the result of getStepDistance(org.kynosarges.tektosyne.geometry.PointI, org.kynosarges.tektosyne.geometry.PointI)
for source
and target
,
which is always an Integer
value cast to Double
.getDistance
in interface Graph<PointI>
source
- the source node in the Graph
target
- the target node in the Graph
source
and target
java.lang.NullPointerException
- if source
or target
is null
public java.util.List<PointI> getNeighbors(PointI node)
Graph
node.
Returns an empty List
if node
or all its direct neighbors are not part
of the Graph
. Otherwise, calculates all direct neighbors by adding each element
in the appropriate neighborOffsets()
array to node
, omitting any
neighbors outside the Graph
. The resulting list is ordered clockwise.getNeighbors
in interface Graph<PointI>
node
- the Graph
node whose direct neighbors to collectList
of all Graph
nodes that are directly connected
with node
, numbering from zero to connectivity()
java.lang.NullPointerException
- if node
is null
public java.util.List<PointI> getNeighbors(PointI node, int steps)
Graph
node within the specified step distance.
Returns an empty List
if node
or all its direct neighbors are not
part of the Graph
. Otherwise, returns a List
ordered by increasing
x- and then y-coordinates unless steps
is one, in which case the result of
getNeighbors(PointI)
is returned.getNeighbors
in interface Graph<PointI>
node
- the Graph
node whose neighbors within steps
to collectsteps
- the distance around node
, in movement steps, in which
other nodes are considered neighbors of node
List
of all Graph
nodes whose step distance from
node
is greater than zero, but equal to or less than steps
java.lang.IllegalArgumentException
- if steps
is equal to or less than zerojava.lang.NullPointerException
- if node
is null
public PointD getWorldLocation(PointI node)
Graph
node.
Returns the result of gridToWorld(int, int)
for the
PointI.x
and PointI.y
coordinates of node
.getWorldLocation
in interface Graph<PointI>
node
- the Graph
node whose world location to findPointD
location of node
, in world coordinatesjava.lang.NullPointerException
- if node
is null
public PointD[] getWorldRegion(PointI node)
Graph
node.
Returns the result of getElementVertices(int, int)
for the PointI.x
and PointI.y
coordinates of node
.getWorldRegion
in interface Graph<PointI>
node
- the Graph
node whose world region to findPointD
vertices defining the polygonal region
covered by node
, in world coordinatesjava.lang.NullPointerException
- if node
is null