|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectsim.field.SparseField
sim.field.continuous.Continuous3D
public class Continuous3D
A storage facility for objects located in a continuous 3D environment. This facility relates objects with 3D double tuples (in the form of Double3D). The facility extends SparseField, and like other objects which extend SparseField (such as SparseGrid3D), the facility can only relate any given object with a single location at a time -- that is, an object cannot hold two locations at once in the Continuous3D field.
Because hashtable lookups are more expensive than just storing the object, we suggest that you ALSO store the location of an object in the object itself, so you can read from the object rather than having to call getObjectLocation(object).
The Continuous3D has been arranged to make neighborhood lookup information efficient. It discretizes the space into grid buckets. The discretization size of the buckets is provided in the constructor and cannot be changed thereafter. If the discretization was 0.7, for example, then one bucket would be (0,0,0) to (under 0.7, under 0.7, under 0.7), another bucket would be (0,0,0.0,0.7) to (under 0.7, under 0.7, under 1.4), etc.
You can use Continuous3D to look up objects in a given region by asking for objects within the enclosing buckets, then rummaging through the buckets to find the individuals actually in the desired region. The trick here is to come up with a good bucket size. If the bucket size is much larger than the typical size of a neighborhood lookup, then a typical lookup will include large numbers of objects you don't care about; in the worst case, this is an O(n) lookup for something that could have been much smaller. On the other hand, if the bucket size is much smaller than the typical size of a neighborhood lookup, then you have to do lots of bucket lookups to cover your range; many if not most of these buckets could be empty. This can also be highly inefficient.
If your objects are point objects, you have no minimum bound on the discretization size. But if the object are non-point location objects (that is, they have dimensions of width, height, etc.), and you care about this overlap when you do distance lookups, then you have a minimum bound on your discretization. In this case, you want to make certain that your discretization is at LEAST larger than the LARGEST dimension of any object you plan on putting in the Continuous3D. The idea here is that if an any part of an object fell within the bounding box for your distance lookup task (see getNeighborsWithinDistance(...)), you're guaranteed that the stored location of the object must be within a bounding box 1 discretization larger in each direction.
Okay, so that gives you the minimum discretization you should use. What about the maximum discretization? It depends largely on the number of objects expected to occupy a given discretized bucket region, and on what kind of lookups you need to do for objects within a given distance. Searching through one bucket is a hash table lookup. A smaller discretization returns a more accurate sample of objects within the requested bounding box, but requires more hash table lookups. If you have point location objects, and your field is very dense (LOTS of objects in a bucket on average), then we recommend a discretization equal to the maximum range distance you are likely to look up; but if your field is very sparse, then we recommend a discretization equal to twice the maximum range distance. You have to tune it. If you have non-point-location objects, then you have two choices. One approach is to assume a discretization equal to the maximum range distance, but when doing lookups with getNeighborsWithinDistance(...), you need to state that you're using non-point-location objects. If you're fairly sparse and your objects aren't big, you can set the discretization to twice the maximum range distance, and you should be safe calling getNeighborsWithinDistance() pretending that your objects are point-location; this saves you a lot of hash table lookups.
At any rate, do NOT go below the minimum discretization rules.
But wait, you say, I have objects of widely varying sizes. Or I have many different neighborhood lookup range needs. Never fear. Just use multiple Continuous3Ds of different discretizations. Depending on your needs, you can put all the objects in all of the Continuous3Ds (making different range lookups efficient) or various-sized classes of objects in their own Continuous3Ds perhaps. You have to think this through based on your needs. If all the objects were in all of the Continuous3Ds, you'd think that'd be inefficient in moving objects around. Not really: if the discretizations doubled (or more) each time, you're looking at typically an O(ln n) number of Continuous3Ds, and a corresponding number of lookups.
Continuous3D objects have a width and a height, but this is only used in computing toroidal (wrap-around) situations. If you don't care about toroidal features, then you can completely disregard the width and height.
Nested Class Summary |
---|
Nested classes/interfaces inherited from class sim.field.SparseField |
---|
SparseField.LocationAndIndex |
Field Summary | |
---|---|
double |
discretization
|
java.util.Map |
doubleLocationHash
Where we store the Double3D values hashed by object |
double |
height
|
double |
length
|
double |
width
|
Fields inherited from class sim.field.SparseField |
---|
allObjects, ANY_SIZE, INITIAL_BAG_SIZE, LARGE_BAG_RATIO, locationAndIndexHash, MIN_BAG_SIZE, objectHash, removeEmptyBags, replaceLargeBags, REPLACEMENT_BAG_RATIO |
Constructor Summary | |
---|---|
Continuous3D(Continuous3D other)
|
|
Continuous3D(double discretization,
double width,
double height,
double length)
Provide expected bounds on the SparseContinuous3D |
Method Summary | |
---|---|
Bag |
clear()
Deletes everything, returning all the objects as a Bag (which you can freely use and modify). |
Int3D |
discretize(Double3D location)
Discretizes the location according to the internal discretization of the Continuous3D. |
Int3D |
discretize(Double3D location,
int discretization)
Discretizes the location according to the provided discretization, which may or may not be the discretization used internally by the Continuous3D. |
Double3D |
getDimensions()
Returns the width and height of the sparse field as a Double3D |
double |
getHeight()
Get the height |
double |
getLength()
Get the height |
Bag |
getNeighborsExactlyWithinDistance(Double3D position,
double distance)
Returns a Bag containing EXACTLY those objects within a certain distance of a given position, or equal to that distance, measuring using a circle of radius 'distance' around the given position. |
Bag |
getNeighborsExactlyWithinDistance(Double3D position,
double distance,
boolean toroidal)
Returns a Bag containing EXACTLY those objects within a certain distance of a given position, or equal to that distance, measuring using a circle of radius 'distance' around the given position. |
Bag |
getNeighborsExactlyWithinDistance(Double3D position,
double distance,
boolean toroidal,
boolean radial,
boolean inclusive,
Bag result)
Returns a Bag containing EXACTLY those objects within a certain distance of a given position. |
Bag |
getNeighborsWithinDistance(Double3D position,
double distance)
Returns a bag containing AT LEAST those objects within the bounding box surrounding the specified distance of the specified position. |
Bag |
getNeighborsWithinDistance(Double3D position,
double distance,
boolean toroidal)
Returns a bag containing AT LEAST those objects within the bounding box surrounding the specified distance of the specified position. |
Bag |
getNeighborsWithinDistance(Double3D position,
double distance,
boolean toroidal,
boolean nonPointObjects)
Returns a bag containing AT LEAST those objects within the bounding box surrounding the specified distance of the specified position. |
Bag |
getNeighborsWithinDistance(Double3D position,
double distance,
boolean toroidal,
boolean nonPointObjects,
Bag result)
Puts into the result Bag (and returns it) AT LEAST those objects within the bounding box surrounding the specified distance of the specified position. |
Double3D |
getObjectLocation(java.lang.Object obj)
|
Double3D |
getObjectLocationAsDouble3D(java.lang.Object obj)
Returns the object location as a Double3D, or as null if there is no such object. |
Bag |
getObjectsAtDiscretizedLocation(Int3D location)
Returns a bag containing all the objects at a given discretized location, or null when there are no objects at the location. |
Bag |
getObjectsAtLocation(Double3D location)
Returns a bag containing all the objects at a given location, or null if there are no such objects or if location is null. |
Bag |
getObjectsAtLocationOfObject(java.lang.Object obj)
Returns a bag containing all the objects at the exact same location as a given object, including the object itself, or null if the object is not in the Field. |
Bag |
getObjectsExactlyWithinDistance(Double3D position,
double distance)
Deprecated. |
Bag |
getObjectsExactlyWithinDistance(Double3D position,
double distance,
boolean toroidal)
Deprecated. |
Bag |
getObjectsExactlyWithinDistance(Double3D position,
double distance,
boolean toroidal,
boolean radial,
boolean inclusive,
Bag result)
Deprecated. |
Bag |
getObjectsWithinDistance(Double3D position,
double distance)
Deprecated. |
Bag |
getObjectsWithinDistance(Double3D position,
double distance,
boolean toroidal)
Deprecated. |
Bag |
getObjectsWithinDistance(Double3D position,
double distance,
boolean toroidal,
boolean nonPointObjects)
Deprecated. |
Bag |
getObjectsWithinDistance(Double3D position,
double distance,
boolean toroidal,
boolean nonPointObjects,
Bag result)
Deprecated. |
double |
getWidth()
Get the width |
int |
numObjectsAtLocation(Double3D location)
Returns the number of the objects at a given location, or 0 if there are no such objects or if location is null. |
int |
numObjectsAtLocationOfObject(java.lang.Object obj)
Returns the number of objects at the exact same location as a given object, including the object itself, or 0 if the object is not in the Field. |
java.lang.Object |
remove(java.lang.Object obj)
Removes an object if it exists. |
Bag |
removeObjectsAtLocation(Double3D location)
Removes objects at exactly the given location, and returns a bag of them, or null of no objects are at that location. |
boolean |
setObjectLocation(java.lang.Object obj,
Double3D location)
|
double |
stx(double x)
Simple [and fast] toroidal x. |
double |
sty(double y)
Simple [and fast] toroidal y. |
double |
stz(double z)
Simple [and fast] toroidal z. |
double |
tds(Double3D d1,
Double3D d2)
Minimum Toroidal Distance Squared between two points. |
double |
tdx(double x1,
double x2)
Minimum toroidal difference between two values in the X dimension. |
double |
tdy(double y1,
double y2)
Minimum toroidal difference between two values in the Y dimension. |
double |
tdz(double z1,
double z2)
Minimum toroidal difference between two values in the Z dimension. |
Double3D |
tv(Double3D d1,
Double3D d2)
Minimum Toroidal difference vector between two points. |
double |
tx(double x)
Toroidal x |
double |
ty(double y)
Toroidal y |
double |
tz(double z)
Toroidal z |
Methods inherited from class sim.field.SparseField |
---|
buildMap, buildMap, exists, getAllObjects, getObjectIndex, getObjectsAtLocation, getObjectsAtLocations, getRawObjectLocation, getRawObjectsAtLocation, iterator, locationBagIterator, numObjectsAtLocation, removeObjectsAtLocation, setObjectLocation, size |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
public java.util.Map doubleLocationHash
public double width
public double height
public double length
public final double discretization
Constructor Detail |
---|
public Continuous3D(double discretization, double width, double height, double length)
public Continuous3D(Continuous3D other)
Method Detail |
---|
public final Double3D getObjectLocation(java.lang.Object obj)
public final Int3D discretize(Double3D location)
public final Int3D discretize(Double3D location, int discretization)
public final boolean setObjectLocation(java.lang.Object obj, Double3D location)
public final Bag clear()
SparseField
clear
in class SparseField
public final java.lang.Object remove(java.lang.Object obj)
SparseField
remove
in class SparseField
public double getWidth()
public double getHeight()
public double getLength()
public final double tx(double x)
public final double ty(double y)
public final double tz(double z)
public double stx(double x)
public double sty(double y)
public double stz(double z)
public double tdx(double x1, double x2)
public double tdy(double y1, double y2)
public double tdz(double z1, double z2)
public double tds(Double3D d1, Double3D d2)
public Double3D tv(Double3D d1, Double3D d2)
public Bag getObjectsExactlyWithinDistance(Double3D position, double distance)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getObjectsExactlyWithinDistance(Double3D position, double distance, boolean toroidal)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getObjectsExactlyWithinDistance(Double3D position, double distance, boolean toroidal, boolean radial, boolean inclusive, Bag result)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getNeighborsExactlyWithinDistance(Double3D position, double distance)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getNeighborsExactlyWithinDistance(Double3D position, double distance, boolean toroidal)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getNeighborsExactlyWithinDistance(Double3D position, double distance, boolean toroidal, boolean radial, boolean inclusive, Bag result)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getObjectsWithinDistance(Double3D position, double distance)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getObjectsWithinDistance(Double3D position, double distance, boolean toroidal)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getObjectsWithinDistance(Double3D position, double distance, boolean toroidal, boolean nonPointObjects)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getObjectsWithinDistance(Double3D position, double distance, boolean toroidal, boolean nonPointObjects, Bag result)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getNeighborsWithinDistance(Double3D position, double distance)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getNeighborsWithinDistance(Double3D position, double distance, boolean toroidal)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getNeighborsWithinDistance(Double3D position, double distance, boolean toroidal, boolean nonPointObjects)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getNeighborsWithinDistance(Double3D position, double distance, boolean toroidal, boolean nonPointObjects, Bag result)
Note: if the field is toroidal, and position is outside the boundaries, it will be wrapped to within the boundaries before computation.
public Bag getObjectsAtDiscretizedLocation(Int3D location)
public Bag getObjectsAtLocation(Double3D location)
public int numObjectsAtLocation(Double3D location)
public Bag getObjectsAtLocationOfObject(java.lang.Object obj)
getObjectsAtLocationOfObject
in class SparseField
public int numObjectsAtLocationOfObject(java.lang.Object obj)
numObjectsAtLocationOfObject
in class SparseField
public Bag removeObjectsAtLocation(Double3D location)
public final Double3D getDimensions()
SparseField3D
getDimensions
in interface SparseField3D
public Double3D getObjectLocationAsDouble3D(java.lang.Object obj)
getObjectLocationAsDouble3D
in interface SparseField3D
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |