lib2geom-devel

[Lib2geom-devel] Intersection of SBasis

[Krzysztof K. <twe...@gm...>]

Is there a published algorithm for finding the intersections between
two 2D polynomials expressed in SBasis?

Currently 2Geom seems only to contain intersection algorithms for
Bezier, and SBasis are just converted to Bezier to perform the
intersection.

Regards, Krzysztof

Re: [Lib2geom-devel] Intersection of SBasis

[Nathan H. <nj...@nj...>]

The best algorithm for curve-curve intersection is inherently best
done in bezier form (because it is optimal in a convex hull sense).
Conversion is far cheaper than the alternatives (and we tried a
bunch).  Indeed one of my long term projects was to replace all the
sbasis code with the bezier form and simplify the code base.

njh

On Wed, Aug 20, 2014 at 06:43:34PM +0200, Krzysztof Kosiński wrote:
> Is there a published algorithm for finding the intersections between
> two 2D polynomials expressed in SBasis?
> 
> Currently 2Geom seems only to contain intersection algorithms for
> Bezier, and SBasis are just converted to Bezier to perform the
> intersection.
> 
> Regards, Krzysztof
> 
> ------------------------------------------------------------------------------
> Slashdot TV.  
> Video for Nerds.  Stuff that matters.
> http://tv.slashdot.org/
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel

Re: [Lib2geom-devel] Intersection of SBasis

[Krzysztof K. <twe...@gm...>]

2014-08-20 22:10 GMT+02:00 Nathan Hurst <nj...@nj...>:
>
> The best algorithm for curve-curve intersection is inherently best
> done in bezier form (because it is optimal in a convex hull sense).
> Conversion is far cheaper than the alternatives (and we tried a
> bunch).  Indeed one of my long term projects was to replace all the
> sbasis code with the bezier form and simplify the code base.

"All the sbasis code" in the sense that sbasis-math.h would be
reimplemented for Bezier? Or does it mean only the intersection part?
Is SBasis on its way out?

Regards, Krzysztof

Re: [Lib2geom-devel] Intersection of SBasis

[Nathan H. <nj...@nj...>]

On Thu, Aug 21, 2014 at 01:24:55AM +0200, Krzysztof Kosiński wrote:
> 2014-08-20 22:10 GMT+02:00 Nathan Hurst <nj...@nj...>:
> >
> > The best algorithm for curve-curve intersection is inherently best
> > done in bezier form (because it is optimal in a convex hull sense).
> > Conversion is far cheaper than the alternatives (and we tried a
> > bunch).  Indeed one of my long term projects was to replace all the
> > sbasis code with the bezier form and simplify the code base.
> 
> "All the sbasis code" in the sense that sbasis-math.h would be
> reimplemented for Bezier? Or does it mean only the intersection part?

I mean all the sbasis code - the benefits of sbasis over bernstein
basis are not sufficient to warrant the two code paths.

> Is SBasis on its way out?

I think so.

njh