-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathtensormax.cpp
executable file
·168 lines (150 loc) · 5.48 KB
/
tensormax.cpp
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
/*
Copyright ©2013 The Regents of the University of California
(Regents). All Rights Reserved. Permission to use, copy, modify, and
distribute this software and its documentation for educational,
research, and not-for-profit purposes, without fee and without a
signed licensing agreement, is hereby granted, provided that the
above copyright notice, this paragraph and the following two
paragraphs appear in all copies, modifications, and
distributions. Contact The Office of Technology Licensing, UC
Berkeley, 2150 Shattuck Avenue, Suite 510, Berkeley, CA 94720-1620,
(510) 643-7201, for commercial licensing opportunities.
IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT,
INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING
LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
DOCUMENTATION, EVEN IF REGENTS HAS BEEN ADVISED OF THE POSSIBILITY
OF SUCH DAMAGE.
REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
FOR A PARTICULAR PURPOSE. THE SOFTWARE AND ACCOMPANYING
DOCUMENTATION, IF ANY, PROVIDED HEREUNDER IS PROVIDED "AS
IS". REGENTS HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT,
UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
*/
#include "tensormax.hpp"
#include "util.hpp"
using namespace std;
struct Disk {
Vec2 c;
double r;
Disk (): c(Vec2(0)), r(0) {}
Disk (const Vec2 &c, double r): c(c), r(r) {}
};
ostream &operator<< (ostream &out, const Disk &disk) {out << "Circle[{" << disk.c[0] << "," << disk.c[1] << "}," << disk.r << "]"; return out;}
// Welzl, Smallest enclosing disks..., 1991
Disk welzls_algorithm (const vector<Disk> &disks);
Mat2x2 tensor_max (const vector<Mat2x2> &Ms) {
int n = Ms.size();
vector<Disk> disks;
for (int i = 0; i < n; i++) {
const Mat2x2 &M = Ms[i];
if (trace(M) == 0)
continue;
disks.push_back(Disk(Vec2((M(0,0)-M(1,1))/2, (M(0,1)+M(1,0))/2),
(M(0,0)+M(1,1))/2));
}
Disk disk = welzls_algorithm(disks);
return disk.c[0]*Mat2x2(Vec2(1,0),Vec2(0,-1))
+ disk.c[1]*Mat2x2(Vec2(0,1),Vec2(1,0))
+ disk.r*Mat2x2(Vec2(1,0),Vec2(0,1));
}
Disk minidisk (const vector<Disk> &P);
Disk b_minidisk (const vector<Disk> &P, const vector<Disk> &R);
Disk b_md (const vector<Disk> &R);
Disk welzls_algorithm (const vector<Disk> &disks) {
return minidisk(disks);
}
bool enclosed (const Disk &disk0, const Disk &disk1);
template <typename T> T head (const vector<T> &v);
template <typename T> vector<T> tail (const vector<T> &v);
template <typename T> vector<T> cons (const T &x, const vector<T> &v);
Disk minidisk (const vector<Disk> &P) {
if (P.empty())
return Disk();
Disk p = head(P);
vector<Disk> P_ = tail(P);
Disk D = minidisk(P_);
if (enclosed(p, D))
return D;
else
return b_minidisk(P_, vector<Disk>(1,p));
}
Disk b_minidisk (const vector<Disk> &P, const vector<Disk> &R) {
if (P.empty() || R.size() == 3)
return b_md(R);
Disk p = head(P);
vector<Disk> P_ = tail(P);
Disk D = b_minidisk(P_, R);
if (enclosed(p, D))
return D;
else
return b_minidisk(P_, cons(p, R));
}
Disk apollonius (const Disk &disk1, const Disk &disk2, const Disk &disk3);
Disk b_md (const vector<Disk> &R) {
if (R.empty())
return Disk();
else if (R.size() == 1)
return head(R);
else if (R.size() == 2) {
double d = norm(R[0].c - R[1].c);
double r = (R[0].r + d + R[1].r)/2;
double t = (r - R[0].r)/d;
return Disk(R[0].c + t*(R[1].c - R[0].c), r);
} else
return apollonius(R[0], R[1], R[2]);
}
Disk apollonius (const Disk &disk1, const Disk &disk2, const Disk &disk3) {
// nicked from http://rosettacode.org/mw/index.php?title=Problem_of_Apollonius&oldid=88212
#define DEFXYR(N) double x##N = disk##N.c[0]; \
double y##N = disk##N.c[1]; \
double r##N = disk##N.r;
DEFXYR(1); DEFXYR(2); DEFXYR(3);
#undef DEFXYR
int s1 = 1, s2 = 1, s3 = 1;
double v11 = 2*x2 - 2*x1;
double v12 = 2*y2 - 2*y1;
double v13 = x1*x1 - x2*x2 + y1*y1 - y2*y2 - r1*r1 + r2*r2;
double v14 = 2*s2*r2 - 2*s1*r1;
double v21 = 2*x3 - 2*x2;
double v22 = 2*y3 - 2*y2;
double v23 = x2*x2 - x3*x3 + y2*y2 - y3*y3 - r2*r2 + r3*r3;
double v24 = 2*s3*r3 - 2*s2*r2;
double w12 = v12/v11;
double w13 = v13/v11;
double w14 = v14/v11;
double w22 = v22/v21-w12;
double w23 = v23/v21-w13;
double w24 = v24/v21-w14;
double P = -w23/w22;
double Q = w24/w22;
double M = -w12*P-w13;
double N = w14 - w12*Q;
double a = N*N + Q*Q - 1;
double b = 2*M*N - 2*N*x1 + 2*P*Q - 2*Q*y1 + 2*s1*r1;
double c = x1*x1 + M*M - 2*M*x1 + P*P + y1*y1 - 2*P*y1 - r1*r1;
double D = b*b-4*a*c;
double rs = (-b-sqrt(D))/(2*a);
double xs = M+N*rs;
double ys = P+Q*rs;
return Disk(Vec2(xs,ys), rs);
}
bool enclosed (const Disk &disk0, const Disk &disk1) {
return norm(disk0.c-disk1.c) + disk0.r <= disk1.r + 1e-6;
}
template <typename T> T head (const vector<T> &v) {
return v.front();
}
template <typename T> vector<T> tail (const vector<T> &v) {
vector<T> w(v.size()-1);
for (int i = 0; i < w.size(); i++)
w[i] = v[i+1];
return w;
}
template <typename T> vector<T> cons (const T &x, const vector<T> &v) {
vector<T> w(v.size()+1);
w[0] = x;
for (int i = 1; i < w.size(); i++)
w[i] = v[i-1];
return w;
}