GEOS 3.14.0dev
CoordinateSequence.h
1/**********************************************************************
2 *
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
5 *
6 * Copyright (C) 2022 ISciences LLC
7 * Copyright (C) 2006 Refractions Research 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
20#include <geos/geom/Coordinate.h> // for applyCoordinateFilter
21#include <geos/geom/CoordinateSequenceIterator.h>
22
23#include <cassert>
24#include <vector>
25#include <iostream>
26#include <iosfwd> // ostream
27#include <memory> // for unique_ptr typedef
28
29// Forward declarations
30namespace geos {
31namespace geom {
32class Envelope;
33class CoordinateFilter;
34}
35}
36
37namespace geos {
38namespace geom { // geos::geom
39
56class GEOS_DLL CoordinateSequence {
57
58public:
59
61 enum { X, Y, Z, M };
62
63 using iterator = CoordinateSequenceIterator<CoordinateSequence, Coordinate>;
64 using const_iterator = CoordinateSequenceIterator<const CoordinateSequence, const Coordinate>;
65
66 typedef std::unique_ptr<CoordinateSequence> Ptr;
67
70
75
83 CoordinateSequence(std::size_t size, std::size_t dim = 0);
84
96 CoordinateSequence(std::size_t size, bool hasz, bool hasm, bool initialize = true);
97
103 CoordinateSequence(const std::initializer_list<Coordinate>&);
104
109 CoordinateSequence(const std::initializer_list<CoordinateXY>&);
110
116 CoordinateSequence(const std::initializer_list<CoordinateXYM>&);
117
121 CoordinateSequence(const std::initializer_list<CoordinateXYZM>&);
122
128 static CoordinateSequence XY(std::size_t size) {
129 return CoordinateSequence(size, false, false);
130 }
131
137 static CoordinateSequence XYZ(std::size_t size) {
138 return CoordinateSequence(size, true, false);
139 }
140
146 static CoordinateSequence XYZM(std::size_t size) {
147 return CoordinateSequence(size, true, true);
148 }
149
155 static CoordinateSequence XYM(std::size_t size) {
156 return CoordinateSequence(size, false, true);
157 }
158
162 std::unique_ptr<CoordinateSequence> clone() const;
163
167
174
178 std::size_t getSize() const {
179 return size();
180 }
181
185 size_t size() const
186 {
187 assert(stride() == 2 || stride() == 3 || stride() == 4);
188 switch(stride()) {
189 case 2: return m_vect.size() / 2;
190 case 4: return m_vect.size() / 4;
191 default : return m_vect.size() / 3;
192 }
193 }
194
196 bool isEmpty() const {
197 return m_vect.empty();
198 }
199
206 bool isRing() const;
207
214 std::size_t getDimension() const;
215
216 bool hasZ() const {
217 return m_hasdim ? m_hasz : (m_vect.empty() || !std::isnan(m_vect[2]));
218 }
219
220 bool hasM() const {
221 return m_hasm;
222 }
223
225 bool hasRepeatedPoints() const;
226
229
233 CoordinateType getCoordinateType() const {
234 switch(stride()) {
235 case 4: return CoordinateType::XYZM;
236 case 2: return CoordinateType::XY;
237 default: return hasM() ? CoordinateType::XYM : CoordinateType::XYZ;
238 }
239 }
240
244
248 template<typename T=Coordinate>
249 const T& getAt(std::size_t i) const {
250 static_assert(std::is_base_of<CoordinateXY, T>::value, "Must be a Coordinate class");
251 assert(sizeof(T) <= sizeof(double) * stride());
252 assert(i*stride() < m_vect.size());
253 const T* orig = reinterpret_cast<const T*>(&m_vect[i*stride()]);
254 return *orig;
255 }
256
260 template<typename T=Coordinate>
261 T& getAt(std::size_t i) {
262 static_assert(std::is_base_of<CoordinateXY, T>::value, "Must be a Coordinate class");
263 assert(sizeof(T) <= sizeof(double) * stride());
264 assert(i*stride() < m_vect.size());
265 T* orig = reinterpret_cast<T*>(&m_vect[i*stride()]);
266 return *orig;
267 }
268
272 template<typename T>
273 void getAt(std::size_t i, T& c) const {
274 switch(getCoordinateType()) {
275 case CoordinateType::XY: c = getAt<CoordinateXY>(i); break;
276 case CoordinateType::XYZ: c = getAt<Coordinate>(i); break;
277 case CoordinateType::XYZM: c = getAt<CoordinateXYZM>(i); break;
278 case CoordinateType::XYM: c = getAt<CoordinateXYM>(i); break;
279 default: getAt<Coordinate>(i);
280 }
281 }
282
283 void getAt(std::size_t i, CoordinateXY& c) const {
284 c = getAt<CoordinateXY>(i);
285 }
286
287 // TODO: change to return CoordinateXY
291 const Coordinate& operator[](std::size_t i) const
292 {
293 return getAt(i);
294 }
295
296 // TODO: change to return CoordinateXY
301 operator[](std::size_t i)
302 {
303 return getAt(i);
304 }
305
316 double getOrdinate(std::size_t index, std::size_t ordinateIndex) const;
317
324 double getX(std::size_t index) const
325 {
326 return m_vect[index * stride()];
327 }
328
335 double getY(std::size_t index) const
336 {
337 return m_vect[index * stride() + 1];
338 }
339
341 template<typename T=Coordinate>
342 const T& back() const
343 {
344 return getAt<T>(size() - 1);
345 }
346
348 template<typename T=Coordinate>
349 T& back()
350 {
351 return getAt<T>(size() - 1);
352 }
353
355 template<typename T=Coordinate>
356 const T& front() const
357 {
358 return *(reinterpret_cast<const T*>(m_vect.data()));
359 }
360
362 template<typename T=Coordinate>
363 T& front()
364 {
365 return *(reinterpret_cast<T*>(m_vect.data()));
366 }
367
369 void toVector(std::vector<Coordinate>& coords) const;
370
371 void toVector(std::vector<CoordinateXY>& coords) const;
372
373
377
379 template<typename T>
380 void setAt(const T& c, std::size_t pos) {
381 switch(getCoordinateType()) {
382 case CoordinateType::XY: setAtImpl<CoordinateXY>(c, pos); break;
383 case CoordinateType::XYZ: setAtImpl<Coordinate>(c, pos); break;
384 case CoordinateType::XYZM: setAtImpl<CoordinateXYZM>(c, pos); break;
385 case CoordinateType::XYM: setAtImpl<CoordinateXYM>(c, pos); break;
386 default: setAtImpl<Coordinate>(c, pos);
387 }
388 }
389
398 void setOrdinate(std::size_t index, std::size_t ordinateIndex, double value);
399
401 void setPoints(const std::vector<Coordinate>& v);
402
406
411 template<typename T=Coordinate>
412 void add(const T& c) {
413 add(c, size());
414 }
415
422 template<typename T>
423 void add(const T& c, bool allowRepeated)
424 {
425 if(!allowRepeated && !isEmpty()) {
426 const CoordinateXY& last = back<CoordinateXY>();
427 if(last.equals2D(c)) {
428 return;
429 }
430 }
431
432 add(c);
433 }
434
443 template<typename T>
444 void add(const T& c, std::size_t pos)
445 {
446 static_assert(std::is_base_of<CoordinateXY, T>::value, "Must be a Coordinate class");
447
448 // c may be a reference inside m_vect, so we make sure it will not
449 // grow before adding it
450 if (m_vect.size() + stride() <= m_vect.capacity()) {
451 make_space(pos, 1);
452 setAt(c, static_cast<std::size_t>(pos));
453 } else {
454 T tmp{c};
455 make_space(pos, 1);
456 setAt(tmp, static_cast<std::size_t>(pos));
457 }
458 }
459
469 template<typename T>
470 void add(std::size_t i, const T& coord, bool allowRepeated)
471 {
472 // don't add duplicate coordinates
473 if(! allowRepeated) {
474 std::size_t sz = size();
475 if(sz > 0) {
476 if(i > 0) {
477 const CoordinateXY& prev = getAt<CoordinateXY>(i - 1);
478 if(prev.equals2D(coord)) {
479 return;
480 }
481 }
482 if(i < sz) {
483 const CoordinateXY& next = getAt<CoordinateXY>(i);
484 if(next.equals2D(coord)) {
485 return;
486 }
487 }
488 }
489 }
490
491 add(coord, i);
492 }
493
494 void add(double x, double y) {
495 CoordinateXY c(x, y);
496 add(c);
497 }
498
499 void add(const CoordinateSequence& cs);
500
501 void add(const CoordinateSequence& cs, bool allowRepeated);
502
503 void add(const CoordinateSequence& cl, bool allowRepeated, bool forwardDirection);
504
505 void add(const CoordinateSequence& cs, std::size_t from, std::size_t to);
506
507 void add(const CoordinateSequence& cs, std::size_t from, std::size_t to, bool allowRepeated);
508
509 template<typename T, typename... Args>
510 void add(T begin, T end, Args... args) {
511 for (auto it = begin; it != end; ++it) {
512 add(*it, args...);
513 }
514 }
515
516 template<typename T>
517 void add(std::size_t i, T from, T to) {
518 auto npts = static_cast<std::size_t>(std::distance(from, to));
519 make_space(i, npts);
520
521 for (auto it = from; it != to; ++it) {
522 setAt(*it, i);
523 i++;
524 }
525 }
526
530
531 void clear() {
532 m_vect.clear();
533 }
534
535 void reserve(std::size_t capacity) {
536 m_vect.reserve(capacity * stride());
537 }
538
539 void resize(std::size_t capacity) {
540 m_vect.resize(capacity * stride());
541 }
542
543 void pop_back();
544
546 std::string toString() const;
547
549 const CoordinateXY* minCoordinate() const;
550
557
559 //
562 static std::size_t indexOf(const CoordinateXY* coordinate,
563 const CoordinateSequence* cl);
564
570 static bool equals(const CoordinateSequence* cl1,
571 const CoordinateSequence* cl2);
572
578 bool equalsIdentical(const CoordinateSequence& other) const;
579
581 static void scroll(CoordinateSequence* cl, const CoordinateXY* firstCoordinate);
582
601
603 void reverse();
604
605 void sort();
606
607
613 void expandEnvelope(Envelope& env) const;
614
615 void closeRing(bool allowRepeated = false);
616
620
621 template<typename Filter>
622 void apply_rw(const Filter* filter) {
623 switch(getCoordinateType()) {
624 case CoordinateType::XY:
625 for (auto& c : items<CoordinateXY>()) {
626 if (filter->isDone()) break;
627 filter->filter_rw(&c);
628 }
629 break;
630 case CoordinateType::XYZ:
631 for (auto& c : items<Coordinate>()) {
632 if (filter->isDone()) break;
633 filter->filter_rw(&c);
634 }
635 break;
636 case CoordinateType::XYM:
637 for (auto& c : items<CoordinateXYM>()) {
638 if (filter->isDone()) break;
639 filter->filter_rw(&c);
640 }
641 break;
642 case CoordinateType::XYZM:
643 for (auto& c : items<CoordinateXYZM>()) {
644 if (filter->isDone()) break;
645 filter->filter_rw(&c);
646 }
647 break;
648 }
649 m_hasdim = m_hasz = false; // re-check (see http://trac.osgeo.org/geos/ticket/435)
650 }
651
652 template<typename Filter>
653 void apply_ro(Filter* filter) const {
654 switch(getCoordinateType()) {
655 case CoordinateType::XY:
656 for (const auto& c : items<CoordinateXY>()) {
657 if (filter->isDone()) break;
658 filter->filter_ro(&c);
659 }
660 break;
661 case CoordinateType::XYZ:
662 for (const auto& c : items<Coordinate>()) {
663 if (filter->isDone()) break;
664 filter->filter_ro(&c);
665 }
666 break;
667 case CoordinateType::XYM:
668 for (const auto& c : items<CoordinateXYM>()) {
669 if (filter->isDone()) break;
670 filter->filter_ro(&c);
671 }
672 break;
673 case CoordinateType::XYZM:
674 for (const auto& c : items<CoordinateXYZM>()) {
675 if (filter->isDone()) break;
676 filter->filter_ro(&c);
677 }
678 break;
679 }
680 }
681
682 template<typename F>
683 auto applyAt(size_t i, F&& fun) const {
684 switch(getCoordinateType()) {
685 case CoordinateType::XYZ: return fun(getAt<Coordinate>(i));
686 case CoordinateType::XYM: return fun(getAt<CoordinateXYM>(i));
687 case CoordinateType::XYZM: return fun(getAt<CoordinateXYZM>(i));
688 default: return fun(getAt<CoordinateXY>(i));
689 }
690 }
691
692 template<typename F>
693 void forEach(F&& fun) const {
694 switch(getCoordinateType()) {
695 case CoordinateType::XY: for (const auto& c : items<CoordinateXY>()) { fun(c); } break;
696 case CoordinateType::XYZ: for (const auto& c : items<Coordinate>()) { fun(c); } break;
697 case CoordinateType::XYM: for (const auto& c : items<CoordinateXYM>()) { fun(c); } break;
698 case CoordinateType::XYZM: for (const auto& c : items<CoordinateXYZM>()) { fun(c); } break;
699 }
700 }
701
702 template<typename T, typename F>
703 void forEach(F&& fun) const
704 {
705 for (std::size_t i = 0; i < size(); i++) {
706 fun(getAt<T>(i));
707 }
708 }
709
710 template<typename T, typename F>
711 void forEach(std::size_t from, std::size_t to, F&& fun) const
712 {
713 for (std::size_t i = from; i <= to; i++) {
714 fun(getAt<T>(i));
715 }
716 }
717
718 template<typename T>
719 class Coordinates {
720 public:
721 using SequenceType = typename std::conditional<std::is_const<T>::value, const CoordinateSequence, CoordinateSequence>::type;
722
723 explicit Coordinates(SequenceType* seq) : m_seq(seq) {}
724
725 CoordinateSequenceIterator<SequenceType, T> begin() {
726 return {m_seq};
727 }
728
729 CoordinateSequenceIterator<SequenceType, T> end() {
730 return {m_seq, m_seq->getSize()};
731 }
732
733 CoordinateSequenceIterator<const SequenceType, typename std::add_const<T>::type>
734 begin() const {
735 return CoordinateSequenceIterator<const SequenceType, typename std::add_const<T>::type>{m_seq};
736 }
737
738 CoordinateSequenceIterator<const SequenceType, typename std::add_const<T>::type>
739 end() const {
740 return CoordinateSequenceIterator<const SequenceType, typename std::add_const<T>::type>{m_seq, m_seq->getSize()};
741 }
742
743 CoordinateSequenceIterator<const SequenceType, typename std::add_const<T>::type>
744 cbegin() const {
745 return CoordinateSequenceIterator<const SequenceType, typename std::add_const<T>::type>{m_seq};
746 }
747
748 CoordinateSequenceIterator<const SequenceType, typename std::add_const<T>::type>
749 cend() const {
750 return CoordinateSequenceIterator<const SequenceType, typename std::add_const<T>::type>{m_seq, m_seq->getSize()};
751 }
752
753 private:
754 SequenceType* m_seq;
755 };
756
757 template<typename T>
758 Coordinates<typename std::add_const<T>::type> items() const {
759 return Coordinates<typename std::add_const<T>::type>(this);
760 }
761
762 template<typename T>
763 Coordinates<T> items() {
764 return Coordinates<T>(this);
765 }
766
767
769
770 double* data() {
771 return m_vect.data();
772 }
773
774 const double* data() const {
775 return m_vect.data();
776 }
777
778private:
779 std::vector<double> m_vect; // Vector to store values
780
781 uint8_t m_stride; // Stride of stored values, corresponding to underlying type
782
783 mutable bool m_hasdim; // Has the dimension of this sequence been determined? Or was it created with no
784 // explicit dimensionality, and we're waiting for getDimension() to be called
785 // after some coordinates have been added?
786 mutable bool m_hasz;
787 bool m_hasm;
788
789 void initialize();
790
791 template<typename T1, typename T2>
792 void setAtImpl(const T2& c, std::size_t pos) {
793 auto& orig = getAt<T1>(pos);
794 orig = c;
795 }
796
797 void make_space(std::size_t pos, std::size_t n) {
798 m_vect.insert(std::next(m_vect.begin(), static_cast<std::ptrdiff_t>(pos * stride())),
799 m_stride * n,
800 DoubleNotANumber);
801 }
802
803 std::uint8_t stride() const {
804 return m_stride;
805 }
806
807};
808
809GEOS_DLL std::ostream& operator<< (std::ostream& os, const CoordinateSequence& cs);
810
811GEOS_DLL bool operator== (const CoordinateSequence& s1, const CoordinateSequence& s2);
812
813GEOS_DLL bool operator!= (const CoordinateSequence& s1, const CoordinateSequence& s2);
814
815} // namespace geos::geom
816} // namespace geos
817
The internal representation of a list of coordinates inside a Geometry.
Definition CoordinateSequence.h:56
Coordinate is the lightweight class used to store coordinates.
Definition Coordinate.h:217
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition Envelope.h:59
T & getAt(std::size_t i)
Returns a reference to Coordinate at position i.
Definition CoordinateSequence.h:261
Coordinate & operator[](std::size_t i)
Definition CoordinateSequence.h:301
void toVector(std::vector< Coordinate > &coords) const
Pushes all Coordinates of this sequence into the provided vector.
double getOrdinate(std::size_t index, std::size_t ordinateIndex) const
const T & front() const
Return first Coordinate in the sequence.
Definition CoordinateSequence.h:356
T & back()
Return last Coordinate in the sequence.
Definition CoordinateSequence.h:349
void getAt(std::size_t i, T &c) const
Write Coordinate at position i to given Coordinate.
Definition CoordinateSequence.h:273
const T & getAt(std::size_t i) const
Returns a read-only reference to Coordinate at position i.
Definition CoordinateSequence.h:249
T & front()
Return first Coordinate in the sequence.
Definition CoordinateSequence.h:363
double getX(std::size_t index) const
Definition CoordinateSequence.h:324
double getY(std::size_t index) const
Definition CoordinateSequence.h:335
const Coordinate & operator[](std::size_t i) const
Definition CoordinateSequence.h:291
const T & back() const
Return last Coordinate in the sequence.
Definition CoordinateSequence.h:342
void add(const T &c, bool allowRepeated)
Definition CoordinateSequence.h:423
void add(std::size_t i, const T &coord, bool allowRepeated)
Inserts the specified coordinate at the specified position in this list.
Definition CoordinateSequence.h:470
void add(const T &c)
Definition CoordinateSequence.h:412
void add(const T &c, std::size_t pos)
Inserts the specified coordinate at the specified position in this sequence. If multiple coordinates ...
Definition CoordinateSequence.h:444
CoordinateSequence(const std::initializer_list< CoordinateXYZM > &)
static CoordinateSequence XYM(std::size_t size)
Definition CoordinateSequence.h:155
CoordinateSequence(const std::initializer_list< CoordinateXY > &)
std::unique_ptr< CoordinateSequence > clone() const
Returns a heap-allocated deep copy of this CoordinateSequence.
CoordinateSequence(std::size_t size, bool hasz, bool hasm, bool initialize=true)
static CoordinateSequence XYZM(std::size_t size)
Definition CoordinateSequence.h:146
static CoordinateSequence XYZ(std::size_t size)
Definition CoordinateSequence.h:137
static CoordinateSequence XY(std::size_t size)
Definition CoordinateSequence.h:128
CoordinateSequence(std::size_t size, std::size_t dim=0)
CoordinateSequence(const std::initializer_list< CoordinateXYM > &)
CoordinateSequence(const std::initializer_list< Coordinate > &)
void setOrdinate(std::size_t index, std::size_t ordinateIndex, double value)
void setPoints(const std::vector< Coordinate > &v)
Substitute Coordinate list with a copy of the given vector.
void setAt(const T &c, std::size_t pos)
Copy Coordinate c to position pos.
Definition CoordinateSequence.h:380
std::size_t getSize() const
Returns the number of Coordinates.
Definition CoordinateSequence.h:178
bool hasRepeatedOrInvalidPoints() const
Returns true if contains any NaN/Inf coordinates.
size_t size() const
Returns the number of Coordinates.
Definition CoordinateSequence.h:185
bool hasRepeatedPoints() const
Returns true if contains any two consecutive points.
CoordinateType getCoordinateType() const
Definition CoordinateSequence.h:233
bool isEmpty() const
Returns true if list contains no coordinates.
Definition CoordinateSequence.h:196
bool isRing() const
Tests whether an a CoordinateSequence forms a ring, by checking length and closure....
std::size_t getDimension() const
bool equalsIdentical(const CoordinateSequence &other) const
Returns true if the two sequences are identical (pointwise equal in all dimensions,...
void reverse()
Reverse Coordinate order in given CoordinateSequence.
static void scroll(CoordinateSequence *cl, const CoordinateXY *firstCoordinate)
Scroll given CoordinateSequence so to start with given Coordinate.
const CoordinateXY * minCoordinate() const
Returns lower-left Coordinate in list.
static int increasingDirection(const CoordinateSequence &pts)
Determines which orientation of the Coordinate array is (overall) increasing.
void expandEnvelope(Envelope &env) const
static CoordinateSequence * atLeastNCoordinatesOrNothing(std::size_t n, CoordinateSequence *c)
Returns either the given CoordinateSequence if its length is greater than the given amount,...
std::string toString() const
Get a string representation of CoordinateSequence.
static std::size_t indexOf(const CoordinateXY *coordinate, const CoordinateSequence *cl)
Return position of a Coordinate.
static bool equals(const CoordinateSequence *cl1, const CoordinateSequence *cl2)
Returns true if the two arrays are identical, both null, or pointwise equal in two dimensions.
Basic namespace for all GEOS functionalities.
Definition geos.h:39