|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.vividsolutions.jts.index.chain.MonotoneChain
public class MonotoneChain
Monotone Chains are a way of partitioning the segments of a linestring to allow for fast searching of intersections. They have the following properties:
Property 2 allows an efficient binary search to be used to find the intersection points of two monotone chains. For many types of real-world data, these properties eliminate a large number of segment comparisons, producing substantial speed gains.
One of the goals of this implementation of MonotoneChains is to be as space and time efficient as possible. One design choice that aids this is that a MonotoneChain is based on a subarray of a list of points. This means that new arrays of points (potentially very large) do not have to be allocated.
MonotoneChains support the following kinds of queries:
Constructor Summary | |
---|---|
MonotoneChain(Coordinate[] pts,
int start,
int end,
java.lang.Object context)
|
Method Summary | |
---|---|
void |
computeOverlaps(MonotoneChain mc,
MonotoneChainOverlapAction mco)
|
java.lang.Object |
getContext()
|
Coordinate[] |
getCoordinates()
Return the subsequence of coordinates forming this chain. |
int |
getEndIndex()
|
Envelope |
getEnvelope()
|
int |
getId()
|
void |
getLineSegment(int index,
LineSegment ls)
|
int |
getStartIndex()
|
void |
select(Envelope searchEnv,
MonotoneChainSelectAction mcs)
Determine all the line segments in the chain whose envelopes overlap the searchEnvelope, and process them |
void |
setId(int id)
|
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public MonotoneChain(Coordinate[] pts, int start, int end, java.lang.Object context)
Method Detail |
---|
public void setId(int id)
public int getId()
public java.lang.Object getContext()
public Envelope getEnvelope()
public int getStartIndex()
public int getEndIndex()
public void getLineSegment(int index, LineSegment ls)
public Coordinate[] getCoordinates()
public void select(Envelope searchEnv, MonotoneChainSelectAction mcs)
public void computeOverlaps(MonotoneChain mc, MonotoneChainOverlapAction mco)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |