Module org.arakhne.afc.gis.giscore
Package org.arakhne.afc.gis.tree
Class MapPolylineTreeSet<P extends MapPolyline>
- java.lang.Object
-
- org.arakhne.afc.gis.tree.AbstractGISTreeSet<P,GISTreeSetNode<P>>
-
- org.arakhne.afc.gis.tree.StandardGISTreeSet<P>
-
- org.arakhne.afc.gis.tree.MapElementTreeSet<P>
-
- org.arakhne.afc.gis.tree.MapPolylineTreeSet<P>
-
- Type Parameters:
P
- is the type of the user data inside the node.
- All Implemented Interfaces:
Iterable<P>
,Collection<P>
,Set<P>
,GISElementSet<P>
,GISPolylineSet<P>
,GISSet<P>
,GISTreeSet<P,GISTreeSetNode<P>>
,GISTreeSetNodeFactory<P,GISTreeSetNode<P>>
public class MapPolylineTreeSet<P extends MapPolyline> extends MapElementTreeSet<P> implements GISPolylineSet<P>
This class describes a quad tree that contains map polylines and that permits to find them according to there geo-location.- Since:
- 14.0
- Version:
- 17.0 2020-01-04 14:41:53
- Author:
- Stéphane GALLAND
- See Also:
GISPrimitive
- Maven Group Id:
- org.arakhne.afc.gis
- Maven Artifact Id:
- giscore
-
-
Field Summary
-
Fields inherited from class org.arakhne.afc.gis.tree.AbstractGISTreeSet
worldBounds
-
-
Constructor Summary
Constructors Constructor Description MapPolylineTreeSet()
Create an empty tree.MapPolylineTreeSet(double boundsX, double boundsY, double boundsWidth, double boundsHeight)
Constructor.MapPolylineTreeSet(Rectangle2afp<?,?,?,?,?,?> bounds)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(P polyline, double precision, OutputParameter<P> firstNeighbour, OutputParameter<P> secondNeighbour)
Add the selected polyline inside the tree and replies the two nearest polylines that are already inside the tree.P
getNearestEnd(double x, double y)
Replies the object that has the nearest end to the specified point.P
getNearestEnd(Point2D<?,?> position)
Replies the object that has the nearest end to the specified point.-
Methods inherited from class org.arakhne.afc.gis.tree.MapElementTreeSet
getNearest, getNearest, getNearestData, getNearestData
-
Methods inherited from class org.arakhne.afc.gis.tree.StandardGISTreeSet
add, getNodeFactory, newNode, newRootNode, newRootNode, setNodeFactory
-
Methods inherited from class org.arakhne.afc.gis.tree.AbstractGISTreeSet
addAll, boundsIterator, clear, computeSize, contains, containsAll, extractClassFrom, get, get, get, getElementType, getTree, getTreeNodeAt, indexOf, isEmpty, isTypeRecomputedAfterRemoval, iterator, iterator, iterator, nodeIterator, remove, removeAll, retainAll, setTypeRecomputedAfterRemoval, size, slowContains, toArray, toArray, toIterable, toIterable, toString, updateComponentType, updateComponentType
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface java.util.Collection
parallelStream, removeIf, stream, toArray
-
Methods inherited from interface org.arakhne.afc.gis.GISElementSet
getNearest, getNearest, getNearestData, getNearestData
-
Methods inherited from interface org.arakhne.afc.gis.GISSet
boundsIterator, computeSize, get, get, get, getElementType, indexOf, isTypeRecomputedAfterRemoval, iterator, iterator, setTypeRecomputedAfterRemoval, slowContains, toIterable, toIterable
-
-
-
-
Constructor Detail
-
MapPolylineTreeSet
public MapPolylineTreeSet()
Create an empty tree.
-
MapPolylineTreeSet
public MapPolylineTreeSet(double boundsX, double boundsY, double boundsWidth, double boundsHeight)
Constructor.- Parameters:
boundsX
- is the bounds of the scene.boundsY
- is the bounds of the scene.boundsWidth
- is the bounds of the scene.boundsHeight
- is the bounds of the scene.
-
MapPolylineTreeSet
public MapPolylineTreeSet(Rectangle2afp<?,?,?,?,?,?> bounds)
Constructor.- Parameters:
bounds
- are the bounds of the scene stored inside this tree.
-
-
Method Detail
-
add
public boolean add(P polyline, double precision, OutputParameter<P> firstNeighbour, OutputParameter<P> secondNeighbour)
Description copied from interface:GISPolylineSet
Add the selected polyline inside the tree and replies the two nearest polylines that are already inside the tree.- Specified by:
add
in interfaceGISPolylineSet<P extends MapPolyline>
- Parameters:
polyline
- is the polyline to addprecision
- is the precision (in meters) used to detect the neighbours.firstNeighbour
- is one of the two nearest polylines that could be connected to the new segment.secondNeighbour
- is one of the two nearest polylines that could be connected to the new segment.- Returns:
true
if successfully added,false
otherwise
-
getNearestEnd
@Pure public final P getNearestEnd(Point2D<?,?> position)
Replies the object that has the nearest end to the specified point. The nearest neighbor (NN) algorithm, to find the NN to a given target point not in the tree, relies on the ability to discard large portions of the tree by performing a simple test. To perform the NN calculation, the tree is searched in a depth-first fashion, refining the nearest distance. First the root node is examined with an initial assumption that the smallest distance to the next point is infinite. The subdomain (right or left), which is a hyperrectangle, containing the target point is searched. This is done recursively until a final minimum region containing the node is found. The algorithm then (through recursion) examines each parent node, seeing if it is possible for the other domain to contain a point that is closer. This is performed by testing for the possibility of intersection between the hyperrectangle and the hypersphere (formed by target node and current minimum radius). If the rectangle that has not been recursively examined yet does not intersect this sphere, then there is no way that the rectangle can contain a point that is a better nearest neighbour. This is repeated until all domains are either searched or discarded, thus leaving the nearest neighbour as the final result. In addition to this one also has the distance to the nearest neighbour on hand as well. Finding the nearest point is an O(logN) operation.- Specified by:
getNearestEnd
in interfaceGISPolylineSet<P extends MapPolyline>
- Parameters:
position
- is the position from which the nearest primitive must be replied.- Returns:
- the nearest element or
null
if none. - See Also:
GISPolylineSet.getNearestEnd(double, double)
-
getNearestEnd
@Pure public P getNearestEnd(double x, double y)
Replies the object that has the nearest end to the specified point. The nearest neighbor (NN) algorithm, to find the NN to a given target point not in the tree, relies on the ability to discard large portions of the tree by performing a simple test. To perform the NN calculation, the tree is searched in a depth-first fashion, refining the nearest distance. First the root node is examined with an initial assumption that the smallest distance to the next point is infinite. The subdomain (right or left), which is a hyperrectangle, containing the target point is searched. This is done recursively until a final minimum region containing the node is found. The algorithm then (through recursion) examines each parent node, seeing if it is possible for the other domain to contain a point that is closer. This is performed by testing for the possibility of intersection between the hyperrectangle and the hypersphere (formed by target node and current minimum radius). If the rectangle that has not been recursively examined yet does not intersect this sphere, then there is no way that the rectangle can contain a point that is a better nearest neighbour. This is repeated until all domains are either searched or discarded, thus leaving the nearest neighbour as the final result. In addition to this one also has the distance to the nearest neighbour on hand as well. Finding the nearest point is an O(logN) operation.- Specified by:
getNearestEnd
in interfaceGISPolylineSet<P extends MapPolyline>
- Parameters:
x
- is the position from which the nearest primitive must be replied.y
- is the position from which the nearest primitive must be replied.- Returns:
- the nearest element or
null
if none.
-
-