Aller au contenu

« Utilisateur:Yannig/PdD » : différence entre les versions

Une page de Wikipédia, l'encyclopédie libre.
Contenu supprimé Contenu ajouté
Yannig (discuter | contributions)
Nouvelle page : Traduction en cours des additions de Minkowski thumb|Minkowski sum ''A'' + ''B'' thumb|''B'' [[Image:Minkowski-sumex1.s…
 
Yannig (discuter | contributions)
Aucun résumé des modifications
Ligne 1 : Ligne 1 :
Traduction en cours des additions de Minkowski
Traduction en cours des additions de Minkowski


[[Image:Minkowski-sumex4.svg|thumb|Somme Minkowski ''A'' + ''B'']]
[[Image:Minkowski-sumex2.svg|thumb|''B'']]
[[Image:Minkowski-sumex1.svg|thumb|''A'']]

En [[géométrie]], '''l'addition de Mikowski''' — également connu sous le nom de dilatation — de deux ensembles ''A'' et ''B'' en [[espace Euclidien]] est le résultat de l'addition de tous les éléments de ''A'' avec tous les éléments de ''B'', cad l'ensemble

: <math>A + B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}.</math>

Prenons un exemple avec deux 2-simplexes (triangles en espace 2D), représentés par les points suivants pour

:''A'' = { (1, 0), (0, 1), (0, −1)}

et

:''B'' = { (0, 0), (1, 1), (1, −1)},

alors la somme de Minkowski est

:''A'' + ''B'' = { (1, 0), (2, 1), (2, −1), (0, 1), (1, 2), (1, 0), (0, −1), (1, 0), (1, −2)}, figure qui ressemble à un [[hexagone]] avec trois répétitions du point (1,0).

Ceci défini une [[opération binaire]] appelé '''addition de Minkowski''', du nom de son inventeur [[Hermann Minkowski]]. Elle est obtenue en respectant le théorème de Minkoswki, sous la forme

:''C'' + ''C'' = 2''C''

Soit un [[ensemble convexe]]

for a [[Convex set|convex]] symmetric set containing 0, where the left-hand side is the Minkowski sum and the right-hand side the [[homothety|enlargement]] by a factor of 2.

This operation is sometimes called (somewhat inappropriately) the ''convolution'' of the two sets. The actual [[convolution]] of the [[indicator function]]s of the set will be a [[function (mathematics)|function]] with the same [[support (mathematics)|support]] as the Minkowski sum.

Minkowski addition is also called the binary '''dilation''' of A by B.

==Essential Minkowski sum==
There is also a notion of the '''essential Minkowski sum''' +<sub>e</sub> of two subsets of Euclidean space. Note that the usual Minkowski sum can be written as

:<math>A + B = \{ z \in \mathbb{R}^{n} | A \cap (z - B) \neq \emptyset \}.</math>

Thus, the '''essential Minkowski sum''' is defined by

:<math>A +_{\mathrm{e}} B = \{ z \in \mathbb{R}^{n} | \mu (A \cap (z - B)) > 0 \},</math>

where ''μ'' denotes ''n''-dimensional [[Lebesgue measure]]. The reason for the term "essential" is the following property of [[indicator function]]s: while

:<math>1_{A + B} (z) = \sup_{x \in \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x),</math>

it can be seen that

:<math>1_{A +_{\mathrm{e}} B} (z) = \mathop{\mathrm{ess\,sup}}_{x \in \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x),</math>

where ess sup denotes the [[essential supremum]].

==Applications==

Minkowski addition plays a central role in [[mathematical morphology]]. It arises in the [[brush-and-stroke paradigm]] of [[2D computer graphics]] (pioneered by [[Donald E. Knuth]] in [[Metafont]]), and as the [[solid sweep]] operation of [[3D computer graphics]].

===Motion planning===
Minkowski sums are used in [[motion planning]] of an object among obstacles. they are used for the computation of the [[configuration space]], which is the set of all admissible positions of the object. In the simple model of translational motion of an object in the plane, where the position of an object may be uniquely specified by the position of a fixed point of this object, the configuration space are the Minkowski sum of the set of obstacles and the movable object.

===NC machining===

In [[NC machining]], the programming of the NC tool exploits the fact that the Minkowski sum of the [[cutting piece]] with its trajectory gives the shape of the cut in the material.

==Algorithms for computing Minkowski sums==
===Planar case===
====Two convex polygons in the plane====
For two [[convex polygon]]s P and Q in the plane with m and n vertices, their Minkowski sum is a convex polygon with at most m + n vertices and may be computed in time O (m + n) by a very simple procedure, which may be informally described as follows. Assume that the edges of a polygon are given the direction, say, counterclockwise, along the polygon boundary. Then it is easily seen that these edges of the convex polygon are ordered by [[polar angle]]. Let us [[Merge algorithm|merge the ordered sequences]] of the directed edges from P and Q into a single ordered sequence S. Imagine that these edges are solid [[arrow]]s which can be moved freely while keeping them parallel to their original direction. Assemble these arrows in the order of the sequence S by attaching the tail of the next arrow to the head of the previous arrow. It turns out that the resulting [[polygonal chain]] will in fact be a convex polygon which is the Minkowski sum of P and Q.

====Other====
If one polygon is convex and another one is not, the complexity of their Minkowski sum is O(nm). If both of them are nonconvex, their Minkowski sum complexity is O((mn)<sup>2</sup>)

==See also==

* [[Interval arithmetic]]
* [[Zonotope]]
* [[Parallel curve]]
* [[Erosion (morphology)|Erosion]]

==References==

* {{cite journal | last=Gardner | first=Richard J. | title=The Brunn-Minkowski inequality | journal=[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]] (N.S.) | volume=39 | issue=3 | year=2002 | pages=355&ndash;405 (electronic) | doi=10.1090/S0273-0979-02-00941-2 }}

==External links==
* [http://www.cgal.org/Pkg/MinkowskiSum2 Minkowski Sums], in [[Computational Geometry Algorithms Library]]
* [http://demonstrations.wolfram.com/TheMinkowskiSumOfTwoTriangles/ The Minkowski Sum of Two Triangles] and [http://demonstrations.wolfram.com/TheMinkowskiSumOfADiskAndAPolygon/ The Minkowski Sum of a Disk and a Polygon] by George Beck, [[The Wolfram Demonstrations Project]].

[[Category:Convex geometry]]
[[Category:Euclidean geometry]]
[[Category:Binary operations]]
[[Category:Digital geometry]]
[[Category:Geometric algorithms]]

[[de:Minkowski-Summe]]
[[eo:Sumo de Minkowski]]
[[fr:Somme de Minkowski]]
[[it:Somma di Minkowski]]
[[pl:Sumy Minkowskiego]]
[[ru:Сумма Минковского]]
[[zh:閔可夫斯基和]]

<!--
[[Image:Minkowski-sumex4.svg|thumb|Minkowski sum ''A'' + ''B'']]
[[Image:Minkowski-sumex4.svg|thumb|Minkowski sum ''A'' + ''B'']]
[[Image:Minkowski-sumex2.svg|thumb|''B'']]
[[Image:Minkowski-sumex2.svg|thumb|''B'']]
Ligne 97 : Ligne 197 :
[[ru:Сумма Минковского]]
[[ru:Сумма Минковского]]
[[zh:閔可夫斯基和]]
[[zh:閔可夫斯基和]]
-->

Version du 19 mars 2009 à 18:20

Traduction en cours des additions de Minkowski

Somme Minkowski A + B
B
A

En géométrie, l'addition de Mikowski — également connu sous le nom de dilatation — de deux ensembles A et B en espace Euclidien est le résultat de l'addition de tous les éléments de A avec tous les éléments de B, cad l'ensemble

Prenons un exemple avec deux 2-simplexes (triangles en espace 2D), représentés par les points suivants pour

A = { (1, 0), (0, 1), (0, −1)}

et

B = { (0, 0), (1, 1), (1, −1)},

alors la somme de Minkowski est

A + B = { (1, 0), (2, 1), (2, −1), (0, 1), (1, 2), (1, 0), (0, −1), (1, 0), (1, −2)}, figure qui ressemble à un hexagone avec trois répétitions du point (1,0).

Ceci défini une opération binaire appelé addition de Minkowski, du nom de son inventeur Hermann Minkowski. Elle est obtenue en respectant le théorème de Minkoswki, sous la forme

C + C = 2C

Soit un ensemble convexe

for a convex symmetric set containing 0, where the left-hand side is the Minkowski sum and the right-hand side the enlargement by a factor of 2.

This operation is sometimes called (somewhat inappropriately) the convolution of the two sets. The actual convolution of the indicator functions of the set will be a function with the same support as the Minkowski sum.

Minkowski addition is also called the binary dilation of A by B.

Essential Minkowski sum

There is also a notion of the essential Minkowski sum +e of two subsets of Euclidean space. Note that the usual Minkowski sum can be written as

Thus, the essential Minkowski sum is defined by

where μ denotes n-dimensional Lebesgue measure. The reason for the term "essential" is the following property of indicator functions: while

it can be seen that

where ess sup denotes the essential supremum.

Applications

Minkowski addition plays a central role in mathematical morphology. It arises in the brush-and-stroke paradigm of 2D computer graphics (pioneered by Donald E. Knuth in Metafont), and as the solid sweep operation of 3D computer graphics.

Motion planning

Minkowski sums are used in motion planning of an object among obstacles. they are used for the computation of the configuration space, which is the set of all admissible positions of the object. In the simple model of translational motion of an object in the plane, where the position of an object may be uniquely specified by the position of a fixed point of this object, the configuration space are the Minkowski sum of the set of obstacles and the movable object.

NC machining

In NC machining, the programming of the NC tool exploits the fact that the Minkowski sum of the cutting piece with its trajectory gives the shape of the cut in the material.

Algorithms for computing Minkowski sums

Planar case

Two convex polygons in the plane

For two convex polygons P and Q in the plane with m and n vertices, their Minkowski sum is a convex polygon with at most m + n vertices and may be computed in time O (m + n) by a very simple procedure, which may be informally described as follows. Assume that the edges of a polygon are given the direction, say, counterclockwise, along the polygon boundary. Then it is easily seen that these edges of the convex polygon are ordered by polar angle. Let us merge the ordered sequences of the directed edges from P and Q into a single ordered sequence S. Imagine that these edges are solid arrows which can be moved freely while keeping them parallel to their original direction. Assemble these arrows in the order of the sequence S by attaching the tail of the next arrow to the head of the previous arrow. It turns out that the resulting polygonal chain will in fact be a convex polygon which is the Minkowski sum of P and Q.

Other

If one polygon is convex and another one is not, the complexity of their Minkowski sum is O(nm). If both of them are nonconvex, their Minkowski sum complexity is O((mn)2)

See also

References

External links

fr:Somme de Minkowski