Home / index

Numerical Methods

A gentle invitation to the topic of Numerical Methods

by Simon Hasur (alias the Nerd of Algorihms)

Have You ever wondered how would it be to start learning about somethig with a completely random topic of that field? Well, let's do it!
And start introducing the field of Numerical Methods, by showing a little interactive applet, below... .

Bezier curve test-applet 2

test for a module of the Falanster City 3D rendering-engine written in JavaScript


cursor position: ...

cursor position realtive to center: program needs to be running to see it...

concept and program by Simon Hasur ( alias 'the Nerd of Algorithms' ) ;
licence-type: OpenSource software.

About this program:
Test of a little procedure using the HTML Canvas module's color-filled paths to draw a segment of road. In this particular case, only in 2D.
The heart of the whole thing is that the closed path, which is then filled with color, is not merely a polygon, but a 4-sided closed area wich is made of 2 segments of Bezier-curve and 2 segments of straight line.
And it's there! - move the cursor within the display-area to shape the segment of road!

Now that You could try this little program, we can gently introduce what it is about, and to steer then towards something to get oriented about the field of Numerical Methods.

As it's clear, the enclosing polygonal area (a sort of trapezoid) of the curvilinear segment of road, needs some tricks to be found correctly. Finding that correctly, has important applications for contact-detection, since for a point to touch the segment of road, it is a necessary condition for it to touch the polygonal area enclosing the curvilinear area entirely. Because it's a convex polugon, and checking if a point is within the area of a convex polygon, is comparatively easy. So far, so good.

without going into much detail about it, the Bezier-curve can be costructed so as to cross itself at some point: but in order to be concrete, let's restrict the Bezier-curves in consideration to be NON self-crossing.

But even with this restriction, as one can experiment a bit with this program, the enclosing polygonal area, sometimes mismatches. If You want a good collision-detection system, first a routine must be deviced which determines correctly that particular polygonal enclosing-area. The simil-trapezoidal polygon enclosing the segment of road, is, as You could see, always convex, otherwise a mismatch of the area is already there. If interested, use Your creativity to find which conditions can tell univocously if the polygonal area matches correctly, or not. The possiblity to easily do so, is a point which well illustrates the importance of the Bezier-curves: their feature to be encosable into a sort of convex trapezoid.

Well, Bezier-curves are usually categorized as a topic belonging to Numerical Methods, even if it's not one of the primary topics, but one which is certainly impressive from a visual point of view. If You want to explore other topics categorized ususally as Numerical Methods, hope this little demo and explanation was a positive input. With this said, let's get started.

Now follow some words on further applications of this filled polygon type of usage of Bezier-curves, and then a more calssical Numerical Method will be introduced, which will start a more systematic outline of the topics within the field of Numerical Methods. Generalizing to 3D view for sorts of 3D maps, similarly to the Map System library which I had written some time ago in C++, is easy, and a matter of just a few lines of procedure. This fact is at the basis of the FalansterCity3D rendering-engine's strategy to achieve perspectivic view of generic, large networks of roads, at a minimum coputational cost.

A 3D generalization of this, with some tuning, is one of the modules of the Falanster City 3D rendering-engine desigend to allow rendering in real-time, all sorts of urban environements in a preferably top-down view.
So... . Welcome to the field of Numerical Methods, accompanied by some applets witten in the Javascript programming-language to show things working!

Good luck!

Now. You might be wondering, what has all this to do with more classic topics of Numerical Methods:
well, one does not need to go far to find one! Ones a contact-condition is verified for the simil-trapezoidal area encolisng the segment of road illustrated before by the little applet presented before, comes the task of checking the contact with the segment of road itself. Here, it gets more interesting... the road-segment is assumed to have an always constant width... but as apparent, this trick of the Bezier-curve does not so. But it does nearly so in most circumstances. First, let's present first a variant on the previous applet, but this time featuring a forcedly symmetric road-segment.

Bezier curve test-applet 3


cursor position: ...

cursor position realtive to center: program needs to be running to see it...

This one is better, and allows us to go on with the discussion: we'll see why, soon.

Now, let's consider how a similar segment of road is treated in the Map System library: that's our starting point.
It is a polygonalized model derived either fom a simple polynomial 3D parametrized curve, or a 3D Bezier-curve, assumed to pass at the middle of the road-segment.

Now... how to check if a point is touching the segment of raoad or not, assuming that the road is planar on the vertical azis ( coordinate z) ? Well, a proper application of the Bisection method (a classical Numerical Method), can get precisely the distance from the afore-mentioned parametrized curve ; and that result can then be used easily to check if the point is at the heght of the road, and if that's it, how far it goes perpendicularly from it ( road's width matches? Or not?).

So, the next ( and starting ), topic of Numerical Methods is certainly the Bisection Algorithm : to find when a certain function f(q) is zero. As mentioned a little before, it needs some tuning to be applied to the previous discussion, but these tunings are pretty straightforward.

Only after it has been introduced, will we move to give some general definition of what Numerical Methods are about.

More material on numerical methods will be available soon!
[SITE IN CONSTRUCTION: thank You for Your Patience!]