M.	Neagu
	Equivalence of Arrangements of Curves
	12th Canadian Conference on Computational Geometry CCCG 2000
	résumé ou .ps.gz
M.	Neagu, E. Calcoen, B. Lacolle
	Bézier Curves: Topological Convergence of the Control Polygon
	5th International Conference on Mathematical Methods for Curves and Surfaces Oslo CAGD 2000
	résumé ou .ps.gz
M.	Neagu, B. Lacolle
	Convergence of Approximations for Arrangements of Curves
	4th International Conference on Curves and Surfaces Saint-Malo 1999
	Curve and Surface Design: Saint-Malo 1999, Pierre-Jean Laurent, Paul Sablonnière, and Larry L. Schumaker (eds.), Vanderbilt University Press, Nashville, Tennessee, p 297-306.
	résumé
M.	Neagu
	Polygonal Approximations for Curved Problems: an Application to Arrangements
	Japan Conference on Discrete and Computational Geometry JCDCG98
	Lecture Notes in Computer Science no. 1763, 2000, p. 235-249.
	résumé
M.	Neagu, B. Lacolle
	Computing the Combinatorial Structure of Arrangements of Curves Using Polygonal Approximations
	European Workshop on Computational Geometry CG'98,
	résumé ou .ps.gz
M.	Neagu, B. Lacolle
	Topology-Oriented Convex Hull Algorithm for Objects Bounded by Bézier Curves
	rapport de recherche IMAG RR 1007-M-
	résumé ou .ps.gz
M.	Neagu, B. Lacolle
	Enveloppe convexe d'objets courbes : une approche topologique
	Revue internationale de CFAO et d'informatique graphique, vol. 12, no. 6, 1997, p. 595-612
	résumé

  Equivalence of Arrangements of Curves

For arrangements of hyperplanes in $\R^d$, the notion of equivalence is well understood and presents no ambiguity. Two definitions of it can be found in the literature, one given by Edelsbrunner and the other one given by Grünbaum. Edelsbrunner's definition is based on the position vectors of the faces of an arrangement and it implies the more general definition of Grünbaum, which relies solely on the incidence graphs of the two arrangements.

The two definitions can be naturally extended to arrangements of (simple unbounded or closed) Jordan curves in the plane (we remark that if we want to consider arrangements of Jordan arcs, the only pertinent definition is Grünbaum's one). Nevertheless, these definitions appear to be rather improper in this case, and in Section~2 we give examples showing their limitations.

We intuitively say that two arrangements of curves are equivalent if we can continuously and reversibly deform the partition of the plane defined by one of the sets of curves to obtain the partition of the plane defined by the other one, or if they are obtained one from another by reflection. In Section~3, we give the formal expression of this notion and discuss the relations between it and the two previous definitions.

  Bézier Curves: Topological Convergence of the Control Polygon

In terms of distance (e.g., Hausdorff distance), the control polygon of a B\'ezier curve converges to the curve via the de Casteljau subdivision. This convergence is widely studied in the literature. In this paper, we adopt a different point of view for the convergence problem: We study whether the control polygon preserves the topology of the associated curve. In this purpose, we deal with two main topological features of the B\'ezier curve, the existence of multiple points and the convexity.

  Enveloppe convexe d'objets courbes : une approche topologique

Il existe plusieurs algorithmes de calcul de l'enveloppe convexe d'un polygone simple. Il existe aussi quelques propositions d'algorithmes de calcul, en utilisant des primitives complexes, de l'enveloppe convexe d'objets qui ne sont pas bornés par des segments de droite, mais par des courbes planes suffisamment régulières et convexes par morceaux. Cet article présente une approche différente du problème et un algorithme de calcul de l'enveloppe convexe d'un objet borné par une union de courbes de Bézier de polygones de contrôle convexes.

  Computing the Combinatorial Structure of Arrangements of Curves Using Polygonal Approximations

In this paper, we present a method for computing the incidence graph of an arrangement of curves. The main idea of our approach is to avoid algebraic equations resolution, for the reason that this resolution cannot be performed precisely. To reach our goal, we use two polygonal approximations for each of the curves of the arrangement and we establish sufficient conditions of equivalence for the three arrangements obtained. This provides not only two polygonal arrangements having the same incidence graph as the arrangement of curves, but also an approximation of this last arrangement in terms of distance. The method is made concrete by an algorithm and numerical results and examples are presented.

  Polygonal Approximations for Curved Problems: an Application to Arrangements

The most of the authors who proposed algorithms dealing with curved objects used a set of {\it oracles} allowing to perform basic geometric operations on curves (as computing the intersection of two curves). If the handled curves are algebraic, the oracles involve algebraic equations resolution, and in a geometric computing framework no method of solving algebraic equations is considered available. In this paper, we address the problem of the incidence graph of an arrangement of curves and we propose a method that completely avoids algebraic equations, all the computations to be done concerning linear objects. This will be done via suitable polygonal approximations of the given curves; we start by presenting a ``polygonal'' method in a case where the required polygonal approximations exist by definition, the case of composite B\'ezier curves, and then we show how we can construct these polygonal approximations in the general case of Jordan arcs.

  Convergence of Approximations for Arrangements of Curves

The arrangements of planar objects represent one of the main topics of the computational geometry. The case of linear objects has been widely studied, as well from a theoretical point of view as from a practical one. The arrangements of curves, rising important supplementary difficulties, have also been addressed.

Placing ourselves in a geometric computing framework, we propose an approach which allows reliable computations on arrangements of curves. This approach is based on the use of polygonal approximations for the curves composing the arrangement, and the questions to be answered concern the topological and geometric properties of the approximating arrangement of polygonal lines.

As a first step, we have chosen to deal with composite Bézier curves, the approximating polygonal lines being, in this case, naturally associated to the given curves. We have proven that the arrangement of composite control polygons topologically converges, via de Casteljau subdivision, to the arrangement of curves [3]: We can construct the incidence graph of the arrangement of Bézier curves handling uniquely the polygonal approximations.

In this presentation, we interest in the complementary aspect of the problem, addressing it from a geometric point of view. Namely, we study the convergence, in terms of distance, of a face of the arrangement of polygonal lines to the corresponding face of the arrangement of composite Bézier curves. The main result is that the convergence is achieved with respect to the Hausdorff distance. This allows interesting developments for one of the most important problems related to arrangements, the point location problem. Indeed, the question of the location of a point in the arrangement of composite Bézier curves can then be reduced to the one of its location in the polygonal arrangement.

  Topology-Oriented Convex Hull Algorithm for Objects Bounded by Bézier Curves

There exist many algorithms computing the convex hull of a simple polygon. There also exist some proposals of algorithms computing, using a few complex "oracles", the convex hull of objects bounded not by straight line segments, but by smooth piecewise convex planar curves. The results provided by the existing algorithms are objects approaching the convex hull of the given curved object, the quality of the approximation depending on the accuracy the oracles can be solved with. Solving these oracles implies high-degree algebraic equations resolution.

This paper presents a different approach for the convex hull problem for non-linear objects, placed in a "geometric computation" framework. So, all our discussion is made under the assumption that algebraic equations can not be accurately solved (Chazelle, 1996). To make this approach concrete, we propose an algorithm computing the convex hull of a {\reffontit polycurve}, an union of point-controled parametric curves with simple and convex control polygon. The properties that these parametric curves must fulfill are general; to fix the ideas, we choose the Bézier curves for the presentation of our results.

The method we propose is topology-oriented. The notion of topological convex hull is introduced and we prove that it can be obtained via suitable discretisations of the curved object. Discretisation seems a naïve and expensive approach, but we show that, firstly, the obtained linear object captures all the topological features of the curved one, and secondly, the size of this polygon is reasonable. From a practical point of view, we give a construction method for the mentioned linear object that does not require the resolution of algebraic equations.

Dernière mise à jour : 19.12.2000