Nice and terse -- like on an EXAM!

Don Y <this@is.not.me.com> wrote:

(snip, someone wrote)
>> OK.  I am not going to do this for you, because I'm rather exasperated.
>> But I will repeat my first answer in detail:

(snip)

> (sigh)  No, you clearly don't understand the question being asked.
 
> Do you think I *didn't* use Wikipedia, Google, my bookshelf full of
> Computer Graphics texts and various other technical periodicals
> *before* posing the question?  Or, do you think that I simply couldn't
> RECOGNIZE the OBVIOUS ANSWER to my question before posting it, here?
 
> Perhaps you've only a casual familiarity with cubic beziers?  And,
> as such, aren't aware of (or haven't considered) the variety of
> different curves that can be generated from the canonical form?
> So, the idea of *characterizing* a curve based on the coefficients
> (parameters) plugged into said form doesn't mean anything to you?
 
> Let's try something simpler.  Pretend we're talking about *lines*!

(snip)

> OK, lines are pretty boring.  Let's try circles!  You recognize:
>     (x-X0)^2 + (y-Y0)^2 = R^2
> and, based on a set of X0, Y0 and R, you'd characterize things of
> this form as:
>     a circle
>     a circle of radius R
>     a circle centered at (X0,Y0)
> etc.  You wouldn't even waste the time to feed that to the fancy
> graphing program -- you *know* what it's going to look like without
> burning all those electrons trying to render an image of it!

In high school, I had a project to write a program (in PL/I) that
would characterize a conic section.  That is, given the coefficients of

A*x**2+B*x*y+C*y**2+D*x+E*y+F=0

report on the shape being a hyperbola, parabold, ellipse, circle,
line, two lines, or some other degenerate cases.  Then, for
each, describe important parameters, such as foci, ellipticity,
x and y intercepts, etc.

It seems that it is easier without the B term, but I wanted it in.
 
> And, after a moment of thought, you'd realize that for R=0, this
> degenerates to a *point* -- at (X0, Y0).
 
> Move on to ellipses (yeah, I'm using lots of keystrokes -- but introducing
> higher order constructs as we creep up on the Bezier's complexity!).  You'd
> see:
>     (x-X0)^2 / a^2    +   (y-Y0)^2 / b^2   =   1
> as the canonical form for an ellipse.  And would characterize it as:
>     an ellipse
>     an ellipse "centered" at (X0,Y0)
>     an ellipse having eccentricity sqrt(1-(b/a)^2)
>     an ellipse having major/minor axis of lengths 2a and 2b
> etc.  Again, you wouldn't bother graphing it as these characteristics
> are evident from a casual inspection of the equation.
 
> Repeat this exercise with various higher-order polynomials and

(snip)
> *NOW*, do the same for a cubic Bezier -- by moving the control points.
 
> You will end up with:
>     a simple curve (concave/convex -- though with potentially tightening
>        *or* loosening radius
>     an 'ess' shaped curve (to the left, then right; or vice versa)
>     a 'double ess' curve
>     a *loop* with "pigtails"
>     a *cusp*
>     a *closed* loop
>     a straight line (segment)
>     a line that folds back over some portion of itself
>     a line that folds back over itself *twice*
>     a *point*  (!)
> (I think those are all of the cases)
 
> As with each of the other classes of "curves" that I've discussed, here,
> all of this information is encoded in the parameters (control points)
> present in the standard form of the curve.

It would be interesting to know why you want to know this, not that
there needs to be a reason.

In the case of second order partial differential equations, the same
parameters that determine the shape for conic sections categorize
the differential equation as elliptical, parabolic, or hyperbolic,
which determines the needed boundary conditions and solution method.

Not that characterizing the shape isn't enough.
 
> As *drawing* (plotting) a Bezier is relatively EXPEN$IVE, you wouldn't
> want to have to draw each candidate curve and then heuristically
> examine the DRAWN CURVE to identify which of these cases is represented
> in the rendering.   (it's far more work to write a piece of code to
> analyze an arbitrary *image* than it would be to analyze the data
> that *drives* the creation of that image!)
 
> [A colleague already stumbled upon a solution (in the theoretical sense)
> for this part of the problem.  But, it falls down when you map it onto
> the numerical representations that you encounter in a computational
> environment -- limited precision, etc.  And, falls down in a potentially
> *big* way -- unless you arbitrarily constrain the choices for the
> various parameters/"control points"]
 
> Perhaps now you understand why lots of pretty equations on Wikipedia
> are completely USELESS in addressing this issue?

OK, I suspect that you want to be able to do multiplies with up
to Q2m.2n, and to add/subtract such.

Not so long ago, I saw someone solving the problem:

  given integers A, B, C, D, determine if A/B is greater, equal to,
  or less than C/D.

It seems that the expectation was to do it in floating point, 
and special case when B and/or D are zero.  But note that it can
be done with integer arithmetic by computing A*D and B*C.
(Java has long, which is twice the size of int, so I could multiply
without worrying about overflow.)

I suspect in your case, you also want to avoid floating point,
for one because of the uncertainty it introduces, but also the 
special cases.

Given that they are cubic Bezier, it might need products of three
values, and so Q3m.3n, but that isn't all that hard to do.

If you only do integer multiply and add/subtract, and keep all
the bits, you should not have roundoff problems.

Note also that if you have a line of the form

A*x+B*y+C=0, with integer A, B, C, you can figure out which side of
the line a point is on using integer arithmetic. No rounding,
no close but you aren't sure.

-- glen

Don Y <this@is.not.me.com> wrote:
> *This* is how the email conversation started.  I've elided things
> that I don't want discussed in a public forum (e.g., the "what"
> and "why" motivating the question).  

I suppose, but after not so long it helps to add them.

For one, it gets people in the right frame of mind to answer the
question. Also, which approximations, if any, are useful. 

The "why" is allowed to be "just because" or "for fun", but you
get appropriate answers in any case.

-- glen

George Neuner <gneuner2@comcast.net> wrote:
> On Tue, 28 Jul 2015 15:16:59 -0500, Tim Wescott

(snip)
>>Step 4: Find the EASY AND VERY RELEVANT math under the heading "Cubic 
>>Besier Curves".
 
> Don knows what a bezier is and how to compute the curve.  What he
> wants is a way to guess the shape of the curve *without* computing it.
> He is trying to use curve fitting to do shape recognition, and I
> suspect what he wants is a quick, cheap way to filter out templates
> that can't possibly match.
 
> There's not a whole lot you can say about a cubic bezier just by
> looking at its point representation.  
 
> If you have  b = {p1,p2,p3,p4} and consider the vectors:  ->p1p4,
> ->p1p2, ->p1p3   then you can you use dot product to tell whether its
> a line, a "C", or an "S", and in which direction it starts, by looking
> at on which side of ->p1p4  the control points lie.

And note that for integer, or scaled fixed point, you can do that
exactly with multiply, and, and subtract, no need for divide.
You do need multiply with double length product, though.
 
> You can tell whether the half curve relatively is a hill or some kind
> of weird ass balloon by dropping perpendiculars from the control
> points to the _line_ p1p4 and noting whether the intersections lie on
> or outside the _segment_ p1p4.

Again, I believe with multiply and add/subtract.
 
> You can make (comparitive only) proportional guesses at amplitude by
> looking at the areas of the triangles /_p1p2p4 and /_p1p3p4.

And again.
 
> If you scale 2 beziers such that ->p1p4 is the same length in each,
> then you can do some rough proportional comparisons of these features.

Careful to avoid any divide. 
 
> That's all I can think of offhand that is cheap and constant time to
> compute.   I doubt any of it will help Don much ... I suspect he
> already knows all of these tricks and they are too blunt to be of use.

The thing I don't know, though, is if you can get away with only
double length produt, or if it needs triple length.

-- glen

Don Y <this@is.not.me.com> wrote:

(snip)

> The biggest problem is dealing with the fact that the "math"
> assumes you can represent rational numbers to infinite precision
> and for little cost.  If that were the case, the two immediately
> preceding examples wouldn't bite people in the *ss!

As noted previously, avoid that.  Don't compute A/B and C/D
but instead A*D and B*C.    Always multiply, never divide.

-- glen

On 7/28/2015 10:49 PM, Don Y wrote:
>
> *NOW*, do the same for a cubic Bezier -- by moving the control points.
>
> You will end up with:
>      a simple curve (concave/convex -- though with potentially tightening
>         *or* loosening radius
>      an 'ess' shaped curve (to the left, then right; or vice versa)
>      a 'double ess' curve
>      a *loop* with "pigtails"
>      a *cusp*
>      a *closed* loop
>      a straight line (segment)
>      a line that folds back over some portion of itself
>      a line that folds back over itself *twice*
>      a *point*  (!)

I found a web page that let me adjust the control points of a cubic 
Bezier and it appears to me that the distinctions of many of these 
features could be found by inspecting such a drawing.  For example, 
whether there is a reversal of the sign of the slope of the line seems 
to depend on the separation of the two control points.

The particular drawing does not allow me to manipulate the control 
points to create a loop, so I can't say much about that.  But I am 
confident you can figure out a heuristic for identifying each of the 
features you desire.

http://cubic-bezier.com/#.93,1,.17,.01

-- 

Rick

Hi Glen,

On 7/29/2015 11:09 AM, glen herrmannsfeldt wrote:
> Don Y <this@is.not.me.com> wrote:
>
> (snip, someone wrote)
>>> OK.  I am not going to do this for you, because I'm rather exasperated.
>>> But I will repeat my first answer in detail:
>
> (snip)
>
>> (sigh)  No, you clearly don't understand the question being asked.
>
>> Do you think I *didn't* use Wikipedia, Google, my bookshelf full of
>> Computer Graphics texts and various other technical periodicals
>> *before* posing the question?  Or, do you think that I simply couldn't
>> RECOGNIZE the OBVIOUS ANSWER to my question before posting it, here?
>
>> Perhaps you've only a casual familiarity with cubic beziers?  And,
>> as such, aren't aware of (or haven't considered) the variety of
>> different curves that can be generated from the canonical form?
>> So, the idea of *characterizing* a curve based on the coefficients
>> (parameters) plugged into said form doesn't mean anything to you?
>
>> Let's try something simpler.  Pretend we're talking about *lines*!
>
> (snip)
>
>> OK, lines are pretty boring.  Let's try circles!  You recognize:
>>      (x-X0)^2 + (y-Y0)^2 = R^2
>> and, based on a set of X0, Y0 and R, you'd characterize things of
>> this form as:
>>      a circle
>>      a circle of radius R
>>      a circle centered at (X0,Y0)
>> etc.  You wouldn't even waste the time to feed that to the fancy
>> graphing program -- you *know* what it's going to look like without
>> burning all those electrons trying to render an image of it!
>
> In high school, I had a project to write a program (in PL/I) that
> would characterize a conic section.  That is, given the coefficients of
>
> A*x**2+B*x*y+C*y**2+D*x+E*y+F=0
>
> report on the shape being a hyperbola, parabold, ellipse, circle,
> line, two lines, or some other degenerate cases.

Exactly.  The coefficients encode all the data that is necessary to
make those decisions (assuming they fit into an equation of a particular
form).  So, why bother "drawing/plotting" and then using human *eyes*
to recognize the resulting shape?  Instead, just use the relationships
of the coefficients/parameters to *extract* the information.

> Then, for
> each, describe important parameters, such as foci, ellipticity,
> x and y intercepts, etc.
>
> It seems that it is easier without the B term, but I wanted it in.

One of my high school projects was to compute the locations of the
"second focus" of each of the planetary orbits (on the assumption that
the Sun was one of the foci).  Just an arbitrary project to demonstrate
knowledge of the math involved.  (the *idea* was more entertaining
to the teacher as a "source" of suitable raw data)

>> *NOW*, do the same for a cubic Bezier -- by moving the control points.
>
>> You will end up with:
>>      a simple curve (concave/convex -- though with potentially tightening
>>         *or* loosening radius
>>      an 'ess' shaped curve (to the left, then right; or vice versa)
>>      a 'double ess' curve
>>      a *loop* with "pigtails"
>>      a *cusp*
>>      a *closed* loop
>>      a straight line (segment)
>>      a line that folds back over some portion of itself
>>      a line that folds back over itself *twice*
>>      a *point*  (!)
>> (I think those are all of the cases)
>
>> As with each of the other classes of "curves" that I've discussed, here,
>> all of this information is encoded in the parameters (control points)
>> present in the standard form of the curve.
>
> It would be interesting to know why you want to know this, not that
> there needs to be a reason.

I posted a (LENGTHY) description of one of the applications that relies
heavily on this.  In brief, if you know the shape of the curve, it allows
you to short-circuit what might otherwise be expensive computations.
"How long is the curve?"  (ZERO length!  It's a POINT!, etc.)

> In the case of second order partial differential equations, the same
> parameters that determine the shape for conic sections categorize
> the differential equation as elliptical, parabolic, or hyperbolic,
> which determines the needed boundary conditions and solution method.
>
> Not that characterizing the shape isn't enough.

Characterizing the shape of a (cubic) Bezier leaks lots of information
that you'd burn CPU cycles to obtain, otherwise.  E.g., if the shape
is a concave/convex simple curve, then you already know the ordering of
the control points necessary to determine the convex hull.  If an 'S'
curve (one inflection point), then you know you have to swap two points
to get the proper ordering for the convex hull.  Etc.

I.e., the shape gives you a lot of information to avoid needless
explicit tests -- because the shape *embodies* much of that
information implicitly!

>> [A colleague already stumbled upon a solution (in the theoretical sense)
>> for this part of the problem.  But, it falls down when you map it onto
>> the numerical representations that you encounter in a computational
>> environment -- limited precision, etc.  And, falls down in a potentially
>> *big* way -- unless you arbitrarily constrain the choices for the
>> various parameters/"control points"]
>
>> Perhaps now you understand why lots of pretty equations on Wikipedia
>> are completely USELESS in addressing this issue?
>
> OK, I suspect that you want to be able to do multiplies with up
> to Q2m.2n, and to add/subtract such.

In the app described elsewhere this thread (gesture recognizer), you are
doing MILLIONS of MAC's to try to fit a given set of input data to one
of N *potential* gesture templates.  Forcing each of those to be a floating
point operation "just because" you weren't clever enough to AVOID floating
point is a huge computational overhead.  As this is the equivalent of
"recognizing a keystroke", you can't afford to take your sweet time
coming up with an "answer"; users get fidgitty in the absence of
feedback within a couple hundred ms.

So, use a bigger faster CPU/DSP with a better floating point unit!
And, a bigger, faster *battery* to keep it running all day!

(every sloppy decision has consequences; make smart decisions up
front -- even if it makes YOUR job more difficult!)

> Not so long ago, I saw someone solving the problem:
>
>    given integers A, B, C, D, determine if A/B is greater, equal to,
>    or less than C/D.
>
> It seems that the expectation was to do it in floating point,
> and special case when B and/or D are zero.  But note that it can
> be done with integer arithmetic by computing A*D and B*C.

Yes.  Eschew the obvious -- unless there are no alternatives!

> (Java has long, which is twice the size of int, so I could multiply
> without worrying about overflow.)
>
> I suspect in your case, you also want to avoid floating point,
> for one because of the uncertainty it introduces, but also the
> special cases.
>
> Given that they are cubic Bezier, it might need products of three
> values, and so Q3m.3n, but that isn't all that hard to do.

Keeping "values" small (e.g., ~16b) allows you to make accumulators
small, etc.  You have to look at the entire computation chain to
decide the consequences of your "lowest" implementation choices.

> If you only do integer multiply and add/subtract, and keep all
> the bits, you should not have roundoff problems.
>
> Note also that if you have a line of the form
>
> A*x+B*y+C=0, with integer A, B, C, you can figure out which side of
> the line a point is on using integer arithmetic. No rounding,
> no close but you aren't sure.

All these sorts of things are commonplace in Computer Graphics
algorithms.  You're concerned with performance issues and economy.

However, you can often "forgive" visual artifacts that are a
consequence of an implementation.  If, OTOH, those consequences
cause some "math" to be incorrect -- leading to a misrecognized
gesture, in this case -- the user is less forgiving.  "How come
it won't recognize the 'turn off' gesture??"

On 7/29/2015 11:22 AM, glen herrmannsfeldt wrote:
> Don Y <this@is.not.me.com> wrote:
>
> (snip)
>
>> The biggest problem is dealing with the fact that the "math"
>> assumes you can represent rational numbers to infinite precision
>> and for little cost.  If that were the case, the two immediately
>> preceding examples wouldn't bite people in the *ss!
>
> As noted previously, avoid that.  Don't compute A/B and C/D
> but instead A*D and B*C.    Always multiply, never divide.

You don't always have a choice -- unless you use rational arithmetic
throughout the computations.

E.g., the De Casteljau algorithm requires incrementally (recursive
solutions out of the question!) walking along the perimeter of the
control polygon and fabricating new chords between them that
similarly "walk".  Then, obtaining successive points on the Bezier
from these (simple) operations.  Lots of interpolation as you move t
over [0,1] so you end up having to resolve fractions instead of just
propagating them.