sim.field.continuous
Class Continuous3D

java.lang.Object
  extended bysim.field.SparseField
      extended bysim.field.continuous.Continuous3D
All Implemented Interfaces:
java.io.Serializable

public class Continuous3D
extends SparseField

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 getObjectsWithinDistance(...)), 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 getObjectsWithinDistance(...), 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 getObjectsWithinDistance() 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.

Warning about getObjectsAtLocation() and numObjectsAtLocation() Because this class uses its superclass (the SparseField) to store the discretized region, getObjectsAtLocation(...) and numObjectsAtLocation(...) will not work as you might expect. The Sparse Field is storing Int3Ds (the discretized grid locations), not Double3Ds. While you could get all the objects in the same discretization cell as a given Double3D location with getObjectsAtLocation(discretize(theDouble3D)), almost certainly you're going to retain sanity better by using the neighborhood functions (getObjectsWithinDistance(...)). The same goes for getObjectsAtLocationOfObject() and numObjectsAtLocationOfObject().

See Also:
Serialized Form

Nested Class Summary
 
Nested classes inherited from class sim.field.SparseField
SparseField.LocationAndIndex
 
Field Summary
 double discretization
           
 java.util.HashMap doubleLocationHash
          Where we store the Double3D values hashed by object
 double height
           
 double length
           
 double width
           
 
Fields inherited from class sim.field.SparseField
allObjects, INITIAL_BAG_SIZE, LARGE_BAG_RATIO, locationAndIndexHash, MIN_BAG_SIZE, objectHash, removeEmptyBags, replaceLargeBags, REPLACEMENT_BAG_RATIO
 
Constructor Summary
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)
           
 double getHeight()
          Get the height
 double getLength()
          Get the height
 Double3D getObjectLocation(java.lang.Object obj)
           
 Bag getObjectsWithinDistance(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 getObjectsWithinDistance(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 getObjectsWithinDistance(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 getObjectsWithinDistance(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.
 double getWidth()
          Get the width
 java.lang.Object remove(java.lang.Object obj)
          Removes an object if it exists.
 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 distance between two values in the X dimension.
 double tdy(double y1, double y2)
          Minimum toroidal distance between two values in the Y dimension.
 double tdz(double z1, double z2)
          Minimum toroidal distance 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
exists, getAllObjects, getObjectIndex, getObjectsAtLocation, getObjectsAtLocationOfObject, getObjectsAtLocations, getRawObjectLocation, iterator, locationBagIterator, numObjectsAtLocation, numObjectsAtLocationOfObject, removeObjectsAtLocation, setObjectLocation
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

doubleLocationHash

public java.util.HashMap doubleLocationHash
Where we store the Double3D values hashed by object


width

public double width

height

public double height

length

public double length

discretization

public final double discretization
Constructor Detail

Continuous3D

public Continuous3D(double discretization,
                    double width,
                    double height,
                    double length)
Provide expected bounds on the SparseContinuous3D

Method Detail

getObjectLocation

public final Double3D getObjectLocation(java.lang.Object obj)

discretize

public final Int3D discretize(Double3D location)

setObjectLocation

public final boolean setObjectLocation(java.lang.Object obj,
                                       Double3D location)

clear

public final Bag clear()
Description copied from class: SparseField
Deletes everything, returning all the objects as a Bag (which you can freely use and modify). If you need the Bag, then this is a useful method -- otherwise it might in fact be faster to just make a brand new Sparse Field and let the garbage collector do its magic.

Overrides:
clear in class SparseField

remove

public final java.lang.Object remove(java.lang.Object obj)
Description copied from class: SparseField
Removes an object if it exists. Returns its location, or null if the object didn't exist.

Overrides:
remove in class SparseField

getWidth

public double getWidth()
Get the width


getHeight

public double getHeight()
Get the height


getLength

public double getLength()
Get the height


tx

public final double tx(double x)
Toroidal x


ty

public final double ty(double y)
Toroidal y


tz

public final double tz(double z)
Toroidal z


stx

public double stx(double x)
Simple [and fast] toroidal x. Use this if the values you'd pass in never stray beyond (-width ... width * 2) not inclusive. It's a bit faster than the full toroidal computation as it uses if statements rather than two modulos. The following definition:
{ double width = this.width; if (x >= 0) { if (x < width) return x; return x - width; } return x + width; }
...produces the shortest code (24 bytes) and is inlined in Hotspot for 1.4.1. However removing the double width = this.width; is likely to be a little faster if most objects are within the toroidal region.


sty

public double sty(double y)
Simple [and fast] toroidal y. Use this if the values you'd pass in never stray beyond (-height ... height * 2) not inclusive. It's a bit faster than the full toroidal computation as it uses if statements rather than two modulos. The following definition:
{ double height = this.height; if (y >= 0) { if (y < height) return y ; return y - height; } return y + height; }
...produces the shortest code (24 bytes) and is inlined in Hotspot for 1.4.1. However removing the double height = this.height; is likely to be a little faster if most objects are within the toroidal region.


stz

public double stz(double z)
Simple [and fast] toroidal z. Use this if the values you'd pass in never stray beyond (-length ... length * 2) not inclusive. It's a bit faster than the full toroidal computation as it uses if statements rather than two modulos. The following definition:
{ double length = this.length; if (z >= 0) { if (z < length) return z ; return z - length; } return z + length; }
...produces the shortest code (24 bytes) and is inlined in Hotspot for 1.4.1. However removing the double length = this.length; is likely to be a little faster if most objects are within the toroidal region.


tdx

public double tdx(double x1,
                  double x2)
Minimum toroidal distance between two values in the X dimension.


tdy

public double tdy(double y1,
                  double y2)
Minimum toroidal distance between two values in the Y dimension.


tdz

public double tdz(double z1,
                  double z2)
Minimum toroidal distance between two values in the Z dimension.


tds

public double tds(Double3D d1,
                  Double3D d2)
Minimum Toroidal Distance Squared between two points. This computes the "shortest" (squared) distance between two points, considering wrap-around possibilities as well.


tv

public Double3D tv(Double3D d1,
                   Double3D d2)
Minimum Toroidal difference vector between two points. This subtracts the second point from the first and produces the minimum-length such subtractive vector, considering wrap-around possibilities as well


getObjectsWithinDistance

public Bag getObjectsWithinDistance(Double3D position,
                                    double distance)
Returns a bag containing AT LEAST those objects within the bounding box surrounding the specified distance of the specified position. The bag could include other objects than this. In this case we include the object if any part of the bounding box could overlap into the desired region. To do this, if nonPointObjects is true, we extend the search space by one extra discretization in all directions. For small distances within a single bucket, this returns 27 bucket's worth rather than 1 (!!!), so if you know you only care about the actual x/y/z points stored, rather than possible object overlap into the distance sphere you specified, you'd want to set nonPointObjects to FALSE. That's a lot of extra hash table lookups. [assumes non-toroidal, point objects]


getObjectsWithinDistance

public Bag getObjectsWithinDistance(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. The bag could include other objects than this. If toroidal, then wrap-around possibilities are also considered. In this case we include the object if any part of the bounding box could overlap into the desired region. To do this, if nonPointObjects is true, we extend the search space by one extra discretization in all directions. For small distances within a single bucket, this returns 27 bucket's worth rather than 1 (!!!), so if you know you only care about the actual x/y/z points stored, rather than possible object overlap into the distance sphere you specified, you'd want to set nonPointObjects to FALSE. That's a lot of extra hash table lookups. [assumes point objects]


getObjectsWithinDistance

public Bag getObjectsWithinDistance(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. The bag could include other objects than this. If toroidal, then wrap-around possibilities are also considered. If nonPointObjects, then it is presumed that the object isn't just a point in space, but in fact fills an area in space where the x/y point location could be at the extreme corner of a bounding box of the object. In this case we include the object if any part of the bounding box could overlap into the desired region. To do this, if nonPointObjects is true, we extend the search space by one extra discretization in all directions. For small distances within a single bucket, this returns 27 bucket's worth rather than 1 (!!!), so if you know you only care about the actual x/y/z points stored, rather than possible object overlap into the distance sphere you specified, you'd want to set nonPointObjects to FALSE. That's a lot of extra hash table lookups.


getObjectsWithinDistance

public Bag getObjectsWithinDistance(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. The bag could include other objects than this. If toroidal, then wrap-around possibilities are also considered. If nonPointObjects, then it is presumed that the object isn't just a point in space, but in fact fills an area in space where the x/y point location could be at the extreme corner of a bounding box of the object. In this case we include the object if any part of the bounding box could overlap into the desired region. To do this, if nonPointObjects is true, we extend the search space by one extra discretization in all directions. For small distances within a single bucket, this returns 27 bucket's worth rather than 1 (!!!), so if you know you only care about the actual x/y/z points stored, rather than possible object overlap into the distance sphere you specified, you'd want to set nonPointObjects to FALSE. That's a lot of extra hash table lookups.