CGAL users discussion list

[Marc Alexa <>]

Converting between parametric and implicit representations used to be a topic in CAGD in the 80s-90s. The right keyword for searching is ‘implicitization’. Classic references are:

R. N. Goldman, T. W. Sederberg, and D. C. Anderson. 1984. Vector elimination: A technique for the implicitization, inversion, and intersection of planar parametric rational polynomial curves. <i>Comput. Aided Geom. Des.</i> 1, 4 (December, 1984), 327–356. DOI:https://doi.org/10.1016/0167-8396(84)90020-7

Thomas W. Sederberg. 1984. Planar piecewise algebraic curves. <i>Comput. Aided Geom. Des.</i> 1, 3 (December, 1984), 241–255. DOI:https://doi.org/10.1016/0167-8396(84)90011-6

The case for cubic Bezier curves has been solved, see here: https://www.mn.uio.no/math/english/people/aca/michaelf/papers/implicitize.pdf

Best,

Marc

On 13. Dec 2021, at 04:44, Kevin Morgan ( via cgal-discuss Mailing List) <> wrote:

Ok, please disregard the notes in the previous email about a general implicit bezier form.

I'm still looking for one, if it exists, but other than the fact that U(x) and V(y) exist, the rest of my speculation does not make much sense. 

Kevin

On Fri, Dec 10, 2021 at 8:07 PM Kevin Morgan <> wrote:

Thanks Efi,

Your feedback confirms my thoughts about this. I'm glad that I didn't miss an already existing solution to the problem somewhere.

The beziers for input will be arbitrary svg paths, so nothing that can be pre-calculated. The highest degree would likely be cubic beziers.

I've already run into the topology issues you mentioned in an earlier version of my application that does not use CGAL. Looking at the way bezier intersections are handled in bezier_traits does give me some ideas how to fix it.

Here's some notes on an implicit form for beziers, if anyone else is following along. If anyone reading this actually investigates this, or is aware of an implicit form for beziers, please let me know about it.

I was originally thinking that an implicit form did not exist, or would be hard to derive. The implicit form would have to be t = U(x) == V(y) where U(x) and V(y) are the inverse mapping of the X and Y components of the parametric bezier. 

I'll conjecture that it if it exists, and if it has the same degree as the bezier, it might be U(x) = (x-x0)(x-x1)... and V(y) = (y-y0)((y-y1)... where x[i] and y[i] are the roots of the X(t) and Y(t) components of the bezier polynomial. It would have to be the case for t==0. The roots might be complex, but possibly the expanded coefficients of U and V might be just reals. The quadratic formula or Cardano's formula could be used to find the roots. I know CGAL has a poly root finder. One could back substitute U and V in the original bezier to prove or disprove this conjecture (I haven't done it). 

For Arr_algebraic_segments_traits, there's also the issue of specifying the starting and ending points of the curve, and in the case of a loop, you would need to subdivide the curve into two or more parts to be unambiguous. Anyway, I probably won't use this approach, but it might be viable.

Kevin

On Thu, Dec 9, 2021 at 1:04 AM Efi Fogel <> wrote:

Hi Kevin,

1. The first approach defeats the purpose of the Bezier traits.

They were developed under those constraints, which enabled efficient code.

2. I think that it is possible to convert a Bezier curve to an implicit form, but it's not trivial.

If the degree of the Bezier curve is fixed or at least bounded, then you can find implicit forms (perhaps using tools like sage).

Is it fixed or bounded?

3. Writing your own Bezier traits is, of course, possible, but not trivial.

The complicated functions are make_x_monotone_2() and intersect_2().

4. Reducing the requirements of your application is always a good thing to do, regardless of the difficulties one faces when not doing it.

As you know now, with the Bezier traits you can only obtain approximations of intersection points.

It implies that theoretically the arrangement where real points are replaced with their approximations (and thus slightly shifted) is not always topologically equivalent to the original arrangement.

This may happen very rarely and may not necessarily be a problem.

Efi

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Tue, 7 Dec 2021 at 06:01, Kevin Morgan <> wrote:

Hi All,

I want to connect edges to arbitrary points on a bezier curve.

I've posted previously about using Arr_bezier_curve_traits. I want to use it with Algebraic vertices. which are not supported.

The main issue is that I want to connect edges to points on a Bezier that may not be endpoints.

There are a few ways that I might proceed, and I'd like some feedback from the authors and other users about that.

One approach I can take is to attempt to rework Arr_bezier_curve_traits to support Algebraic vertices. That seems daunting to me, because of the underlying exact representation, but I might be overestimating the difficulty and the issues that can arise. 

Another way, suggested by Efi, is to use Arr_algebraic_segments_traits. The issue with that is that you provide the curves in an implicit form, and Beziers don't have an equivalent implicit form, as far as I can tell. Maybe there's some way to rework it to do what I want. 

Yet another approach would be to just write my own support for Beziers, independent of that class. I'm familiar with the math involved, but not so much with the CGAL framework, and with template metaprogramming, so this would be a bit of a project. And it seems silly to do this if the functionality exists somewhere in the CGAL framework already.

A fourth approach would be to try to work around the issues in my application. Specifically, to replace any bezier segments that have algebraic vertices with new resampled segments that have rational vertices. This would lose information about the original curves. Also, It's not clear how well this would work, because there's not a guarantee about the precision or representation of the intersection points. But I can probably make it work as long as the intersection vertices all agree about the Algebraic to Rational mapping. 

Comments and suggestions are welcome, and feel free to correct me about any errors or misunderstandings I have about any of this.

Thanks,

Kevin

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss