1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
/*
Copyrigth 2015, D. Morozov, M. Kerber, A. Nigmetov
This file is part of GeomBottleneck.
GeomBottleneck is free software: you can redistribute it and/or modify
it under the terms of the Lesser GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
GeomBottleneck is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
Lesser GNU General Public License for more details.
You should have received a copy of the Lesser GNU General Public License
along with GeomBottleneck. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef BASIC_DEFS_BT_H
#define BASIC_DEFS_BT_H
#ifdef _WIN32
#include <ciso646>
#endif
#include <vector>
#include <stdexcept>
#include <cmath>
#include <cstddef>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cassert>
#include "def_debug_bt.h"
#ifndef FOR_R_TDA
#include <iostream>
#endif
namespace geom_bt {
typedef double CoordinateType;
typedef int IdType;
constexpr IdType MinValidId = 10;
struct Point {
CoordinateType x, y;
bool operator==(const Point& other) const;
bool operator!=(const Point& other) const;
Point(CoordinateType ax, CoordinateType ay) : x(ax), y(ay) {}
Point() : x(0.0), y(0.0) {}
#ifndef FOR_R_TDA
friend std::ostream& operator<<(std::ostream& output, const Point p);
#endif
};
struct DiagramPoint
{
// Points above the diagonal have type NORMAL
// Projections onto the diagonal have type DIAG
// for DIAG points only x-coordinate is relevant
// to-do: add getters/setters, checks in constructors, etc
enum Type { NORMAL, DIAG};
// data members
private:
CoordinateType x, y;
public:
Type type;
IdType id;
// operators, constructors
bool operator==(const DiagramPoint& other) const;
bool operator!=(const DiagramPoint& other) const;
DiagramPoint(CoordinateType xx, CoordinateType yy, Type ttype, IdType uid);
bool isDiagonal(void) const { return type == DIAG; }
bool isNormal(void) const { return type == NORMAL; }
CoordinateType inline getRealX() const // return the x-coord
{
return x;
//if (DiagramPoint::NORMAL == type)
//return x;
//else
//return 0.5 * ( x + y);
}
CoordinateType inline getRealY() const // return the y-coord
{
return y;
//if (DiagramPoint::NORMAL == type)
//return y;
//else
//return 0.5 * ( x + y);
}
#ifndef FOR_R_TDA
friend std::ostream& operator<<(std::ostream& output, const DiagramPoint p);
#endif
};
struct PointHash {
size_t operator()(const Point& p) const{
return std::hash<CoordinateType>()(p.x)^std::hash<CoordinateType>()(p.y);
}
};
struct DiagramPointHash {
size_t operator()(const DiagramPoint& p) const{
//return std::hash<CoordinateType>()(p.x)^std::hash<CoordinateType>()(p.y)^std::hash<bool>()(p.type == DiagramPoint::NORMAL);
assert(p.id >= MinValidId);
return std::hash<int>()(p.id);
}
};
CoordinateType sqrDist(const Point& a, const Point& b);
CoordinateType dist(const Point& a, const Point& b);
CoordinateType distLInf(const DiagramPoint& a, const DiagramPoint& b);
typedef std::unordered_set<Point, PointHash> PointSet;
class DiagramPointSet {
public:
void insert(const DiagramPoint p);
void erase(const DiagramPoint& p, bool doCheck = true); // if doCheck, erasing non-existing elements causes assert
void erase(const std::unordered_set<DiagramPoint, DiagramPointHash>::const_iterator it);
void removeDiagonalPoints();
size_t size() const;
void reserve(const size_t newSize);
void clear();
bool empty() const;
bool hasElement(const DiagramPoint& p) const;
std::unordered_set<DiagramPoint, DiagramPointHash>::iterator find(const DiagramPoint& p) { return points.find(p); };
std::unordered_set<DiagramPoint, DiagramPointHash>::const_iterator find(const DiagramPoint& p) const { return points.find(p); };
std::unordered_set<DiagramPoint, DiagramPointHash>::iterator begin() { return points.begin(); };
std::unordered_set<DiagramPoint, DiagramPointHash>::iterator end() { return points.end(); }
std::unordered_set<DiagramPoint, DiagramPointHash>::const_iterator cbegin() const { return points.cbegin(); }
std::unordered_set<DiagramPoint, DiagramPointHash>::const_iterator cend() const { return points.cend(); }
#ifndef FOR_R_TDA
friend std::ostream& operator<<(std::ostream& output, const DiagramPointSet& ps);
#endif
friend void addProjections(DiagramPointSet& A, DiagramPointSet& B);
template<class PairIterator> DiagramPointSet(PairIterator first, PairIterator last);
template<class PairIterator> void fillIn(PairIterator first, PairIterator last);
// default ctor, empty diagram
DiagramPointSet(IdType minId = MinValidId + 1) : maxId(minId + 1) {};
IdType nextId() { return maxId + 1; }
private:
bool isLinked { false };
IdType maxId {MinValidId + 1};
std::unordered_set<DiagramPoint, DiagramPointHash> points;
};
template<typename DiagPointContainer>
CoordinateType getFurthestDistance3Approx(DiagPointContainer& A, DiagPointContainer& B)
{
CoordinateType result { 0.0 };
DiagramPoint begA = *(A.begin());
DiagramPoint optB = *(B.begin());
for(const auto& pointB : B) {
if (distLInf(begA, pointB) > result) {
result = distLInf(begA, pointB);
optB = pointB;
}
}
for(const auto& pointA : A) {
if (distLInf(pointA, optB) > result) {
result = distLInf(pointA, optB);
}
}
return result;
}
template<class PairIterator>
void DiagramPointSet::fillIn(PairIterator start, PairIterator end)
{
isLinked = false;
clear();
IdType uniqueId = MinValidId + 1;
for(auto iter = start; iter != end; ++iter) {
insert(DiagramPoint(iter->first, iter->second, DiagramPoint::NORMAL, uniqueId++));
}
}
template<class PairIterator>
DiagramPointSet::DiagramPointSet(PairIterator start, PairIterator end)
{
fillIn(start, end);
}
// preprocess diagrams A and B by adding projections onto diagonal of points of
// A to B and vice versa. NB: ids of points will be changed!
void addProjections(DiagramPointSet& A, DiagramPointSet& B);
}
#endif
|
