Debian Codegraph @

texmf-dist/doc/latex/tkz-elements/TKZdoc-elements-CMGE.tex

raw
1 \section{Computational Model and Geometric Engine}
2 \subsection{Introduction}
3
4 The package \tkzNamePack{tkz-elements} is not merely a collection of geometric
5 construction commands. It implements a coherent computational geometry engine
6 based on a unified mathematical model.
7
8 This chapter presents the mathematical and computational foundations
9 underlying the package. While most users interact with high-level geometric
10 objects such as \tkzClass{point}, \tkzClass{line}, \tkzClass{circle},
11 \tkzClass{triangle}, or \tkzClass{conic}, all constructions ultimately rely
12 on a compact algebraic core and a carefully designed numerical strategy.
13
14 The purpose of this chapter is threefold:
15
16 \begin{itemize}
17 \item to describe the mathematical model used internally,
18 \item to explain the numerical robustness strategy,
19 \item to clarify the architectural principles governing the engine.
20 \end{itemize}
21
22 This chapter may be read independently as a technical overview of the
23 geometric engine.
24
25 \subsection{The Complex-Plane Model}
26
27 All planar points are represented internally as complex numbers:
28
29 \[
30 z = x + iy,
31 \]
32
33 where \(x\) and \(y\) are real coordinates.
34
35 This choice provides a compact and algebraically coherent framework for
36 geometric computations. Vector addition, subtraction, rotation,
37 and homothety become natural algebraic operations.
38
39 The class \tkzClass{point} therefore has a dual interpretation:
40 it behaves both as a geometric point in the Euclidean plane and as a complex
41 number in the algebraic model. This design avoids maintaining separate
42 vector and complex abstractions and provides a compact, coherent framework
43 for geometric computations.
44
45 The complex-plane representation allows:
46
47 \begin{itemize}
48 \item direct implementation of vector arithmetic,
49 \item concise expressions for rotations and symmetries,
50 \item natural encoding of orientation via complex multiplication,
51 \item simplified determinant and dot-product calculations.
52 \end{itemize}
53
54 The use of complex numbers ensures both elegance and computational efficiency.
55
56 %--------------------------------------------------------------------
57 \subsubsection{The Point Class as a Complex Number}
58 \label{sub:complex_numbers}
59
60 For example,
61 \begin{verbatim}
62 z.A = point(1, 2)
63 z.B = point(1, -1)
64 \end{verbatim}
65 define two point objects whose associated affixes are
66 \[
67 z_A = 1 + 2i,
68 \qquad
69 z_B = 1 - i.
70 \]
71 The notation \verb|z.A| refers to a Lua object stored in table \verb|z|,
72 whereas \(z_A\) denotes its associated complex number.
73
74 \medskip
75 If one prefers to work with standalone variables (without using reserved
76 tables), one may also write:
77 \begin{verbatim}
78 za = point(1, 2)
79 zb = point(1, -1)
80 \end{verbatim}
81 The only difference is organizational: \verb|z.A| is stored in the table
82 \verb|z|, while \verb|za| is a regular Lua variable.
83
84 \medskip
85 The algebraic structure is implemented through Lua metamethods and a small
86 set of class methods, allowing standard operators to perform geometric
87 operations in a natural way.
88
89 %--------------------------------------------------------------------
90 % Metamethods table
91 %--------------------------------------------------------------------
92 \begin{center}
93 \bgroup
94 \catcode`_=12
95 \small
96 \begin{minipage}{\textwidth}
97 \captionof{table}{Point (complex) metamethods.}
98 \begin{tabular}{lll}
99 \toprule
100 \textbf{Metamethod} & \textbf{Application} & \textbf{Result} \\
101 \midrule
102 \tkzMeta{point}{add(z1,z2)} & \verb|z.a + z.b| & affix \\
103 \tkzMeta{point}{sub(z1,z2)} & \verb|z.a - z.b| & affix \\
104 \tkzMeta{point}{unm(z)} & \verb|-z.a| & affix \\
105 \tkzMeta{point}{mul(z1,z2)} & \verb|z.a * z.b| & affix \\
106 \tkzMeta{point}{concat(z1,z2)} & \verb|z.a .. z.b| & dot product (real number) \\
107 \tkzMeta{point}{pow(z1,z2)} & \verb|z.a ^ z.b| & determinant (real number) \\
108 \tkzMeta{point}{div(z1,z2)} & \verb|z.a / z.b| & affix \\
109 \tkzMeta{point}{tostring(z)} & \verb|tostring(z.a)| & TeX-friendly display \\
110 \tkzMeta{point}{tonumber(z)} & \verb|tonumber(z.a)| & affix or \texttt{nil} \\
111 \tkzMeta{point}{eq(z1,z2)} & \verb|z.a == z.b| & boolean \\
112 \bottomrule
113 \end{tabular}
114 \end{minipage}
115 \egroup
116 \end{center}
117
118 %--------------------------------------------------------------------
119 % Methods table
120 %--------------------------------------------------------------------
121 \begin{center}
122 \bgroup
123 \catcode`_=12
124 \small
125 \begin{minipage}{\textwidth}
126 \captionof{table}{Point (complex) class methods.}
127 \begin{tabular}{lll}
128 \toprule
129 \textbf{Method} & \textbf{Application} & \textbf{Result} \\
130 \midrule
131 \tkzMeth{point}{conj()} & \verb|z.a:conj()| & affix (conjugate) \\
132 \tkzMeth{point}{mod()} & \verb|z.a:mod()| & real number (modulus) \\
133 \tkzMeth{point}{abs()} & \verb|z.a:abs()| & real number (modulus) \\
134 \tkzMeth{point}{norm()} & \verb|z.a:norm()| & real number (squared modulus) \\
135 \tkzMeth{point}{arg()} & \verb|z.a:arg()| & real number (argument in radians) \\
136 \tkzMeth{point}{get()} & \verb|z.a:get()| & \verb|re| and \verb|im| (two real numbers) \\
137 \tkzMeth{point}{sqrt()} & \verb|z.a:sqrt()| & affix \\
138 \bottomrule
139 \end{tabular}
140 \end{minipage}
141 \egroup
142 \end{center}
143
144
145 \subsubsection{Example of complex use}
146
147 Let |za = math.cos(a) + i math.sin(a)| .
148 This is obtained from the library by writing
149
150 \begin{mybox}
151 |za = point(math.cos(a),math.sin(a))|.
152 \end{mybox}
153
154 Then |z.B = z.A * za| describes a rotation of point A by an angle |a|.
155
156 \begin{minipage}{.45\textwidth}
157 \begin{verbatim}
158 \directlua{
159 init_elements()
160 z.O = point(0, 0)
161 z.A = point(1, 2)
162 a = math.pi / 6
163 za = point(math.cos(a), math.sin(a))
164 z.B = z.A * za}
165 \begin{tikzpicture}
166 \tkzGetNodes
167 \tkzDrawPoints(O,A,B)
168 \tkzDrawArc[->,delta=0](O,A)(B)
169 \tkzDrawSegments[dashed](O,A O,B)
170 \tkzLabelAngle(A,O,B){$\pi/6$}
171 \end{tikzpicture}
172 \end{verbatim}
173 \end{minipage}
174 \begin{minipage}{.55\textwidth}
175 \directlua{
176 init_elements()
177 z.O = point(0, 0)
178 z.A = point(1, 2)
179 a = math.pi / 6
180 za = point(math.cos(a), math.sin(a))
181 z.B = z.A * za}
182 \begin{center}
183 \begin{tikzpicture}[scale=2]
184 \tkzGetNodes
185 \tkzDrawPoints(O,A,B)
186 \tkzDrawArc[->,delta=0,thick](O,A)(B)
187 \tkzDrawSegments[dashed](O,A O,B)
188 \tkzLabelAngle(A,O,B){$\pi/6$}
189 \end{tikzpicture}
190 \end{center}
191
192 \end{minipage}
193
194 \subsubsection{Point operations (complex)}
195
196 \begin{minipage}{.5\textwidth}
197 \begin{verbatim}
198 \directlua{
199 init_elements()
200 z.o = point(0, 0)
201 z.a = point(1, -1)
202 z.b = point(2, 1)
203 z.bp = -z.b
204 z.c = z.a + z.b
205 z.d = z.a - z.b
206 z.e = z.a * z.b
207 z.f = z.a / z.b
208 z.ap = point.conj(z.a)
209 z.g = z.b * point(math.cos(math.pi / 2),
210 math.sin(math.pi / 2))}
211
212 \begin{tikzpicture}
213 \tkzGetNodes
214 \tkzInit[xmin=-2,xmax=3,ymin=-2,ymax=3]
215 \tkzGrid
216 \tkzDrawSegments(o,a o,b o,c o,e o,b')
217 \tkzDrawSegments(o,f o,g)
218 \tkzDrawSegments[red](a,c b,c b',d a,d)
219 \tkzDrawPoints(a,...,g,o,a',b')
220 \tkzLabelPoints(o,a,b,c,d,e,f,g,a',b')
221 \end{tikzpicture}
222 \end{verbatim}
223 \end{minipage}
224 \begin{minipage}{.5\textwidth}
225 \directlua{
226 init_elements()
227 z.o = point(0, 0)
228 z.a = point(1, -1)
229 z.b = point(2, 1)
230 z.bp = -z.b
231 z.c = z.a + z.b
232 z.d = z.a - z.b
233 z.e = z.a * z.b
234 z.f = z.a / z.b
235 z.ap = point.conj(z.a)
236 z.g = z.b * point(math.cos(math.pi / 2), math.sin(math.pi / 2))}
237
238 \begin{center}
239 \begin{tikzpicture}
240 \tkzGetNodes
241 \tkzInit[xmin=-2,xmax=3,ymin=-2,ymax=3]
242 \tkzGrid
243 \tkzDrawSegments(o,a o,b o,c o,e o,b' o,f o,g)
244 \tkzDrawSegments[red](a,c b,c b',d a,d)
245 \tkzDrawPoints(a,...,g,o,a',b')
246 \tkzLabelPoints(o,a,b,c,d,e,f,g,a',b')
247 \end{tikzpicture}
248 \end{center}
249
250 \end{minipage}
251
252 %--------------------------------------------------------------------
253 \subsubsection{Barycentric Combination}
254 \label{sub:barycentric_combination}
255
256 A fundamental operation in the computational engine is the
257 barycentric combination of points.
258
259 Given points \(z_1, \dots, z_n\) and associated real weights
260 \(w_1, \dots, w_n\), the barycenter is defined as
261
262 \[
263 G = \frac{\sum_{i=1}^{n} w_i z_i}{\sum_{i=1}^{n} w_i}.
264 \]
265
266 Because points are represented as complex numbers,
267 this operation reduces to a weighted linear combination.
268
269 \medskip
270 The internal function \code{barycenter\_} implements this formula
271 directly at the algebraic level. The public interface
272 \code{barycenter} provides a user-friendly wrapper.
273
274 \medskip
275 The barycentric construction is used extensively throughout
276 the package (in triangle centers, homotheties, affine constructions,
277 and other derived geometric algorithms).
278
279 \paragraph{Example.}
280
281
282 \begin{tkzexample}[latex=.35\textwidth]
283 \directlua{
284 init_elements()
285 z.A = point(1, 0)
286 z.B = point(5, -1)
287 z.C = point(2, 5)
288 z.G = tkz.barycenter({z.A, 3}, {z.B, 1}, {z.C, 1})
289 }
290 \begin{center}
291 \begin{tikzpicture}
292 \tkzGetNodes
293 \tkzDrawPolygon(A,B,C)
294 \tkzDrawPoints(A,B,C,G)
295 \tkzLabelPoints(A,B,C,G)
296 \end{tikzpicture}
297 \end{center}
298 \end{tkzexample}
299
300
301 \subsection{Algebraic Primitives and Geometric Operators}
302
303 The computational engine relies on a minimal set of algebraic
304 operations defined on complex numbers.
305
306 These primitives are sufficient to implement all higher-level
307 geometric constructions such as projections, intersections,
308 membership tests, orientation checks, and affine combinations.
309
310 Because points are represented as complex numbers,
311 vector operations reduce to elementary algebra.
312
313 \subsubsection{Vector Arithmetic}
314
315 Given two points represented by complex numbers,
316 vector subtraction is defined naturally:
317
318 \[
319 \overrightarrow{AB} = z_B - z_A.
320 \]
321
322 Addition and scalar multiplication follow directly
323 from complex arithmetic.
324
325 These operations form the basis of translations,
326 midpoints, affine combinations, and homotheties.
327
328
329 \subsubsection{Dot Product}
330 If \(O\) is the origin of the complex plane, then \(\,z_1 .. z_2\) corresponds to the dot product of the vectors \(\overrightarrow{Oz_1}\) and \(\overrightarrow{Oz_2}\).
331
332
333 Given two vectors represented by complex numbers
334 \(z_1 = a+ib\) and \(z_2 = c+id\),
335 their scalar product is defined as
336
337 \[
338 z_1 \verb|..| z_2 = ac + bd.
339 \]
340
341 In the implementation, this quantity is computed
342 using the operator \verb|..|:
343
344 \[
345 z_1 \verb|..| z_2 = ac + bd.
346 \]
347
348 Equivalently, the dot product corresponds to the real part of
349 the product of the first vector and the conjugate of the second:
350
351 \[
352 z_1 \verb|..| z_2
353 =
354 \operatorname{Re}\big(z_1 \,\overline{z_2}\big).
355 \]
356
357 \medskip
358 The dot product plays a central role in planar geometry.
359 It is used for:
360
361 \begin{itemize}
362 \item orthogonality tests,
363 \item projections onto a line,
364 \item distance computations,
365 \item angle measurements.
366 \end{itemize}
367
368 \paragraph{Distance computation.}
369
370 The squared distance between two points \(A\) and \(B\) is
371
372 \[
373 d(A,B)^2 =
374 (z_B - z_A) \verb|..|(z_B - z_A).
375 \]
376
377 \paragraph{Angle measurement.}
378
379 For three points \(A,B,C\), the angle \(\widehat{ABC}\) satisfies
380
381 \[
382 \cos(\theta)
383 =
384 \frac{
385 (z_A - z_B) \verb|..| (z_C - z_B)
386 }{
387 \lVert z_A - z_B \rVert
388 \,
389 \lVert z_C - z_B \rVert
390 }.
391 \]
392
393
394 \subsubsection{Determinant and Oriented Area}
395
396 Given two vectors represented by complex numbers
397 \(z_1 = a+ib\) and \(z_2 = c+id\),
398 their determinant is defined as
399
400 \[
401 \det(z_1, z_2) = ad - bc.
402 \]
403
404 This quantity represents the signed (or oriented) area
405 of the parallelogram generated by the two vectors.
406
407 In the implementation, the determinant is computed
408 using the operator \verb|^|:
409
410 \[
411 z_1 \verb|^| z_2 = ad - bc.
412 \]
413
414 \medskip
415 Given three points \(A,B,C\), the oriented area of triangle \(ABC\)
416 is obtained from
417
418 \[
419 \det(\overrightarrow{AB},\overrightarrow{AC})
420 =
421 (z_B - z_A) \verb|^| (z_C - z_A).
422 \]
423
424 The sign of this quantity determines the orientation:
425
426 \begin{itemize}
427 \item positive: direct (counterclockwise),
428 \item negative: indirect (clockwise),
429 \item zero (up to tolerance): aligned points.
430 \end{itemize}
431
432 This primitive is fundamental for:
433
434 \begin{itemize}
435 \item triangle orientation,
436 \item segment membership tests,
437 \item line intersection,
438 \item inside/outside classification.
439 \end{itemize}
440
441
442 \subsection{Numerical Robustness and Tolerance Control}
443
444
445 Geometric computations rely on floating-point arithmetic and are therefore
446 subject to numerical approximation errors.
447
448 To ensure robustness, all membership and position tests use a configurable
449 tolerance parameter:
450
451 \[
452 \texttt{tkz.epsilon}
453 \]
454
455 This tolerance is applied systematically in:
456
457 \begin{itemize}
458 \item alignment tests,
459 \item intersection detection,
460 \item tangency classification,
461 \item equality comparisons,
462 \item geometric membership tests.
463 \end{itemize}
464
465 Rather than relying on strict equality, the engine evaluates whether
466 a quantity is sufficiently close to zero.
467
468 This strategy guarantees numerical stability across complex constructions.
469
470 \subsection{Geometric Classification Model}
471
472
473 Geometric objects provide a unified classification interface based on
474 three possible states:
475
476 \begin{center}
477 \texttt{"ON"} \quad \texttt{"IN"} \quad \texttt{"OUT"}
478 \end{center}
479
480 This tri-state model applies consistently across:
481
482 \begin{itemize}
483 \item \tkzClass{line}
484 \item \tkzClass{circle}
485 \item \tkzClass{triangle}
486 \item \tkzClass{conic}
487 \end{itemize}
488
489 Membership and region tests are therefore harmonized throughout the system.
490
491 For backward compatibility, boolean interfaces are preserved where necessary,
492 but the internal model is uniformly tri-state.
493
494 \subsection{Degenerate Configurations}
495
496
497 Special care is taken to manage degenerate geometric cases:
498
499 \begin{itemize}
500 \item coincident points,
501 \item concentric circles,
502 \item aligned triangle vertices,
503 \item zero-radius constructions,
504 \item tangency limit cases.
505 \end{itemize}
506
507 Rather than allowing numerical instability, the engine classifies these
508 configurations explicitly.
509
510 This design choice prevents undefined behaviors and improves the reliability
511 of higher-level constructions.
512
513 \subsection{Architecture of the Computational Engine}
514
515 The engine is structured in two layers:
516
517 \subsection*{Primary Computational Functions}
518
519 Low-level functions perform algebraic computations.
520 They are internal and are not part of the public API.
521
522 \subsection*{Object-Oriented Layer}
523
524 Geometric classes provide user-facing methods.
525 These methods call primary functions while ensuring:
526
527 \begin{itemize}
528 \item consistent tolerance handling,
529 \item type safety,
530 \item backward compatibility.
531 \end{itemize}
532
533 This separation maintains clarity between computation and abstraction.
534
535 \subsubsection{Internal Data Tables}
536
537 In Lua, the main data structure is the \emph{table}. It functions both as an array and as a dictionary, allowing you to store sequences of values, associate keys with values, and even represent complex objects. Tables are the foundation for representing geometric structures such as points, lines, and triangles in \tkzNamePack{tkz-elements}.
538
539 \subsubsection{General Use of Tables}
540
541 Tables are the only data structure "container" integrated in Lua.
542 They are associative arrays which associates a key (reference or index) with a value in the form of a field (set) of key/value pairs. Moreover, tables have no fixed size and can grow based on our need dynamically.
543
544 Tables are created using curly braces:
545
546 \begin{mybox}
547 \begin{verbatim}
548 T = {} % T is an empty table.
549 \end{verbatim}
550 \end{mybox}
551
552 In the next example, \code{coords} is a table containing four points written as coordinate strings. Lua indexes tables starting at 1.
553
554 \begin{tkzexample}[latex=0.35\textwidth]
555 \directlua{
556 local coords = { "(0,0)", "(1,0)", "(1,1)", "(0,1)" }
557 for i, pt in ipairs(coords) do
558 tex.print(i .. ": " .. pt)
559 tex.print([[\\]])
560 end}
561 \end{tkzexample}
562
563 You can define a table with unordered indices as follows:
564
565 \begin{mybox}
566 \begin{verbatim}
567 coords = {[1] = "(0,0)", [3] = "(1,1)", [2] = "(1,0)"}
568 \end{verbatim}
569 \end{mybox}
570
571 Accessing an indexed element is straightforward:
572
573 \begin{verbatim}
574 tex.print(coords[3]) --> (1,1)
575 \end{verbatim}
576
577 You can also append new elements:
578
579 \begin{verbatim}
580 coords[4] = "(0,1)"
581 \end{verbatim}
582
583 To iterate over a table with numeric indices in order, use \code{ipairs}:
584
585 \begin{mybox}
586 \begin{verbatim}
587 for i, v in ipairs(coords) do
588 print(i, v)
589 end
590 \end{verbatim}
591 \end{mybox}
592
593 This will print:
594
595 \begin{verbatim}
596 1 (0,0)
597 2 (1,0)
598 3 (1,1)
599 4 (0,1)
600 \end{verbatim}
601
602
603 \textbf{Key–Value Tables.}
604
605 Tables may also use string keys to associate names to values. This is especially useful in geometry for storing attributes like color or label:
606
607 \begin{mybox}
608 \begin{verbatim}
609 properties = {
610 A = "blue",
611 B = "green",
612 C = "red"
613 }
614 properties.D = "black"
615 \end{verbatim}
616 \end{mybox}
617
618 To iterate over all key–value pairs (order not guaranteed), use \code{pairs}:
619
620 \begin{mybox}
621 \begin{verbatim}
622 for k, v in pairs(properties) do
623 print(k, v)
624 end
625 \end{verbatim}
626 \end{mybox}
627
628 \textbf{Deleting an entry.}
629
630 To remove an entry, assign \code{nil} to the corresponding key:
631
632 \begin{verbatim}
633 properties.B = nil
634 \end{verbatim}
635
636
637 \subsubsection{Variable Number of Arguments}
638
639 Tables can also be used to store a variable number of function arguments:
640
641 \begin{mybox}
642 \begin{verbatim}
643 function ReturnTable(...)
644 return table.pack(...)
645 end
646 \end{verbatim}
647 \end{mybox}
648
649 \begin{mybox}
650 \begin{verbatim}
651 function ParamToTable(...)
652 local mytab = ReturnTable(...)
653 for i = 1, mytab.n do
654 print(mytab[i])
655 end
656 end
657
658 ParamToTable("A", "B", "C")
659 \end{verbatim}
660 \end{mybox}
661
662 This technique is useful for collecting points, coordinates, or any variable-length data.
663
664 \textbf{Accessing with Sugar Syntax.}
665
666 In tables with string keys, there are two common syntaxes:
667
668 \begin{itemize}
669 \item \code{properties["A"]} — always valid;
670 \item \code{properties.A} — shorter, but only works with string keys that are valid Lua identifiers (not numbers).
671 \end{itemize}
672
673 \subsubsection{Table \code{z}}
674
675 The most important table in \tkzNamePack{tkz-elements} is \code{z}, used to store geometric points. It is declared as:
676
677 \begin{verbatim}
678 z = {}
679 \end{verbatim}
680
681 Each point is then stored with a named key:
682
683 \begin{mybox}
684 \begin{verbatim}
685 z.M = point(3, 2)
686 \end{verbatim}
687 \end{mybox}
688
689 The object \code{z.M} holds real and imaginary parts, accessible as:
690
691 \begin{verbatim}
692 z.M.re --> 3
693 z.M.im --> 2
694 \end{verbatim}
695
696 If you print it:
697
698 \begin{verbatim}
699 tex.print(tostring(z.M))
700 \end{verbatim}
701
702 You get the complex representation \code{3+2i}.
703
704 Moreover, points in the \code{z} table are not just data—they are objects with methods. You can perform geometric operations directly:
705
706 \begin{verbatim}
707 z.N = z.M:rotation(math.pi / 2)
708 \end{verbatim}
709
710 This makes the \code{z} table central to object creation and manipulation in \tkzNamePack{tkz-elements}.
711
712
713
714 \subsection{Design Principles and Trade-offs}
715
716
717 The design of \tkzNamePack{tkz-elements} follows several guiding principles:
718
719 \begin{itemize}
720 \item Mathematical coherence,
721 \item Minimal algebraic core,
722 \item Numerical robustness,
723 \item Backward compatibility,
724 \item Performance efficiency.
725 \end{itemize}
726
727 The choice of complex representation, tri-state classification,
728 and tolerance-based comparisons results from balancing
729 mathematical rigor and practical usability.