Constructor.
Khachiyan algorithm for Minimum Volume Enclosing Ellipse (MVEE).
The template argument T refers to a data structure which should have the following member methods:
59 {
62
63 const int N =
distance(__begin, __end);
64
67 }
68
70
72
73
74
76
77 for (T p = __begin; p != __end; ++p) {
78
80
81 A.a00 += p->getX() * U[i] * p->getX();
82 A.a01 += p->getX() * U[i] * p->getY();
83 A.a02 += p->getX() * U[i] * 1.0;
84
85 A.a11 += p->getY() * U[i] * p->getY();
86 A.a12 += p->getY() * U[i] * 1.0;
87
88 A.a22 += 1.0 * U[i] * 1.0;
89 }
90
92
93 A.a20 = A.a02;
94 A.a21 = A.a12;
95
96
97
98
99 try {
100 A.invert();
101 }
102 catch(exception& error) {
103 return;
104 }
105
106
107
108 double Dmax = -1.0;
109 int index = 0;
110
111 for (T p = __begin; p != __end; ++p) {
112
113 const double D = (p->getX() * (A.a00 * p->getX() + A.a01 * p->getY() + A.a02 * 1.0) +
114 p->getY() * (A.a10 * p->getX() + A.a11 * p->getY() + A.a12 * 1.0) +
115 1.0 * (A.a20 * p->getX() + A.a21 * p->getY() + A.a22 * 1.0));
116
117 if (D > Dmax) {
118 Dmax = D;
120 }
121 }
122
123 double step = (Dmax - 3.0) / (3.0 * (Dmax - 1.0));
124
125
126
127 for (int i = 0; i < N; ++i) {
128 U[i] = (1.0 - step) * U[i];
129 }
130
131 U[index] += step;
132
133
134
135 if (Dmax - 3.0 <= precision) {
136 break;
137 }
138 }
139
140
141
143
144 for (T p = __begin; p != __end; ++p) {
145
147
149 }
150
151
152
154
155 for (T p = __begin; p != __end; ++p) {
156
158
159 const double x = p->getX() - this->
getX();
160 const double y = p->getY() - this->
getY();
161
162 B.
a00 +=
x * U[i] *
x;
163 B.a01 +=
x * U[i] *
y;
164 B.a11 +=
y * U[i] *
y;
165 }
166
168
169 try {
170 B.invert();
171 }
172 catch(exception& error) {
173 return;
174 }
175
176 B *= 0.5;
177
178 const double trace = B.a00 + B.a11;
179 const double D = sqrt((B.a00 - B.a11) * (B.a00 - B.a11) + 4.0 * B.a01 * B.a01);
180
181 const double lambda_1 = (trace - D) / 2.0;
182 const double lambda_2 = (trace + D) / 2.0;
183
184 this->
major = 1.0 / sqrt(lambda_1);
185 this->
minor = 1.0 / sqrt(lambda_2);
186 this->
angle = 0.5 * atan2(-2.0 * B.a01, B.a11 - B.a00);
187
188
189
191
192 double Fmax = 1.0;
193
194 for (T p = __begin; p != __end; ++p) {
195
197
199
200 pos.rotate_back(R);
201
202 const double F = hypot(pos.getX() / this->major,
203 pos.getY() / this->minor);
204
205 if (F > Fmax) {
206 Fmax = F;
207 }
208 }
209
212 }
#define THROW(JException_t, A)
Marco for throwing exception with std::ostream compatible message.
Data structure for position in two dimensions.
const JPosition2D & getPosition() const
Get position.
JPosition2D()
Default constructor.
void setPosition(const JVector2D &pos)
Set position.
double getY() const
Get y position.
double getX() const
Get x position.
JVector2D & add(const JVector2D &vector)
Add vector.
Exception for accessing a value in a collection that is outside of its range.
This name space includes all other name spaces (except KM3NETDAQ, KM3NET and ANTARES).
static const int MINIMUM_NUMBER_OF_POINTS
double angle
rotation angle in radians
size_t numberOfIterations