### Archive

Archive for the ‘Portfolio’ Category

## Rotate A Point Collection About Another Point

December 24, 2012 1 comment

Well, this will probably be the last, or nearly last post of a busy year that involved a lot of work on gigs and little focus on this blog.  Sorry, maybe next year will be better

In the previous example, I showed how to rotate a box (rectangle) around an arbitrary point, but the algorithm and code never presumed anything about the geometric nature of the object.  It’s possible to extend the exact same algorithm to a collection of points and that is the subject of the current post.

Instead of maintaining variables for the four vertices of a rectangle, the code was modified to work with an arbitrary point collection.  A RotatablePoint class was used to hold data points and offload some of the computations.  This greatly simplifies the actual demo and provides you with ample means for experimentation.

The online example starts with a small collection of points as shown below.

These points are rotated about the fixed point, drawn as a red dot.  The drawing may be cleared after each rotation increment or continually updated from the prior drawing as shown below.

Have a Merry Christmas and I’ll try to post more next year!

## Geometric Shapes in Freehand Drawing Library

Well, here’s another example that I would not have though appropriate for the Freehand Drawing Library.  Regular  geometric shapes might be drawable as strokes (i.e. press-move-release) with some sort of external control to force straight or constant-angle line segments.  That concept, however, does not seem to fit in a freehand or freeform drawing library.

After some thought, many geometric shapes can be defined (even if somewhat arbitrarily) by a bounding rectangle. The current TwoPoint stroke class could easily be extended to define such a bounding rectangle.  By injecting different drawing engines, it is possible to draw a nearly unlimited number of shapes inside that bounding rectangle.

To illustrate the idea, a GeometricShape class was created that extends TwoPoint.  I developed three sample drawing engines for this stroke, Ellipse, Triangle, and BasicArrow.  Each engine draws the bounding rectangle while the mouse is down and clears it on release.  Pre-draw parameters may be assigned to each engine to further control the shape (i.e. select an isosceles or equilateral triangle or alter arrow shape).

While these engines may seem trivial, they open the door to creating a wide variety of such drawings in the FDL, and, all line decorators are available for each shape.  So, if you want a dashed ellipse or dotted arrow, it’s simply a matter of injecting the desired line decorator.

An astute reader (aka existing beta users) may ask, “what about editing?”  It’s easy to modify or extend these shape drawing engines to return the vertex information for the shape.  This information can be edited and then stored in a value object.  That VO may be sent as auxData in the stroke dataProvider.  If present, the stroke could simply redraw the shape directly from the edited vertex information instead of a bounding rectangle.  It’s all supported in the FDL architecture.

An update is going out to all beta users this morning.

Categories: Flex, Math, Portfolio

## Editing A Cubic Bezier Spline

A couple months ago, this was something I believed I would never say about the Freehand Drawing Library.  Now, the library is and always will be a drawing library. Editing is not part of the core library architecture, however, it is something that requires a level of support inside the library.  In the past, this was accomplished by caching the sequence of mouse motions used to define a stroke.  The points could be edited and manually assigned to a stroke, either all at once or in an ENTER_FRAME event to animate the stroke.

This works cleanly with a simple interface for typical strokes, i.e. touch-move-release motions.  Now that the FDL supports splines and possibly other constructs that stretch the definition of a stroke, what about editing more complex drawings?  I want to maintain a light interface and not make editing operations an integral part of the library.  That inevitably leads to interface and code bloat in an attempt to satisfy every possible combination of customer-created editor.

I think it was the movie ‘War Games’ that popularized the phrase, ‘always leave yourself a back door.’  The back door to stroke manipulation outside normal FDL methods is to use arbitrary name-value parameters.  Every stroke has the ability to access or mutate arbitrary data objects.  It’s only two methods in the API, but they provide a wide variety of capability to custom strokes.

I added a simple spline editor to the PolyLine demo as an illustration.  After creating a spline (by clicking the end button), the knot/tangent display is overlaid on top of the stroke as shown below.

The spline knots are already available since they were manually assigned to the stroke.  The tangent information is entirely encapsulated inside the drawing engine, inside the stroke.  That information is obtained by the demo via a parameter request,

__stroke.getParam( “tangent” + i.toString() );

It is the responsibility of each stroke class to document all custom parameter queries and settings.  The above query returns in- and out-tangent values in an Object and that information is passed to the editor.  Knots may be dragged, which cause a parallel shift in the tangent.  The new knot and tangent information is conveyed back to the stroke with a sequence of parameter settings,

__stroke.params = { “changeKnot”:{vertex:index, x:editor.knotX, y:editor.knotY} };

or

__stroke.params = { “changeInTangent”:{vertex:index, x:editor.inTangentX, y:editor.inTangentY} };

__stroke.params = { “changeOutTangent”:{vertex:index, x:editor.outTangentX, y:editor.outTangentY} };

If a spline drawing engine is assigned to the PolyLine, it passes this information onto the internal FDLIntepolatingSpline instance.  A non-spline engine (line segments) ignores the parameters.

The screenshot below shows the result of a knot drag.

After dragging the middle vertex, the following screenshot shows the result of editing the first-vertex out-tangent.

This is all supported by the existing architecture, but there is one wrinkle.  If the edited spline is to be saved and then redrawn at a future time, we must have the facility to record the tangent edits *and* bypass the tangent Command when the spline is reconstructed.

I added an auxData parameter to the StrokeDataVO, which allows arbitrary auxiliary data to be recorded for a stroke.  It’s easy to deep-copy an Object with a ByteArray, so preserving immutability was no problem.  Now, by adding support for a ‘redraw’ parameter in the PolyLine stroke, the spline can be redrawn with arbitrary tangents supplied by external data instead of the tangents computed by the injected tangent Command.

Categories: Flex, Math, Portfolio

## FDL Cubic Bezier Spline

April 30, 2012 1 comment

The cubic bezier spline drawing engine in the Freehand Drawing Library is now complete.  As I mentioned in the prior post, the drawing engine fits into the FDL architecture and allows a spline to be treated as a stroke.  The CubicBezierSpline drawing engine contains a reference to a FDLCubicBezierSpline, which handles all the spline computations except for tangents.  Tangents are implemented via a Command pattern (with the spline as the receiver of the Command).  Three tangent commands are now available for cubic splines.  The NormalBisector Command uses the same algorithm as described in this TechNote.  The CatmullRom Command uses an algorithm similar to that in Catmull-Rom splines.  The Corner Command can be applied on a per-vertex basis and constructs splines with hard ‘corners’ or only G-0 continuity at a join point.

While the CubicBezierSpline engine manages the internal spline and tangent commands, the spline and tangent computations can be easily used outside the FDL in a purely computational context.

Every FDL spline is arc-length parameterized by default, using a fast algorithm for on-the-fly parameterization.  So, every coordinate request, i.e. getX(t) and getY(t) is actually computed based on normalized arc length in [0,1].  So, getX(0.5) returns the x-coordinate at approximately half the length along the spline.

Splines are implemented as drawing engines for a PolyLine stroke.  As always, a drawing engine is injected into the stroke,

__data.drawingEngine = “net.algorithmist.freehand.engine.CubicBezierSpline”;

Arbitrary parameters (name-value pairs) may be assigned to any drawing engine.  All splines require a ‘tangentCommand’ parameter to inject the Command used for tangent computations.  The normal bisector algorithm is applied as follows.

__data.engineParams  = {“tangentCommand”:”net.algorithmist.freehand.commands.NormalBisector”};

or, substitute the Catmull-Rom algorithm, if desired,

__data.engineParams  = {“tangentCommand”:”net.algorithmist.freehand.commands.CatmullRom”};

then, assign the data provider to the stroke,

__stroke.data = __data;

The cubic bezier spline supports auto-closure with G-1 continuity across the full set of tangent commands since the closure algorithm is inside the Command itself. Here is a screenshot,

and here is a screenshot of an open spline using the Catmull-Rom algorithm for tangent computations,

The next step is editing the spline by adjusting knots and tangents.  I was originally skeptical how far the architecture could be pushed in terms of a ‘drawing’ that was not in line with a traditional stroke motion, i.e. press-move-release.  Editing the mathematical properties of something like a spline seemed out of the question at first thought.  So far, I’m glad the architecture is holding up without having to hack anything in.  I suppose a demo containing a spline editor will be the ultimate test

As an aside, spline editing facilities are not part of the library; they are provided as one of the many demos available to FDL users.

Categories: Flex, Portfolio

## Progress on Freehand Drawing Library Splines

Splines in the Freehand Drawing Library have been a challenge in two areas.  First, the concept of freehand drawing is centered around strokes.  Strokes are defined by sequence of mouse/touch points that begin with a press, continue with a sequence of moves (while pressing), and end with a release.  An interpolative spline is defined with a series of interpolation points or vertices and continuity conditions at the join points.  There is no concept of press-move-release. Fortunately, the FDL architecture is sufficiently general to allow points to be artificially added to strokes.  The UI issue with splines is creating a user-friendly mechanism for identifying the last interpolation point.

The second issue is editing, both vertex and in/out tangents at each vertex.  Since all strokes allow their input points to be either manually defined or cached and returned via user input, editing is not part of the core library.  It’s impossible to create an editing system that is general, maintainable, and equally satisfies all prospective users.  When it comes to splines, I don’t want to add more methods to the IFreehandDrawable interface simply to accommodate new features.  New methods should be added only with careful thought and because it makes good, long-term sense for the library.  Fortunately, ample back-doors exist to arbitrarily set and retrieve properties for various stroke engines through parameter access and mutation methods. I plan to use that existing scheme to expose parameters that facilitate spline editing.

Tangent construction is handled by a Command pattern that is applied across the engine spline or at individual vertices.  The tangent command is injectable and its fully qualified class name is part of the stroke engine parameter set.

There is currently one spline-based stroke engine for the PolyLine stroke.  The CubicBezierSpline engine is based on the cubic bezier spline in this TechNote.  The tangent construction is handled by a NormalBisector Command that is injected into the stroke engine.  I also plan to add another tangent command that uses the same approach as Catmull-Rom splines.  This provides two different cubic bezier splines with a single code base.  I also plan to provide a corner tangent command that allows sharp corners to be inserted into otherwise continuous splines.

One final feature of the architecture is the decoupling of the spline computations from the drawing facilities in the FDL.  This is similar to how I decoupled spline computations from the drawing architecture in Degrafa.  There are no actual spline computations performed in the CubicBezierSpline drawing engine.  It contains a FDLCubicBezierSpline, which is a concrete implementation of the IFDLInterpolatingSpline interface.  FDLCubicBezierSpline is completely independent of the FDL.

The final implementation issue is on-the-fly arc-length parameterization.  In order to draw the spline with line decorators, all requests for x-y coordinates along the spline are based on normalized arc length, not the spline’s natural parameter.  In other words, getX(0.5) returns an x-coordinate of a point that is approximately one-half the length along the entire spline.  The arc-length parameterization is optimized for monotonically increasing or decreasing normalized arc-length queries.  It presumes constant redraws of the spline, so there is no pre-computation/lookup applied in the parameterization.

A screenshot of work in progress is provided below.

During debugging, the outer edge of the convex hull of the bezier control points is drawn (in black).  The red dots are points on the cubic bezier spline at (approximate) uniform normalized arc length.  The next step is to apply a line decorator to actually draw the spline.  Another advantage of automatic arc-length parameterization is relatively easy computation of the Δs to use in point-to-point drawing of the spline.  This mimics a freehand curve like all the other engines, which allows automatic application of the existing line decorators in drawing the spline.

Categories: Flex, Math, Portfolio Tags: , , , ,

## New Strokes in Freehand Drawing Library

Based on beta feedback, I’ve added two new strokes into the Freehand Drawing Library.  The first is an alternate variable-width stroke.  The standard variable-width drawing emulates a brush stroke that begins at negligible size and its width increases with speed (like pushing down harder on the brush).  The alternate stroke begins at a maximum size (initial point is a dot) and its width decreases with speed.  This is an experimental implementation and the creation as a separate stroke illustrates how to modify standard strokes for custom usage.  A screenshot is provided, below.

PolyLine is a constant-width stroke that interpolates a set of points.  An interesting feature of this stroke is that it is permanently non-interactive, that is it bypasses the normal stroke interaction for mouse or touch points.  Instead, the user manually adds vertices to the PolyLine.  Like any other constant-width stroke, it is assigned a solid-line drawing engine by default, which produces the drawing below.

The dots are manually added by the demo program.  In the future, they will be draggable.  This demo is currently a placeholder to test the spline drawing engines, now under development.

Because of these new additions, I’ve opened up several more beta slots.  There are currently two remaining.

The FDL is a serious commercial product, designed for serious commercial applications.  All FDL distributions include source code with full ASDoc.  As such, a small three-figure license fee is required to join the beta.  Beta users, however, get free upgrades for the life of the product.

If you have an application that could benefit from the FDL, especially if it is mobile or involves spline drawing, please contact me at theAlgorithmist [at] gmail [dot] com to discuss joining the beta program.

I just finished the first cut at the quadratic arc decorators for the Freehand Drawing Library.  Previously, only solid arcs could be drawn.  The example below shows dashed- and dotted-line decoration applied to arrowed arcs.

The decorators all share a fast, on-the-fly arc-length parameterization utility.  I still have a few tweaks to make to one of the decorators before full production release, but the new library is going out to all beta users this morning.

Based on feedback, I’m going to add one more stroke (Polygonal) and two spline-based drawing engines to the full release.  Because of this new addition, I’m seeking a couple more beta users.  If your drawing requirements could benefit from a variety of splines, including splines that auto-convert to shapes (i.e. lines and quads) for creating dynamic outlines/fills, please e-mail me for more information on entering the beta program.

The beta includes full source code and there is a small, 3-figure license fee.  All beta users get FREE upgrades for life.  Email is theAlgorithmist [at] gmail [dot] com.  Thanks!

Categories: Flex, Math, Portfolio

## Graphing Non-Functions

My current gig is winding down, so this will probably be the last update on the function graphing engine for a while.  Although the function graphing engine is architected to graph cartesian or parameteric functions, only cartesian functions were supported in the initial release.  All functions defined in XML must implement an IPlottable interface, which means that evaluation and derivative methods are interpreted with y as a strict function of x.  All functions must be marked as cartesian, since a parametric function will not plot in the initial implementation.

What about non-functions, that is cases where y is not strictly a function of x?  As the saying goes, there is always a back door.  Functions may identify themselves as self-plotting.  In this case, the engine does not sample the function.  Instead, it provides the function with all the relevant information regarding the current graph window and calls the function’s plot() method.  A self-plotting function is welcome to draw anything it pleases, including Bezier curves, conic sections, spirals, or even smiley faces

Problems may arise with derived functions, however, i.e. other functions that derive their visual display from the definition of another function.  A graphical Marker function is a perfect example.  The Marker is an artist-generated, interactive graphic asset that is constrained to the path of another function.  If domain values exist for which there is not a unique range value, then Marker movement is unpredictable.

This example shows how to work around the non-function issue to a degree.  It plots parabolas that open upward, downward, and to the left or right.  More specifically, the parabola directrix is either parallel to the x or y axis.  Parallel to the x-axis is good.  Parallel to the y-axis causes problems.

Suppose we want a Marker constrained to the parabola along with a display of the tangent and normal, as well as the directrix.  The fixed distance from the point on the parabola to the directrix and axis of symmetry is also drawn.

Of the four use cases, the Marker follows y as a function of x in two and x as a function of y in the other two.  We can’t use the function graphing engine to manage the Marker display as it always calls the base function (parabola) eval() method with an input x-coordinate.  The derivative and normal displays won’t work in two cases because dy/dx is not uniquely defined.

In general, the equation of a parabola with vertex (h,k), focus (h,k+p), and directrix y=k-p is given by

(x-h)2 = 4p(y-k)

which allows y to be defined as a function of x, or x as a function of y.  There are really only two use cases requiring consideration, directrix parallel to the y-axis and directrix parallel to the x-axis.  In one case, horizontal mouse movement is used to position the Marker.  Vertical mouse movements control the Marker in the other case.

The custom Marker is composed directly into the custom Parabola function, which is marked as self-plotting.  This function is responsible for creating the Marker and controlling its placement as well as drawing all supporting graphics.

The Parabola function is defined in XML as

<function id=”Parabola” class=”graph.tests.Parabola” params=”h:0,k:0,p:-1,parallelTo:y”>
<lineMetrics thickness=”2″ color=”0xff0000″ />
<data markerParams=”marker:graph.symbols.CustomMarkerSymbol,rolloverColor:0x9ACD32,digits:2″
markerCoord=”1″ >
<directrix thickness=”3″ color=”0x9933CC” alpha=”1″ lineStyle=”line_dashed” dashWidth=”6″ dashSpacing=”4″ />
<lineSet1 thickness=”2″ color=”0x0000ff” />
<lineSet2 thickness=”1″ color=”0x00ff00″ alpha=”0.5″/>
</data>
</function>

and the display is shown below.

The aspect ratio of this graph is not ideal for the example, but it’s adequate for illustrating the example.  Note that the custom Parabola function is welcome to plot not only the parabola, but as many supporting graphics as it likes.  The custom Marker may be dragged along the boundaries of the parabola and rollover displays the current y-coordinate by default.

A simple parameter change,  h:0,k:0,p:1,parallelTo:y, causes the parabola to open to the right.

Parametric function graphing should be supported in the future, providing for a more clean and general-purpose means to plot any general parabola and supporting visuals.  I thought this was an interesting example of how a decent architecture and simple concepts like Composition open up possibilities that do not seem possible based on the defined constraints of an engine.

Next post will be an update on new capability in the Freehand Drawing Library.

## Graphing Freeform Functions And Derivative

I’m currently working on an interactive set of unit tests for the function graphing engine I wrote over three years ago.  We’ve made some hasty modifications to the engine over the last six months and only tested the mods within the actual learning applications.  The engine is now sufficiently complex that I’m worried about making changes in one area that have undesired consequences in another area.

This unit test engine allows any number of specific graph tests to be coded to an IGraphTest interface and added in XML.  The ComboBoxes for selecting graph tests and functions inside those tests are auto-populated based on XML data.

One of my favorite features of the graph engine (and the least tested) is freeform function input.  In the past, freeform functions and parameter values were defined completely in XML, i.e.

<function id=”freeForm1″ class=”graphing.functions.library.FreeFormparams=”1,-1,2,1″>
<data vars=”a,b,c,d,x” function=”a*x + b*x^2 – 3*sin(c*x) + d*x^3″ />
<lineMetrics thickness=”2″ color=”0xff0000″ />
</function>

The data node defines parameters a, b, c, and d that may take on any real value. The independent variable is x.  The params attribute in the function node defines the actual parameter values.  Function parsing is handled by an independent class that may be used in any other application, independent of the graphing engine.

That’s all well and good, but I wanted to test the ability to define functions and parameters programmatically, specifically typing a function into an input text field.  In this test, the XML looks like

<learningObject id=”testGraph” class=”graphing.functions.FunctionPlot”
x=”25″ y=”60″ width=”350″ height=”280″ display=”freeForm” pannable=”true” >

.
.
.

<function id=”freeForm” class=”graphing.functions.library.FreeForm” >
<lineMetrics thickness=”2″ color=”0xff0000″ />
</function>
<function id=”deriv” class=”graphing.functions.library.Derivative”
derivedFrom=”freeForm”>
<lineMetrics thickness=”2″ color=”0x0000ff”/>
</function>

The graph engine displays an initially undefined function (I had to correct a couple of typos to get that to work). A function is defined in XML (the Derivative) that is derived from that undefined freeform function (yes, two more corrections there).

The function is typed into an input box in the test application.  Spinners are used to set parameter values.  The code automatically determines the presence of a, b, c, and d  parameters and disables spinners for which there are no parameters in the function.  That was a little tricky, because of situations where ‘c’ may be used as a parameter or in the function, i.e. sin(c*x) vs. cos(x).

Here is a screenshot of a simple example with the first derivative automatically computed from the freeform function definition.  Each function is coded to a specific interface and must be able to evaluate itself and its first derivative.  Although I’d like to get into symbolic differentiation one day, the current approach is numerical and it uses an adaptive differencing algorithm based on graph scale.

It is, without question, the ugliest demo you will ever see, but its sole purpose is to facilitate rapid unit testing of both new functionality and prior capability that is to be used in new ways.

I’m really liking the freeform graphing now that it can be done purely programmatically and I’ve almost decided to add symbolic differentiation to my bucket list

## Recent Work on Unit Conversion

My first thought about this project was “boring, but at least it’s a payday.”  This application allows students to practice converting across different types of units on actual problems.  In terms of interactivity, it’s pretty much dragging rectangular tiles with a numerator and denominator into slots inside a work area.  Yes, I’m fading off to sleep as I write  A screenshot of the basic layout is shown below.

Standard tiles are fixed-width and defined in XML so that the tile set for a conversion category can be easily changed (and it was changed multiple times during development).

```<category name="Distance">
<metric>
<tile id="Distance0" >
<numerator value="1000" useCommas="false">meters</numerator>
<denominator value="1" useCommas="false">kilometer</denominator>
</tile>
.
.
.```

which brings us to the interesting part of the application – the text formatting.  I worked within the framework used by this client and all UI text components are based on Flash TextFields.  Each numerator and denominator has a value and units.  Units are written out as text strings, however, units may have singular, plural, and abbreviated forms.  The rules for formatting values are comma-formatted unless otherwise specified and scientific notation is used if the number is outside a pre-specified range.  The number of displayed digits in scientific notation is also variable.  Powers are handled with a superscript font.  I had to test if an exponent was applied in the formatting to vertically adjust text placement.

Unit text is auto-converted to an abbreviation if the text is to wide to fit inside the tile.  The XML unit type is the preferred formatting, but only if it fits.

The objective of the lesson is to convert the starting units to the requested units using the minimum number of tiles.  No more than three tiles may be dragged into the work area and each problem can be solved using no more than three tiles.  Tiles may be flipped, which adjusts the numerator and denominator; however, tiles are restored to their original (XML) form when moved back into the work area.  When a tile is released outside the work area, it automatically jumps to the nearest open slot (left-to-right).

As tiles are dragged into position, the program checks if any units cancel.  Cancellation must take into account any combination of singular, plural, or abbreviated unit.

This is where it gets fun.  The program is supposed to draw a red, diagonal strike-through mark across the unit when cancelation is detected.  Again, this has to work for any combination of singular, plural, or abbreviated unit, so the drawing is completely programmatic.

The other interesting text-processing aspect of units is that units must be gathered into like form with a single power in the event there is no cancellation.  There are also rules for formatting the answer that vary from the work-area tiles, such as rounding to the nearest 0.001 where the rounding value is arbitrary.  An example is shown below.

In the denominator, the singular unit, ‘cubic centimeter’ is combined with the abbreviated unit ‘cm^3′ to create a new unit cm^6.  This processing is done by a gathering pass where all units are broken down into a ‘fundamental’ unit and exponent.  All like units are gathered and the exponents processed to produce the output.

Currently, there is no cancellation in this step unless there is an exact unit match, i.e. cm in the denominator does not cancel cm^4 in the numerator.  The goal is to make it easier for the student to see the unit collections across tiles so that they can quickly decide which tiles to move back to the work area.

The text and dynamic drawing aspects of this project proved to be quite interesting.  The next time I think someone is presenting me with a boring project, I’ll know to think again

Categories: Flash, Flex, Portfolio