GEOS  3.11.0beta2
RingHull.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2021 Paul Ramsey <pramsey@cleverelephant.ca>
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 #pragma once
16 
17 #include <geos/geom/Coordinate.h>
18 #include <geos/simplify/LinkedRing.h>
19 #include <geos/index/VertexSequencePackedRtree.h>
20 
21 #include <queue>
22 
23 namespace geos {
24 namespace geom {
25 class Envelope;
26 class LinearRing;
27 class LineString;
28 class Polygon;
29 }
30 namespace simplify {
31 class RingHullIndex;
32 }
33 }
34 
35 
42 
43 
44 namespace geos {
45 namespace simplify { // geos::simplify
46 
47 
48 class RingHull
49 {
50 
51 public:
52 
53  /*
54  * Creates a new instance.
55  *
56  * @param p_ring the ring vertices to process
57  * @param p_isOuter whether the hull is outer or inner
58  */
59  RingHull(const LinearRing* p_ring, bool p_isOuter);
60 
61  void setMinVertexNum(std::size_t minVertexNum);
62 
63  void setMaxAreaDelta(double maxAreaDelta);
64 
65  const Envelope* getEnvelope() const;
66 
67  std::unique_ptr<LinearRing> getHull(RingHullIndex& hullIndex);
68 
69  static bool isConvex(const LinkedRing& vertexRing, std::size_t index);
70 
71  static double area(const LinkedRing& vertexRing, std::size_t index);
72 
73  void compute(RingHullIndex& hullIndex);
74 
75  std::unique_ptr<Polygon> toGeometry() const;
76 
77 
78 private:
79 
80 
81  class Corner
82  {
83 
84  private:
85 
86  std::size_t index;
87  std::size_t prev;
88  std::size_t next;
89  double area;
90 
91  public:
92 
93  Corner(std::size_t p_idx, std::size_t p_prev, std::size_t p_next, double p_area)
94  : index(p_idx)
95  , prev(p_prev)
96  , next(p_next)
97  , area(p_area)
98  {};
99 
107  bool operator< (const Corner& rhs) const
108  {
109  return area > rhs.area;
110  };
111 
112  bool operator> (const Corner& rhs) const
113  {
114  return area < rhs.area;
115  };
116 
117  bool operator==(const Corner& rhs) const
118  {
119  return area == rhs.area;
120  };
121 
122  bool isVertex(std::size_t p_index) const;
123  std::size_t getIndex() const;
124  double getArea() const;
125  void envelope(const LinkedRing& ring, Envelope& env) const;
126  bool intersects(const Coordinate& v, const LinkedRing& ring) const;
127  bool isRemoved(const LinkedRing& ring) const;
128  std::unique_ptr<LineString> toLineString(const LinkedRing& ring);
129 
130  }; // class Corner
131 
132 
133 
134  const LinearRing* inputRing;
135  double targetVertexNum = -1.0;
136  double targetAreaDelta = -1.0;
137 
143  std::vector<Coordinate> vertex;
144  std::unique_ptr<LinkedRing> vertexRing;
145  double areaDelta = 0;
146 
152  std::unique_ptr<VertexSequencePackedRtree> vertexIndex;
153 
154  std::priority_queue<Corner> cornerQueue;
155 
156 
157  void init(std::vector<Coordinate>& ring, bool isOuter);
158  void addCorner(std::size_t i, std::priority_queue<Corner>& cornerQueue);
159  bool isAtTarget(const Corner& corner);
160 
170  void removeCorner(const Corner& corner, std::priority_queue<Corner>& cornerQueue);
171  bool isRemovable(const Corner& corner, const RingHullIndex& hullIndex) const;
172 
182  bool hasIntersectingVertex(
183  const Corner& corner,
184  const Envelope& cornerEnv,
185  const RingHull* hull) const;
186 
187  const Coordinate& getCoordinate(std::size_t index) const;
188 
189  void query(
190  const Envelope& cornerEnv,
191  std::vector<std::size_t>& result) const;
192 
193  void queryHull(const Envelope& queryEnv, std::vector<Coordinate>& pts);
194 
195 
196 
197 
198 }; // RingHull
199 
200 
201 } // geos::simplify
202 } // geos
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:58
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
Definition: LineString.h:66
Models an OGC SFS LinearRing. A LinearRing is a LineString which is both closed and simple.
Definition: LinearRing.h:55
Represents a linear polygon, which may include holes.
Definition: Polygon.h:61
Definition: VertexSequencePackedRtree.h:49
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25