1

2# -*- coding: utf-8 -*-

3

4 u'''2- or 3-D vectorial functions L{circin6}, L{circum3}, L{circum4_},

5 L{iscolinearWith}, L{meeus2}, L{nearestOn}, L{radii11} and L{soddy4}.

6'''

7

8 from pygeodesy.basics import len2, map2, _xnumpy

9 from pygeodesy.constants import EPS, EPS0, EPS02, EPS4, INF, INT0, \

10 _EPS4e8, isnear0, _0_0, _0_25, _0_5, _N_0_5, \

11 _1_0, _1_0_1T, _N_1_0, _2_0, _N_2_0, _4_0

12 from pygeodesy.errors import _and, _AssertionError, IntersectionError, NumPyError, \

13 PointsError, TriangleError, _xError, _xkwds

14 from pygeodesy.fmath import fabs, fdot, hypot, hypot2_, sqrt

15 from pygeodesy.fsums import Fsum, fsumf_, fsum1f_

16 from pygeodesy.interns import NN, _a_, _and_, _b_, _c_, _center_, _coincident_, \

17 _colinear_, _concentric_, _COMMASPACE_, _few_, \

18 _intersection_, _invalid_, _near_, _no_, _of_, \

19 _radius_, _rIn_, _s_, _SPACE_, _too_, _with_

20# from pygeodesy.lazily import _ALL_LAZY # from .named

21 from pygeodesy.named import _ALL_LAZY, _NamedTuple, _Pass, Property_RO

22 from pygeodesy.namedTuples import LatLon3Tuple, Vector2Tuple

23# from pygeodesy.props import Property_RO # from .named

24 from pygeodesy.streprs import Fmt, unstr

25 from pygeodesy.units import Float, Int, Meter, Radius, Radius_

26 from pygeodesy.vector3d import iscolinearWith, nearestOn, _nearestOn2, _nVc, _otherV3d, \

27 trilaterate2d2, trilaterate3d2, Vector3d # PYCHOK unused

28

29 from contextlib import contextmanager

30# from math import fabs, sqrt # from .fmath

31

32__all__ = _ALL_LAZY.vector2d

33__version__ = '23.06.08'

34

35_cA_ = 'cA'

36_cB_ = 'cB'

37_cC_ = 'cC'

38_deltas_ = 'deltas'

39_outer_ = 'outer'

40_raise_ = 'raise' # PYCHOK used!

41_rank_ = 'rank'

42_residuals_ = 'residuals'

43_Type_ = 'Type'

44

45

46 class Circin6Tuple(_NamedTuple):

47 '''6-Tuple C{(radius, center, deltas, cA, cB, cC)} with the C{radius}, the

48 trilaterated C{center} and contact points of the I{inscribed} aka I{In-

49 circle} of a triangle. The C{center} is I{un}ambiguous if C{deltas} is

50 C{None}, otherwise C{center} is the mean and C{deltas} the differences of

51 the L{pygeodesy.trilaterate3d2} results. Contact points C{cA}, C{cB} and

52 C{cC} are the points of tangency, aka the corners of the U{Contact Triangle

53 <https://MathWorld.Wolfram.com/ContactTriangle.html>}.

54 '''

55 _Names_ = (_radius_, _center_, _deltas_, _cA_, _cB_, _cC_)

56 _Units_ = ( Radius, _Pass, _Pass, _Pass, _Pass, _Pass)

57

58

59 class Circum3Tuple(_NamedTuple): # in .latlonBase

60 '''3-Tuple C{(radius, center, deltas)} with the C{circumradius} and trilaterated

61 C{circumcenter} of the C{circumcircle} through 3 points (aka {Meeus}' Type II

62 circle) or the C{radius} and C{center} of the smallest I{Meeus}' Type I circle.

63 The C{center} is I{un}ambiguous if C{deltas} is C{None}, otherwise C{center}

64 is the mean and C{deltas} the differences of the L{pygeodesy.trilaterate3d2}

65 results.

66 '''

67 _Names_ = (_radius_, _center_, _deltas_)

68 _Units_ = ( Radius, _Pass, _Pass)

69

70

71 class Circum4Tuple(_NamedTuple):

72 '''4-Tuple C{(radius, center, rank, residuals)} with C{radius} and C{center}

73 of a sphere I{least-squares} fitted through given points and the C{rank}

74 and C{residuals} -if any- from U{numpy.linalg.lstsq

75 <https://NumPy.org/doc/stable/reference/generated/numpy.linalg.lstsq.html>}.

76 '''

77 _Names_ = (_radius_, _center_, _rank_, _residuals_)

78 _Units_ = ( Radius, _Pass, Int, _Pass)

79

80

81 class Meeus2Tuple(_NamedTuple):

82 '''2-Tuple C{(radius, Type)} with C{radius} and I{Meeus}' C{Type} of the smallest

83 circle I{containing} 3 points. C{Type} is C{None} for a I{Meeus}' Type II

84 C{circumcircle} passing through all 3 points. Otherwise C{Type} is the center

85 of a I{Meeus}' Type I circle with 2 points on (a diameter of) and 1 point

86 inside the circle.

87 '''

88 _Names_ = (_radius_, _Type_)

89 _Units_ = ( Radius, _Pass)

90

91

92 class Radii11Tuple(_NamedTuple):

93 '''11-Tuple C{(rA, rB, rC, cR, rIn, riS, roS, a, b, c, s)} with the C{Tangent}

94 circle radii C{rA}, C{rB} and C{rC}, the C{circumradius} C{cR}, the C{Incircle}

95 radius C{rIn} aka C{inradius}, the inner and outer I{Soddy} circle radii C{riS}

96 and C{roS}, the sides C{a}, C{b} and C{c} and semi-perimeter C{s} of a triangle,

97 all in C{meter} conventionally.

98

99 @note: C{Circumradius} C{cR} and outer I{Soddy} radius C{roS} may be C{INF}.

100 '''

101 _Names_ = ('rA', 'rB', 'rC', 'cR', _rIn_, 'riS', 'roS', _a_, _b_, _c_, _s_)

102 _Units_ = ( Meter,) * len(_Names_)

103

104

105 class Soddy4Tuple(_NamedTuple):

106 '''4-Tuple C{(radius, center, deltas, outer)} with C{radius} and (trilaterated)

107 C{center} of the I{inner} I{Soddy} circle and the radius of the C{outer}

108 I{Soddy} circle. The C{center} is I{un}ambiguous if C{deltas} is C{None},

109 otherwise C{center} is the mean and C{deltas} the differences of the

110 L{pygeodesy.trilaterate3d2} results.

111

112 @note: The outer I{Soddy} radius C{outer} may be C{INF}.

113 '''

114 _Names_ = (_radius_, _center_, _deltas_, _outer_)

115 _Units_ = ( Radius, _Pass, _Pass, Radius)

116

117

118 def circin6(point1, point2, point3, eps=EPS4, useZ=True):

119 '''Return the radius and center of the I{inscribed} aka I{Incircle} of

120 a (2- or 3-D) triangle.

121

122 @arg point1: First point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

123 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

124 @arg point2: Second point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

125 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

126 @arg point3: Third point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

127 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

128 @kwarg eps: Tolerance for function L{pygeodesy.trilaterate3d2} if

129 C{B{useZ} is True} else L{pygeodesy.trilaterate2d2}.

130 @kwarg useZ: If C{True}, use the Z components, otherwise force C{z=INT0} (C{bool}).

131

132 @return: L{Circin6Tuple}C{(radius, center, deltas, cA, cB, cC)}. The

133 C{center} and contact points C{cA}, C{cB} and C{cC}, each an

134 instance of B{C{point1}}'s (sub-)class, are co-planar with

135 the three given points.

136

137 @raise ImportError: Package C{numpy} not found, not installed or older

138 than version 1.10 and C{B{useZ} is True}.

139

140 @raise IntersectionError: Near-coincident or -colinear points or

141 a trilateration or C{numpy} issue.

142

143 @raise TypeError: Invalid B{C{point1}}, B{C{point2}} or B{C{point3}}.

144

145 @see: Functions L{radii11} and L{circum3}, U{Contact Triangle

146 <https://MathWorld.Wolfram.com/ContactTriangle.html>} and

147 U{Incircle<https://MathWorld.Wolfram.com/Incircle.html>}.

148 '''

149 try:

150 return _circin6(point1, point2, point3, eps=eps, useZ=useZ)

151 except (AssertionError, TypeError, ValueError) as x:

152 raise _xError(x, point1=point1, point2=point2, point3=point3)

153

154

155 def _circin6(point1, point2, point3, eps=EPS4, useZ=True, dLL3=False, **Vector_kwds):

156 # (INTERNAL) Radius, center, deltas, 3 contact points

157

158 def _fraction(r, a):

159 return (r / a) if a > EPS0 else _0_5

160

161 def _contact2(a, p2, r2, p3, r3, V, V_kwds):

162 c = p2.intermediateTo(p3, _fraction(r2, a)) if r2 > r3 else \

163 p3.intermediateTo(p2, _fraction(r3, a))

164 C = V(c.x, c.y, c.z, **V_kwds)

165 return c, C

166

167 t, p1, p2, p3 = _radii11ABC(point1, point2, point3, useZ=useZ)

168 V, r1, r2, r3 = point1.classof, t.rA, t.rB, t.rC

169

170 c1, cA = _contact2(t.a, p2, r2, p3, r3, V, _xkwds(Vector_kwds, name=_cA_))

171 c2, cB = _contact2(t.b, p3, r3, p1, r1, V, _xkwds(Vector_kwds, name=_cB_))

172 c3, cC = _contact2(t.c, p1, r1, p2, r2, V, _xkwds(Vector_kwds, name=_cC_))

173

174 r = t.rIn

175 c, d = _tricenter3d2(c1, r, c2, r, c3, r, eps=eps, useZ=useZ, dLL3=dLL3,

176 **_xkwds(Vector_kwds, Vector=V, name=circin6.__name__))

177 return Circin6Tuple(r, c, d, cA, cB, cC)

178

179

180 def circum3(point1, point2, point3, circum=True, eps=EPS4, useZ=True):

181 '''Return the radius and center of the smallest circle I{through} or

182 I{containing} three (2- or 3-D) points.

183

184 @arg point1: First point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple} or

185 C{Vector4Tuple}).

186 @arg point2: Second point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple} or

187 C{Vector4Tuple}).

188 @arg point3: Third point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple} or

189 C{Vector4Tuple}).

190 @kwarg circum: If C{True} return the C{circumradius} and C{circumcenter}

191 always, ignoring the I{Meeus}' Type I case (C{bool}).

192 @kwarg eps: Tolerance for function L{pygeodesy.trilaterate3d2} if C{B{useZ}

193 is True} else L{pygeodesy.trilaterate2d2}.

194 @kwarg useZ: If C{True}, use the Z components, otherwise force C{z=INT0} (C{bool}).

195

196 @return: A L{Circum3Tuple}C{(radius, center, deltas)}. The C{center}, an

197 instance of B{C{point1}}'s (sub-)class, is co-planar with the three

198 given points.

199

200 @raise ImportError: Package C{numpy} not found, not installed or older

201 than version 1.10 and C{B{useZ} is True}.

202

203 @raise IntersectionError: Near-coincident or -colinear points or

204 a trilateration or C{numpy} issue.

205

206 @raise TypeError: Invalid B{C{point1}}, B{C{point2}} or B{C{point3}}.

207

208 @see: Functions L{pygeodesy.circum4_} and L{pygeodesy.meeus2} and Meeus, J.

209 U{I{Astronomical Algorithms}<http://www.Agopax.IT/Libri_astronomia/pdf/

210 Astronomical%20Algorithms.pdf>}, 2nd Ed. 1998, page 127ff, U{circumradius

211 <https://MathWorld.Wolfram.com/Circumradius.html>} and U{circumcircle

212 <https://MathWorld.Wolfram.com/Circumcircle.html>}.

213 '''

214 try:

215 p1 = _otherV3d(useZ=useZ, point1=point1)

216 return _circum3(p1, point2, point3, circum=circum, eps=eps, useZ=useZ,

217 clas=point1.classof)

218 except (AssertionError, TypeError, ValueError) as x:

219 raise _xError(x, point1=point1, point2=point2, point3=point3, circum=circum)

220

221

222 def _circum3(p1, point2, point3, circum=True, eps=EPS4, useZ=True, dLL3=False,

223 clas=Vector3d, **clas_kwds): # in .latlonBase

224 # (INTERNAL) Radius, center, deltas

225 r, d, p2, p3 = _meeus4(p1, point2, point3, circum=circum, useZ=useZ,

226 clas=clas, **clas_kwds)

227 if d is None: # Meeus' Type II or circum=True

228 kwds = _xkwds(clas_kwds, eps=eps, Vector=clas, name=circum3.__name__)

229 c, d = _tricenter3d2(p1, r, p2, r, p3, r, useZ=useZ, dLL3=dLL3, **kwds)

230 else: # Meeus' Type I

231 c, d = d, None

232 return Circum3Tuple(r, c, d)

233

234

235 def circum4_(*points, **useZ_Vector_and_kwds):

236 '''Best-fit a sphere through three or more (3-D) points.

237

238 @arg points: The points (each a C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

239 or C{Vector4Tuple}).

240 @kwarg useZ_Vector_and_kwds: Keyword arguments C{B{useZ}=True} (C{bool})

241 to use the Z components, otherwise force all C{z=INT0}, class

242 C{B{Vector}=None} to return the center point with optionally,

243 additional nB{C{Vector}} keyword arguments, otherwise the

244 first B{C{points}}' (sub-)class is used.

245

246 @return: L{Circum4Tuple}C{(radius, center, rank, residuals)} with C{center} an

247 instance of C{B{points}[0]}' (sub-)class or B{C{Vector}} if specified.

248

249 @raise ImportError: Package C{numpy} not found, not installed or older than

250 version 1.10.

251

252 @raise NumPyError: Some C{numpy} issue.

253

254 @raise PointsError: Too few B{C{points}}.

255

256 @raise TypeError: One of the B{C{points}} is invalid.

257

258 @see: Functions L{pygeodesy.circum3} and L{pygeodesy.meeus2}, Jekel, Charles F. U{I{Least

259 Squares Sphere Fit}<https://Jekel.me/2015/Least-Squares-Sphere-Fit/>} Sep 13, 2015,

260 U{Appendix A<https://hdl.handle.net/10019.1/98627>}, U{numpy.linalg.lstsq<https://

261 NumPy.org/doc/stable/reference/generated/numpy.linalg.lstsq.html>} and U{Eberly 6

262 <https://www.sci.Utah.EDU/~balling/FEtools/doc_files/LeastSquaresFitting.pdf>}.

263 '''

264 def _useZ_kwds(useZ=True, **kwds):

265 return useZ, kwds

266

267 n, ps = len2(points)

268 if n < 3:

269 raise PointsError(points=n, txt=_too_(_few_))

270 useZ, kwds = _useZ_kwds(**useZ_Vector_and_kwds)

271

272 A, b = [], []

273 for i, p in enumerate(ps):

274 v = _otherV3d(useZ=useZ, i=i, points=p)

275 A.append(v.times(_2_0).xyz + _1_0_1T)

276 b.append(v.length2)

277

278 with _numpy(circum4_, n=n) as _np:

279 A = _np.array(A).reshape((n, 4))

280 b = _np.array(b).reshape((n, 1))

281 C, R, rk, _ = _np.least_squares4(A, b, rcond=None) # to silence warning

282 C = map2(float, C)

283 R = map2(float, R) # empty if rk < 4 or n <= 4

284

285 n = circum4_.__name__

286 c = Vector3d(*C[:3], name=n)

287 r = Radius(sqrt(fsumf_(C[3], *c.x2y2z2)), name=n)

288

289 c = _nVc(c, **_xkwds(kwds, clas=ps[0].classof, name=n))

290 return Circum4Tuple(r, c, rk, R)

291

292

293 def _iscolinearWith(p, point1, point2, eps=EPS, useZ=True):

294 # (INTERNAL) Check colinear, see L{iscolinearWith} above,

295 # separated to allow callers to embellish any exceptions

296 p1 = _otherV3d(useZ=useZ, point1=point1)

297 p2 = _otherV3d(useZ=useZ, point2=point2)

298 n, _ = _nearestOn2(p, p1, p2, within=False, eps=eps)

299 return n is p1 or n.minus(p).length2 < eps

300

301

302 def meeus2(point1, point2, point3, circum=False, useZ=True):

303 '''Return the radius and I{Meeus}' Type of the smallest circle I{through}

304 or I{containing} three (2- or 3-D) points.

305

306 @arg point1: First point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

307 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

308 @arg point2: Second point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

309 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

310 @arg point3: Third point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

311 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

312 @kwarg circum: If C{True} return the C{circumradius} and C{circumcenter}

313 always, overriding I{Meeus}' Type II case (C{bool}).

314 @kwarg useZ: If C{True}, use the Z components, otherwise force C{z=INT0} (C{bool}).

315

316 @return: L{Meeus2Tuple}C{(radius, Type)}, with C{Type} the C{circumcenter}

317 iff C{B{circum}=True}.

318

319 @raise IntersectionError: Near-coincident or -colinear points, iff C{B{circum}=True}.

320

321 @raise TypeError: Invalid B{C{point1}}, B{C{point2}} or B{C{point3}}.

322

323 @see: Functions L{pygeodesy.circum3} and L{pygeodesy.circum4_} and Meeus, J.

324 U{I{Astronomical Algorithms}<http://www.Agopax.IT/Libri_astronomia/pdf/

325 Astronomical%20Algorithms.pdf>}, 2nd Ed. 1998, page 127ff, U{circumradius

326 <https://MathWorld.Wolfram.com/Circumradius.html>} and U{circumcircle

327 <https://MathWorld.Wolfram.com/Circumcircle.html>}.

328 '''

329 try:

330 A = _otherV3d(useZ=useZ, point1=point1)

331 return _meeus2(A, point2, point3, circum, useZ=useZ, clas=point1.classof)

332 except (TypeError, ValueError) as x:

333 raise _xError(x, point1=point1, point2=point2, point3=point3, circum=circum)

334

335

336 def _meeus2(A, point2, point3, circum, useZ=True, **clas_and_kwds): # in .vector3d

337 # (INTERNAL) Radius and center or Meeus' Type

338 f = _circum3 if circum else _meeus4

339 t = f(A, point2, point3, circum=circum, useZ=useZ, **clas_and_kwds)[:2]

340 return Meeus2Tuple(t)

341

342

343 def _meeus4(A, point2, point3, circum=False, useZ=True, clas=None, **clas_kwds):

344 # (INTERNAL) Radius and Meeus' Type

345 B = p2 = _otherV3d(useZ=useZ, point2=point2)

346 C = p3 = _otherV3d(useZ=useZ, point3=point3)

347

348 a = B.minus(C).length2

349 b = C.minus(A).length2

350 c = A.minus(B).length2

351 if a < b:

352 a, b, A, B = b, a, B, A

353 if a < c:

354 a, c, A, C = c, a, C, A

355

356 if a > EPS02 and (circum or a < (b + c)): # circumradius

357 b = sqrt(b / a)

358 c = sqrt(c / a)

359 R = Fsum(_1_0, b, c) * Fsum(_1_0, b, -c) * Fsum(_1_0, -b, c) * Fsum(_N_1_0, b, c)

360 r = R.fover(a)

361 if r < EPS02:

362 raise IntersectionError(_coincident_ if b < EPS0 or c < EPS0 else (

363 _colinear_ if _iscolinearWith(A, B, C) else _invalid_))

364 r = b * c / sqrt(r)

365 t = None # Meeus' Type II

366 else: # obtuse or right angle at A

367 r = sqrt(a * _0_25) if a > EPS02 else INT0

368 t = B.plus(C).times(_0_5) # Meeus' Type I

369 if clas is not None:

370 t = clas(t.x, t.y, t.z, **_xkwds(clas_kwds, name=meeus2.__name__))

371 return r, t, p2, p3

372

373

374 class _numpy(object): # see also .geodesicw._wargs

375 '''(INTERNAL) Partial C{NumPy} wrapper.

376 '''

377 @contextmanager # <https://www.python.org/dev/peps/pep-0343/> Examples

378 def __call__(self, where, *args, **kwds):

379 '''(INTERNAL) Yield self with any errors raised as L{NumPyError}.

380 '''

381 np = self.np

382 try: # <https://NumPy.org/doc/stable/reference/generated/numpy.seterr.html>

383 e = np.seterr(all=_raise_) # throw FloatingPointError for numpy errors

384 yield self

385 except Exception as x: # mostly FloatingPointError?

386 t = unstr(where, *args, **kwds)

387 raise NumPyError(t, cause=x) # _xError2?

388 finally: # restore numpy error handling

389 np.seterr(**e)

390

391 @Property_RO

392 def array(self):

393 return self.np.array

394

395 @Property_RO

396 def least_squares4(self):

397 '''Linear least-squares function.

398 '''

399 return self.np.linalg.lstsq

400

401 @Property_RO

402 def np(self):

403 '''Import numpy 1.10+ once.

404 '''

405 return _xnumpy(self.__class__, 1, 10)

406

407 def null_space2(self, A, rcond=None):

408 '''Return the C{null_space} and C{rank} of matrix B{C{A}}.

409

410 @see: U{Source<https://docs.SciPy.org/doc/scipy/reference/generated/scipy.linalg.null_space.html>}

411 U{SciPY Cookbook<https://SciPy-Cookbook.ReadTheDocs.io/items/RankNullspace.html>}, U{here

412 <https://NumPy.org/doc/stable/reference/generated/numpy.linalg.svd.html>}, U{here

413 <https://StackOverflow.com/questions/19820921>}, U{here

414 <https://StackOverflow.com/questions/2992947>} and U{here

415 <https://StackOverflow.com/questions/5889142>}.

416 '''

417 def _Error(txt=self.null_space2.__name__, **kwds):

418 return _AssertionError(txt=txt, **kwds)

419

420 np = self.np

421 A = np.array(A)

422 m = max(A.shape)

423 if m != 4: # for this usage

424 raise _Error(shape=m)

425 # if needed, square A, pad with zeros

426 A = np.resize(A, m * m).reshape(m, m)

427# try: # no np.linalg.null_space <https://docs.SciPy.org/doc/>

428# Z = scipy.linalg.null_space(A) # XXX no scipy.linalg?

429# return Z, ...

430# except AttributeError:

431# pass

432 U, S, V = np.linalg.svd(A)

433 s = max(EPS, rcond) if rcond else (EPS * max(U.shape[0], V.shape[1]))

434 t = max(EPS, float(np.max(S) * s)) # abs_tol, rel_tol * largest singular

435 r = int(np.sum(S > t)) # rank

436 if r == 3: # get null_space

437 Z = np.transpose(V[r:])

438 s = map2(int, Z.shape)

439 if s != (m, 1): # bad null_space shape

440 raise _Error(shape=s, m=m)

441 D = A.dot(Z) # near-zeros-vector

442 n = float(np.linalg.norm(D, INF)) # INF = max(fabs(D)), 2 = hypot_(*D)

443 if n > t: # largest exceed tol

444 raise _Error(dot=tuple(D.ravel()), norm=n, tol=t)

445 else: # coincident, colinear, concentric centers, ambiguous, etc.

446 Z = None

447 # del A, S, U, V # release numpy

448 return Z, r

449

450 @Property_RO

451 def pseudo_inverse(self):

452 '''Moore-Penrose pseudo-inverse function.

453 '''

454 return self.np.linalg.pinv

455

456 def real_roots(self, *coeffs):

457 '''Compute the real, non-complex roots of a polynomial.

458 '''

459 np = self.np

460 rs = np.polynomial.polynomial.polyroots(coeffs)

461 return tuple(float(r) for r in rs if not np.iscomplex(r))

462

463_numpy = _numpy() # PYCHOK singleton

464

465

466 def radii11(point1, point2, point3, useZ=True):

467 '''Return the radii of the C{In-}, I{Soddy} and C{Tangent} circles of a

468 (2- or 3-D) triangle.

469

470 @arg point1: First point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

471 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

472 @arg point2: Second point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

473 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

474 @arg point3: Third point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

475 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

476 @kwarg useZ: If C{True}, use the Z components, otherwise force C{z=INT0} (C{bool}).

477

478 @return: L{Radii11Tuple}C{(rA, rB, rC, cR, rIn, riS, roS, a, b, c, s)}.

479

480 @raise TriangleError: Near-coincident or -colinear points.

481

482 @raise TypeError: Invalid B{C{point1}}, B{C{point2}} or B{C{point3}}.

483

484 @see: U{Circumradius<https://MathWorld.Wolfram.com/Circumradius.html>},

485 U{Incircle<https://MathWorld.Wolfram.com/Incircle.html>}, U{Soddy

486 Circles<https://MathWorld.Wolfram.com/SoddyCircles.html>} and

487 U{Tangent Circles<https://MathWorld.Wolfram.com/TangentCircles.html>}.

488 '''

489 try:

490 return _radii11ABC(point1, point2, point3, useZ=useZ)[0]

491 except (TypeError, ValueError) as x:

492 raise _xError(x, point1=point1, point2=point2, point3=point3)

493

494

495 def _radii11ABC(point1, point2, point3, useZ=True):

496 # (INTERNAL) Tangent, Circum, Incircle, Soddy radii, sides and semi-perimeter

497 A = _otherV3d(useZ=useZ, point1=point1, NN_OK=False)

498 B = _otherV3d(useZ=useZ, point2=point2, NN_OK=False)

499 C = _otherV3d(useZ=useZ, point3=point3, NN_OK=False)

500

501 a = B.minus(C).length

502 b = C.minus(A).length

503 c = A.minus(B).length

504

505 S = Fsum(a, b, c) * _0_5

506 s = float(S) # semi-perimeter

507 if s > EPS0:

508 rs = float(S - a), float(S - b), float(S - c)

509 r3, r2, r1 = sorted(rs) # r3 <= r2 <= r1

510 if r3 > EPS0: # and r2 > EPS0 and r1 > EPS0

511 r3_r1 = r3 / r1

512 r3_r2 = r3 / r2

513 # t = r1 * r2 * r3 * (r1 + r2 + r3)

514 # = r1**2 * r2 * r3 * (1 + r2 / r1 + r3 / r1)

515 # = (r1 * r2)**2 * (r3 / r2) * (1 + r2 / r1 + r3 / r1)

516 t = r3_r2 * fsum1f_(_1_0, r2 / r1, r3_r1) # * (r1 * r2)**2

517 if t > EPS02:

518 t = sqrt(t) * _2_0 # * r1 * r2

519 # d = r1 * r2 + r2 * r3 + r3 * r1

520 # = r1 * (r2 + r2 * r3 / r1 + r3)

521 # = r1 * r2 * (1 + r3 / r1 + r3 / r2)

522 d = fsum1f_(_1_0, r3_r1, r3_r2) # * r1 * r2

523 # si/o = r1 * r2 * r3 / (r1 * r2 * (d +/- t))

524 # = r3 / (d +/- t)

525 si = r3 / (d + t)

526 so = (r3 / (d - t)) if d > t else INF

527 # ci = sqrt(r1 * r2 * r3 / s)

528 # = r1 * sqrt(r2 * r3 / r1 / s)

529 ci = r1 * sqrt(r2 * r3_r1 / s)

530 # co = a * b * c / (4 * ci * s)

531 t = ci * s * _4_0

532 co = (a * b * c / t) if t > EPS0 else INF

533 r1, r2, r3 = rs # original order

534 t = Radii11Tuple(r1, r2, r3, co, ci, si, so, a, b, c, s)

535 return t, A, B, C

536

537 raise TriangleError(_near_(_coincident_) if min(a, b, c) < EPS0 else (

538 _colinear_ if _iscolinearWith(A, B, C) else _invalid_))

539

540

541 def soddy4(point1, point2, point3, eps=EPS4, useZ=True):

542 '''Return the radius and center of the C{inner} I{Soddy} circle of a

543 (2- or 3-D) triangle.

544

545 @arg point1: First point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

546 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

547 @arg point2: Second point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

548 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

549 @arg point3: Third point (C{Cartesian}, L{Vector3d}, C{Vector3Tuple},

550 C{Vector4Tuple} or C{Vector2Tuple} if C{B{useZ}=False}).

551 @kwarg eps: Tolerance for function L{pygeodesy.trilaterate3d2} if

552 C{B{useZ} is True} otherwise L{pygeodesy.trilaterate2d2}.

553 @kwarg useZ: If C{True}, use the Z components, otherwise force C{z=INT0} (C{bool}).

554

555 @return: L{Soddy4Tuple}C{(radius, center, deltas, outer)}. The C{center},

556 an instance of B{C{point1}}'s (sub-)class, is co-planar with the

557 three given points. The C{outer} I{Soddy} radius may be C{INF}.

558

559 @raise ImportError: Package C{numpy} not found, not installed or older

560 than version 1.10 and C{B{useZ} is True}.

561

562 @raise IntersectionError: Near-coincident or -colinear points or

563 a trilateration or C{numpy} issue.

564

565 @raise TypeError: Invalid B{C{point1}}, B{C{point2}} or B{C{point3}}.

566

567 @see: Functions L{radii11} and L{circum3} and U{Soddy Circles

568 <https://MathWorld.Wolfram.com/SoddyCircles.html>}.

569 '''

570 t, p1, p2, p3 = _radii11ABC(point1, point2, point3, useZ=useZ)

571

572 r = t.riS

573 c, d = _tricenter3d2(p1, t.rA + r,

574 p2, t.rB + r,

575 p3, t.rC + r, eps=eps, useZ=useZ,

576 Vector=point1.classof, name=soddy4.__name__)

577 return Soddy4Tuple(r, c, d, t.roS)

578

579

580 def _tricenter3d2(p1, r1, p2, r2, p3, r3, eps=EPS4, useZ=True, dLL3=False, **kwds):

581 # (INTERNAL) Trilaterate and disambiguate the 3-D center

582 d, kwds = None, _xkwds(kwds, eps=eps, coin=True)

583 if useZ and p1.z != p2.z != p3.z: # ignore z if all match

584 a, b = _trilaterate3d2(p1, r1, p2, r2, p3, r3, **kwds)

585 if a is b: # no unambiguity

586 c = a # == b

587 else:

588 c = a.plus(b).times(_0_5) # mean

589 if not a.isconjugateTo(b, minum=0, eps=eps):

590 if dLL3: # deltas as (lat, lon, height)

591 a = a.toLatLon()

592 b = b.toLatLon()

593 d = LatLon3Tuple(b.lat - a.lat,

594 b.lon - a.lon,

595 b.height - a.height, name=_deltas_)

596 else:

597 d = b.minus(a) # vectorial deltas

598 else:

599 if useZ: # pass z to Vector if given

600 kwds = _xkwds(kwds, z=p1.z)

601 c = _trilaterate2d2(p1.x, p1.y, r1,

602 p2.x, p2.y, r2,

603 p3.x, p3.y, r3, **kwds)

604 return c, d

605

606

607 def _trilaterate2d2(x1, y1, radius1, x2, y2, radius2, x3, y3, radius3,

608 coin=False, eps=None,

609 Vector=None, **Vector_kwds):

610 # (INTERNAL) Trilaterate three circles, see L{pygeodesy.trilaterate2d2}

611

612 def _abct4(x1, y1, r1, x2, y2, r2):

613 a = x2 - x1

614 b = y2 - y1

615 t = _tri3near2far(r1, r2, hypot(a, b), coin)

616 c = _0_0 if t else (hypot2_(r1, x2, y2) - hypot2_(r2, x1, y1))

617 return a, b, c, t

618

619 def _astr(**kwds): # kwds as (name=value, ...) strings

620 return Fmt.PAREN(_COMMASPACE_(*(Fmt.EQUALg(*t) for t in kwds.items())))

621

622 r1 = Radius_(radius1=radius1)

623 r2 = Radius_(radius2=radius2)

624 r3 = Radius_(radius3=radius3)

625

626 a, b, c, t = _abct4(x1, y1, r1, x2, y2, r2)

627 if t:

628 raise IntersectionError(_and(_astr(x1=x1, y1=y1, radius1=r1),

629 _astr(x2=x2, y2=y2, radius2=r2)), txt=t)

630

631 d, e, f, t = _abct4(x2, y2, r2, x3, y3, r3)

632 if t:

633 raise IntersectionError(_and(_astr(x2=x2, y2=y2, radius2=r2),

634 _astr(x3=x3, y3=y3, radius3=r3)), txt=t)

635

636 _, _, _, t = _abct4(x3, y3, r3, x1, y1, r1)

637 if t:

638 raise IntersectionError(_and(_astr(x3=x3, y3=y3, radius3=r3),

639 _astr(x1=x1, y1=y1, radius1=r1)), txt=t)

640

641 q = (a * e - b * d) * _2_0

642 if isnear0(q):

643 t = _no_(_intersection_)

644 raise IntersectionError(_and(_astr(x1=x1, y1=y1, radius1=r1),

645 _astr(x2=x2, y2=y2, radius2=r2),

646 _astr(x3=x3, y3=y3, radius3=r3)), txt=t)

647 t = Vector2Tuple((c * e - b * f) / q,

648 (a * f - c * d) / q, name=trilaterate2d2.__name__)

649

650 if eps and eps > 0: # check distances to center vs radius

651 for x, y, r in ((x1, y1, r1), (x2, y2, r2), (x3, y3, r3)):

652 d = hypot(x - t.x, y - t.y)

653 e = fabs(d - r)

654 if e > eps:

655 t = _and(Float(delta=e).toRepr(), r.toRepr(),

656 Float(distance=d).toRepr(), t.toRepr())

657 raise IntersectionError(t, txt=Fmt.exceeds_eps(eps))

658

659 if Vector is not None:

660 t = Vector(t.x, t.y, **_xkwds(Vector_kwds, name=t.name))

661 return t

662

663

664 def _trilaterate3d2(c1, r1, c2, r2, c3, r3, eps=EPS, coin=False,

665 **clas_Vector_and_kwds):

666 # (INTERNAL) Intersect three spheres or circles, see function

667 # L{pygeodesy.trilaterate3d2}, separated to allow callers to

668 # embellish exceptions, like C{FloatingPointError}s from C{numpy}

669

670 def _F3d2(F):

671 # map numpy 4-vector to floats tuple and Vector3d

672 T = map2(float, F)

673 return T, Vector3d(*T[1:])

674

675 def _N3(t01, x, z):

676 # compute x, y and z and return as B{C{clas}} or B{C{Vector}}

677 v = x.plus(z.times(t01))

678 n = trilaterate3d2.__name__

679 return _nVc(v, **_xkwds(clas_Vector_and_kwds, name=n))

680

681 c2 = _otherV3d(center2=c2, NN_OK=False)

682 c3 = _otherV3d(center3=c3, NN_OK=False)

683 rs = (r1, Radius_(radius2=r2, low=EPS),

684 Radius_(radius3=r3, low=EPS))

685

686 # get matrix A[3 x 4], its pseudo-inverse and null_space Z

687 A = [(_1_0_1T + c.times(_N_2_0).xyz) for c in (c1, c2, c3)]

688 with _numpy(trilaterate3d2, A=A, eps=eps) as _np:

689 Z, _ = _np.null_space2(A, eps)

690 if Z is not None:

691 Z, z = _F3d2(Z) # [4 x 1]

692 z2 = z.length2

693 A = _np.pseudo_inverse(A) # [4 x 3]

694 bs = [c.length2 for c in (c1, c2, c3)]

695 # perturbe radii and vector b slightly by eps and eps * 4

696 for p in _tri5perturb(eps, min(rs)):

697 b = [((r + p)**2 - b) for r, b in zip(rs, bs)] # [3 x 1]

698 X, x = _F3d2(A.dot(b))

699 # quadratic polynomial, coefficients ordered (^0, ^1, ^2)

700 t = _np.real_roots(fdot(X, _N_1_0, *x.xyz),

701 fdot(Z, _N_0_5, *x.xyz) * _2_0, z2)

702 if t:

703 v = _N3(t[0], x, z)

704 if len(t) < 2: # one intersection

705 t = v, v

706 elif fabs(t[0] - t[1]) < eps: # abutting

707 t = v, v

708 else: # "lowest" intersection first (to avoid test failures)

709 u = _N3(t[1], x, z)

710 t = (u, v) if u.x < v.x else (v, u)

711 return t

712

713 # coincident, concentric, colinear, too distant, no intersection:

714 # create the explanation and and throw an IntersectionError

715

716 def _no_intersection(coin):

717 t = _no_(_intersection_)

718 if coin:

719 def _reprs(*crs):

720 return _and(*map(repr, crs))

721

722 r = repr(r1) if r1 == r2 == r3 else _reprs(r1, r2, r3)

723 t = _SPACE_(t, _of_, _reprs(c1, c2, c3), _with_, _radius_, r)

724 elif Z is None:

725 t = _COMMASPACE_(t, _no_(_numpy.null_space2.__name__))

726 return t

727

728 t = _tri4near2far(c1, r1, c2, r2, coin) or \

729 _tri4near2far(c1, r1, c3, r3, coin) or \

730 _tri4near2far(c2, r2, c3, r3, coin) or (

731 _colinear_ if _iscolinearWith(c1, c2, c3, eps=eps) else

732 _no_intersection(coin))

733 raise IntersectionError(t, txt=None)

734

735

736 def _tri3near2far(r1, r2, h, coin):

737 # check for near-coincident/-concentric or too distant spheres/circles

738 return _too_(Fmt.distant(h)) if h > (r1 + r2) else (_near_(

739 _coincident_ if coin else _concentric_) if h < fabs(r1 - r2) else NN)

740

741

742 def _tri4near2far(c1, r1, c2, r2, coin):

743 # check for near-coincident/-concentric or too distant spheres/circles

744 t = _tri3near2far(r1, r2, c1.minus(c2).length, coin)

745 return _SPACE_(c1.name, _and_, c2.name, t) if t else NN

746

747

748 def _tri5perturb(eps, r):

749 # perturb the radii to handle this corner case

750 # <https://GitHub.com/mrJean1/PyGeodesy/issues/49>

751 yield _0_0

752 if eps and eps > 0:

753 p = max(eps, EPS)

754 yield p

755 m = min(p, r)

756 yield -m

757 q = max(eps * _4_0, _EPS4e8)

758 if q > p:

759 yield q

760 q = min(q, r)

761 if q > m:

762 yield -q

763

764# **) MIT License

765#

766# Copyright (C) 2016-2023 -- mrJean1 at Gmail -- All Rights Reserved.

767#

768# Permission is hereby granted, free of charge, to any person obtaining a

769# copy of this software and associated documentation files (the "Software"),

770# to deal in the Software without restriction, including without limitation

771# the rights to use, copy, modify, merge, publish, distribute, sublicense,

772# and/or sell copies of the Software, and to permit persons to whom the

773# Software is furnished to do so, subject to the following conditions:

774#

775# The above copyright notice and this permission notice shall be included

776# in all copies or substantial portions of the Software.

777#

778# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS

779# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

780# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL

781# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR

782# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,

783# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

784# OTHER DEALINGS IN THE SOFTWARE.