GEOS  3.13.0dev
MonotoneChainEdge.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2005-2006 Refractions Research Inc.
7  * Copyright (C) 2001-2002 Vivid Solutions Inc.
8  *
9  * This is free software; you can redistribute and/or modify it under
10  * the terms of the GNU Lesser General Public Licence as published
11  * by the Free Software Foundation.
12  * See the COPYING file for more information.
13  *
14  **********************************************************************/
15 
16 #pragma once
17 
18 #include <geos/export.h>
19 #include <geos/geom/Envelope.h> // for composition
20 
21 #ifdef _MSC_VER
22 #pragma warning(push)
23 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
24 #endif
25 
26 // Forward declarations
27 namespace geos {
28 namespace geom {
29 class CoordinateSequence;
30 }
31 namespace geomgraph {
32 class Edge;
33 namespace index {
34 class SegmentIntersector;
35 }
36 }
37 }
38 
39 namespace geos {
40 namespace geomgraph { // geos::geomgraph
41 namespace index { // geos::geomgraph::index
42 
45 class GEOS_DLL MonotoneChainEdge {
46 public:
47  //MonotoneChainEdge();
48  ~MonotoneChainEdge() = default;
49  MonotoneChainEdge(Edge* newE);
50  const geom::CoordinateSequence* getCoordinates();
51  std::vector<size_t>& getStartIndexes();
52  double getMinX(std::size_t chainIndex);
53  double getMaxX(std::size_t chainIndex);
54 
55  void computeIntersects(const MonotoneChainEdge& mce,
56  SegmentIntersector& si);
57 
58  void computeIntersectsForChain(std::size_t chainIndex0,
59  const MonotoneChainEdge& mce, std::size_t chainIndex1,
60  SegmentIntersector& si);
61 
62 protected:
63  Edge* e;
64  const geom::CoordinateSequence* pts; // cache a reference to the coord array, for efficiency
65  // the lists of start/end indexes of the monotone chains.
66  // Includes the end point of the edge as a sentinel
67  std::vector<size_t> startIndex;
68  // these envelopes are created once and reused
69 private:
70  void computeIntersectsForChain(std::size_t start0, std::size_t end0,
71  const MonotoneChainEdge& mce,
72  std::size_t start1, std::size_t end1,
73  SegmentIntersector& ei);
74 
75  bool overlaps(std::size_t start0, std::size_t end0, const MonotoneChainEdge& mce, std::size_t start1, std::size_t end1);
76 
77 };
78 
79 } // namespace geos.geomgraph.index
80 } // namespace geos.geomgraph
81 } // namespace geos
82 
83 #ifdef _MSC_VER
84 #pragma warning(pop)
85 #endif
The internal representation of a list of coordinates inside a Geometry.
Definition: CoordinateSequence.h:56
Definition: geomgraph/Edge.h:63
MonotoneChains are a way of partitioning the segments of an edge to allow for fast searching of inter...
Definition: MonotoneChainEdge.h:45
Computes the intersection of line segments, and adds the intersection to the edges containing the seg...
Definition: geomgraph/index/SegmentIntersector.h:46
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25