Nice and terse -- like on an EXAM!

Don is a tough guy to help. He is very sharp, so when he asks a question he already has a good understanding of the topic. But he doesn't know how to discuss a topic worth a hoot. I think he is the sort of designer who doesn't understand people so well and has trouble putting himself in your position.

This thread contains many great examples of how he fails to connect the dots of communication. Most notable he has never explained the form of the solution he is looking for. He asks for a way to "characterize (describe) the curve" without adequately explaining what "characterize" means all because he doesn't grasp what others fail to understand about his "technically" correct question.

I remember in college a student would ask a question but not convey his real point of confusion to the professor. Understandable, since he is lacking knowledge of the topic. But the professor would often fail to get what the question was really about. Sometimes this would be so obvious to me that I would raise my hand and explain it for him. lol Not much I can do to help Don though. It has been a long time since I worked with Bezier curves. Reading about them briefly doesn't give me a

be "characterized". But I can see a small start. It should be easy to obtain the slope of the line at the end points. I don't know, but I suspect it should be possible to determine if the curve has a loop or not.

I expect if he asked his question in a more math oriented group he would find an answer. This group has a lot of sharp people, but many of them are admittedly rather math challenged. Perhaps the comp.dsp group would be better, but I am sure they will want a reasonable definition of "characterize" before they will even start on an answer.

--

Rick
Reply to
rickman
Loading thread data ...

(snip, someone wrote)

(snip)

(snip)

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.

(snip)

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.

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

Reply to
glen herrmannsfeldt

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

Reply to
glen herrmannsfeldt

(snip)

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.

Again, I believe with multiply and add/subtract.

And again.

Careful to avoid any divide.

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

Reply to
glen herrmannsfeldt

(snip)

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

Reply to
glen herrmannsfeldt

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.

formatting link

--

Rick
Reply to
rickman

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.

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)

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.)

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!

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!)

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

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.

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??"

Reply to
Don Y

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.

Reply to
Don Y

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.