File Coverage

/usr/local/lib/perl5/site_perl/5.26.1/x86_64-linux/CPP/geos.x/i/geos/index/chain/MonotoneChain.h
Criterion Covered Total %
statement 4 4 100.0
branch n/a
condition n/a
subroutine n/a
pod n/a
total 4 4 100.0


line stmt bran cond sub pod time code
1             /**********************************************************************
2             *
3             * GEOS - Geometry Engine Open Source
4             * http://geos.osgeo.org
5             *
6             * Copyright (C) 2001-2002 Vivid Solutions Inc.
7             *
8             * This is free software; you can redistribute and/or modify it under
9             * the terms of the GNU Lesser General Public Licence as published
10             * by the Free Software Foundation.
11             * See the COPYING file for more information.
12             *
13             **********************************************************************
14             *
15             * Last port: index/chain/MonotoneChain.java rev. 1.15 (JTS-1.10)
16             *
17             **********************************************************************/
18              
19             #ifndef GEOS_IDX_CHAIN_MONOTONECHAIN_H
20             #define GEOS_IDX_CHAIN_MONOTONECHAIN_H
21              
22             #include
23             #include // for inline
24              
25             #include // for unique_ptr
26              
27             // Forward declarations
28             namespace geos {
29             namespace geom {
30             class Envelope;
31             class LineSegment;
32             class CoordinateSequence;
33             }
34             namespace index {
35             namespace chain {
36             class MonotoneChainSelectAction;
37             class MonotoneChainOverlapAction;
38             }
39             }
40             }
41              
42             namespace geos {
43             namespace index { // geos::index
44             namespace chain { // geos::index::chain
45              
46             /** \brief
47             * Monotone Chains are a way of partitioning the segments of a linestring to
48             * allow for fast searching of intersections.
49             *
50             * They have the following properties:
51             *
52             * - the segments within a monotone chain never intersect each other
53             * - the envelope of any contiguous subset of the segments in a monotone
54             * chain is equal to the envelope of the endpoints of the subset.
55             *
56             * Property 1 means that there is no need to test pairs of segments from
57             * within the same monotone chain for intersection.
58             * Property 2 allows an efficient binary search to be used to find the
59             * intersection points of two monotone chains.
60             *
61             * For many types of real-world data, these properties eliminate
62             * a large number of segment comparisons, producing substantial speed gains.
63             *
64             * One of the goals of this implementation of MonotoneChains is to be
65             * as space and time efficient as possible. One design choice that aids this
66             * is that a MonotoneChain is based on a subarray of a list of points.
67             * This means that new arrays of points (potentially very large) do not
68             * have to be allocated.
69             *
70             * MonotoneChains support the following kinds of queries:
71             *
72             * - Envelope select: determine all the segments in the chain which
73             * intersect a given envelope
74             * - Overlap: determine all the pairs of segments in two chains whose
75             * envelopes overlap
76             *
77             * This implementation of MonotoneChains uses the concept of internal iterators
78             * to return the resultsets for the above queries.
79             * This has time and space advantages, since it
80             * is not necessary to build lists of instantiated objects to represent the segments
81             * returned by the query.
82             * However, it does mean that the queries are not thread-safe.
83             *
84             */
85             class GEOS_DLL MonotoneChain
86             {
87             public:
88              
89             /// @param pts
90             /// Ownership left to caller, this class holds a reference.
91             ///
92             /// @param start
93             ///
94             /// @param end
95             ///
96             /// @param context
97             /// Ownership left to caller, this class holds a reference.
98             ///
99             MonotoneChain(const geom::CoordinateSequence& pts,
100             std::size_t start, std::size_t end, void* context);
101              
102             ~MonotoneChain();
103              
104             /// Returned envelope is owned by this class
105             const geom::Envelope& getEnvelope() const;
106              
107 2           size_t getStartIndex() const { return start; }
108              
109 2           size_t getEndIndex() const { return end; }
110              
111             /** \brief
112             * Set given LineSegment with points of the segment starting
113             * at the given index.
114             */
115             void getLineSegment(std::size_t index, geom::LineSegment& ls) const;
116              
117             /**
118             * Return the subsequence of coordinates forming this chain.
119             * Allocates a new CoordinateSequence to hold the Coordinates
120             *
121             */
122             std::unique_ptr getCoordinates() const;
123              
124             /**
125             * Determine all the line segments in the chain whose envelopes overlap
126             * the searchEnvelope, and process them
127             */
128             void select(const geom::Envelope& searchEnv,
129             MonotoneChainSelectAction& mcs);
130              
131             void computeOverlaps(MonotoneChain *mc,
132             MonotoneChainOverlapAction *mco);
133              
134 1           void setId(int nId) { id=nId; }
135              
136 2           inline int getId() const { return id; }
137              
138             void* getContext() { return context; }
139              
140             private:
141              
142             void computeSelect(const geom::Envelope& searchEnv,
143             size_t start0,
144             size_t end0,
145             MonotoneChainSelectAction& mcs);
146              
147             void computeOverlaps(std::size_t start0, std::size_t end0, MonotoneChain& mc,
148             std::size_t start1, std::size_t end1,
149             MonotoneChainOverlapAction& mco);
150              
151             /// Externally owned
152             const geom::CoordinateSequence& pts;
153              
154             /// Owned by this class, lazely created
155             mutable geom::Envelope* env;
156              
157             /// user-defined information
158             void* context;
159              
160             /// Index of chain start vertex into the CoordinateSequence, 0 based.
161             size_t start;
162              
163             /// Index of chain end vertex into the CoordinateSequence, 0 based.
164             size_t end;
165              
166             /// useful for optimizing chain comparisons
167             int id;
168              
169             // Declare type as noncopyable
170             MonotoneChain(const MonotoneChain& other) = delete;
171             MonotoneChain& operator=(const MonotoneChain& rhs) = delete;
172             };
173              
174             } // namespace geos::index::chain
175             } // namespace geos::index
176             } // namespace geos
177              
178             #endif // GEOS_IDX_CHAIN_MONOTONECHAIN_H
179