It’s so lightweight!

September 12, 2013

I was speaking to my recruiter/agent (ok, pimp. Whatever) the other day. A developer like me, but with a better work ethic and business nous. A rails/grails developer, he was back on J2EE and JSF, and enjoying it. Speaking to him reminded me of a lesson I learned a long time ago.

I was on a project a while ago, before the frameworks are as mature as they are now. The project was as much an excuse to skill up the in-house golden-haired boy, as much as anything. We contractors were along for the ride. The didn’t want an app server. Too heavyweight. But it turned out that having a layer to have people log in and to manage their permissions was important. So the young bloke wrote one. It was … what you’d expect. But it was lightweight. Didn’t need one of those damn app servers. Then it turned out that the app really needed a way to manage the problem of apps writing over records that were stale, so all the response/requests were passed with a bundle of what records were entangled in the session – the table names and their primary keys. Back and forth. Over a phone line. But it was lightweight, right?

I saw where it was going. When my time was up, I explained to the dude doing my debrief. Look, I said, this app passes primary keys of all entangles records back and forth with every request. It’s nuts. What is going to happen is that the young bloke will get the bright idea of keeping the list of primary keys for each session on the server, and just passing around an id for the session. That, I explained, is a transaction manager. All this trouble to avoid going with a dreadful heavyweight app server, and at the end of the day you have to write your own transaction manager.

The problem it that their app needed the services that a app server provides. ACID. Access control. There’s no getting around that. And any attempt to go “lightweight” is just going to result in an app thats just as heavyweight as an app server, but you have to spend hours of developer time writing and debugging the code.

These days I’m using spring, and I’m sure you can se where this is going.

We have two applications. A public-facing read-only app, and an editor restricted to certain people who log in remotely to update the data. The public app takes a couple of seconds to deploy. The editor takes half a minute. Why? Because the editor has over 9000 jar files in the war. Spring and struts.

You see, the editor runs on Tomcat. So lightweight! All you need is a WAR file. And the spring and struts jars. Oh, but it’s an editor, so we need an ORM model. No worries – add hibernate. Still lightweight! And the oracle driver jars, naturally. Oh, and spring security. And spring transaction management. And so on, and so forth. Takes a while to deploy. And you have to learn the ins and outs of all the spring and struts configuration files to make it go, write a spring security user service to talk to your tables where the users are. All the bits and pieces.

It occurred to me – you know, it would be way easier to put those library JARs on tomcat. That way, I could compile and deploy just the business logic. At which point, I went wait a moment!

That’s what an app server is. That’s the whole idea. It provides a managed environment for all that stuff that you are going to need whether you like it or not. But it’s so heavyweight! Tough luck – if you want multiple users writing to the same database, then it’s going to be heavyweight no matter what you do.

So what am I saying? Should our you-beaut taxonomic tree editor thingy sit on glassfish? I’ll tell you – I’m beginning to think it should.


smallworld

February 21, 2012

Success, to a degree.

Executable (my POV) jar is here
Executable (your POV) jar is here

  • Yellow = the circle along which the segment lies, green = the circle cutting the yellow circle at right angles.
  • Results are only correct if both ends of the line segment are inside the unit circle. If both ends are outside, sometimes the algorithm picks the path that runs through the unit circle. This means that if you are drawing lines from outside to outside, your best bet is to invert the unit circle, find the line, then invert the result.
  • Note that if the overall transform is fiddled with with the sliders, the “inside the unit circle” rule applies to the *untransformed* “inside”.
  • “drag the transform” is completely buggy.
  • Haven’t handled the case where the circle or its cutter is a straight line.
    if(segment.isLine())
      if(cutter.isPosCircle())
        return new Line2D.Double(a, b);
      else
        return null;
    else		
    if(cutter.isLine())
      return null;
    else
    if (cutter.isPosCircle())
      return Draw.arcNegative(c, a, b);
    else 
      return Draw.arcPositive(c, a, b);
    
    • However, it seems that now I have enough graphics primitives to draw a network on a conformal projection of the elliptic plane. And hyperbolic, for that matter.

      So now to the next bit.

      1. I have a set of nodes.
      2. The nodes have icons and state.
      3. Each node “participates” in two separate graph structures.
      4. Graph A is an arbitrary directed graph. Arcs have properties and end decorations.
      5. Graph B is a tree structure. Nodes can be within nodes.
      6. In terms of graph B, each node is a unit circle. The nodes “within” it are circles at some location with in it.
      7. The location of a node within a node is specified by a moebus transformation that maps the unit circle onto the location where the contained node is.
      8. This allows us to do nesting by composition of transforms.
      9. To display, a given node has the focus and is drawn as the main circle on the screen.
      10. This central circle has an outside and an inside.
      11. Either of these areas can display the “contents” of the node or the “context” of the node.
      12. The “normal” display is context outside, contents inside. Its what you would get if you did a zoom.
      13. If both the ouside and the inside display the same (context/context or content/content), then we draw the short line segments. You see both images of anything and the graph is drawn compactly.
      14. If both the ouside and the inside display the same (context/context or content/content), and a graph A arc needs to be drawn that crosses the border, then either the arc is not drawn, or the arc is drawn from the node to the border – the unit circle serves as a sort of vanishing horizon.
      15. When a graph A arc spans multiple tree steps – a choice
        1. Draw the arc relative to the current focus
        2. Draw the arc relative to the top of the tree
        3. Draw the arc relative to the higest node that contains both
        4. Draw the arc as a number of segments. I prefer this, because I think it will serve to “gather” arcs into pathways that make sense.
      16. Animate focus changes. Anything else will just not work.


      (pretend the blue crosses are closer on the outside than the inside)


smallworld

February 18, 2012

Ok! Where do the segment and it’s cutter intersect? Solving the equation is way too complicated and you wind up with a pair each of bletcherous quadratics for x and y. How to work out which two of the four combintions are the right ones? Gotta be an easier way.

And there is.

Build a mobius transformation H that moves the centre of segment to zero and the center of cutter ∞. The third point is arbitrary (perhaps make the mid point of the two center points fixed). [edit] Actually, it would be nice to have a method that builds a transformaion that moves two points to 0 and ∞ (and on that moves then to 0 and 1) with a k conjugate to the identity. can it be done? … I think so. There the right number of degrees of freedom for there to be a unique solution … but on second though, no. For two arbitrary points on a sphere, you cant move ’em to 0 and ∞ without getting bendy (in most cases). Only exception is when they are already opposite.

Since we know that the circle and its cutter are at right angles, the result will always be segment' = a circle centered on 0 and cutter' = a straight line passing through 0. From the radius of segment' and the slope of cutter', it’s easy to calculate points a' and p'. Transform them back by H-1, and we are done! As a bonus, this solution is general, having only the 2 cases where segment is a positive or a negative circle, and this affects only the sense of the arc, which we already know we have to handle.

I will have to update my code so that the transform correctly handles transforming the point at infinity, and generating the 0,1,∞ transform where one of the starting points is the point at infinity.


[update] Actually, If I move the centers of the circles to 0 and 1, then the points a and b must lie on the semicircles connecting the two and I can derive them from the radii. That means I can calculate them without having to fart around with line slopes.


Smallworld

January 22, 2012

I rock.

I now have generalised circles drawing properly. Looks great. Weird, but makes intuitive sense when you play with the draggers. I’ve noticed this before: while you are writing the code, the lines and arcs skip around the screen in weird ways but with an underlying logic that you can sort of grasp. When you finally get it right, they move in ways that are just a little dull, by comparison. They give you an “Oh. Is that all?” feeling. The motions lock together in predictable ways.

Anyway. The next issue is drawing line segments. This is kinda crucial, because network graphs tend to be made of them.

How to model them? One way is just to keep points a and b, but that does not uniquely specify a line. Oh sure – it does if the unit circle is the elliptic plane, but my thingy is rapidly going to get too complicated for that to work well.

Ok. How about modelling it as a circle Γ, which contains the line segment, end points a and b? Well – that’s numerically unstable. I seriously dislike it – a and b will drift away from Γ. It will actually work ok, mostly, but it won’t be as nice as it could be.

So, how about two circles Γ, which contains the line segment, and Ζ, which cuts Γ at points a and b? That portion of the boundary of Γ which happens to lie inside Ζ is our line segment.

Cool. Now we are getting there. But how to choose Ζ? There’s a pencil of circles that will do the job. Well, we could just take the straight line that cuts a and b and use that. Under transformation, it will still be correct. The problem there is if Γ happens to be a straight line. Well, what about the circle where ab is a diameter? It will always be smaller than Γ. Well … except in the case where ab happens to be a diameter of Γ. This is a general problem: we need a simple way of choosing a suitable Ζ which is never identical to Γ.

The circle at right angles to Γ which intersects it at a and b fits the bill perfectly.

But how to find it? Easy as pie!

Create the moebius transform Η that maps a to (-1,0), b to (1, 0), and the center of Γ to ∞. (an if{} to handle when Γ is a straight line – easy) Our line segment ab is now the straight line from (-1,0) to (1, 0). Our Ζ’ is simply the unit circle. And so Ζ is simply the unit circle transformed by Η-1, which we already know how to do. Voila!

So, with class “LineSegment” modelled as two circles, I need some graphics primitives to return a java Shape for the arc. Transforming the segment is a matter of transforming the circles that describe it, which we can already do.

I probably need a constructor as well. In addition to a general one, and one that creates a straight line, I want one that specifically returns that line segment from a to b where a to be are inside the unit circle and the segment is a straight line in elliptical space (ie: the stereographic projection of). Shoot – while I’m at it I may as well do a constructor for the poincare projection of hyperbolic space, too.

Straight lines in the projection of elliptical space are circles that pass through the unit circle at diametrically opposite points. Straight lines in the Poincare projection of hyperbolic space are circles at right angles to the unit circle. In both cases, they are unique for a given ab with the stipulation that they don’t cross the circle (meaning that there’s a possibility of fun when a or b is on the unit circle).

Note that in hyperbolic space, a point p can be identified with 1/p. In elliptical space, p can be identified with -1/p. This means that given a segment ab, the shortest line segment joining them is not necessarily the segment contained in the unit circle. This will become important much, much later :) .


SmallWorld

January 22, 2012

So. I’m currently attempting to write the graphics primitives for smallworld. I have

The gear that translates from math coordinates to screen coordinates.
This is important, because most of the time the “circles” will be oval in user-land. You can’t just transform the geometry, because that means that the strokes and fonts get transformed as well. Happily, java has an AffineTransform class which has a method to transform a Java2D Shape object. You manage the underlying geometry on the unit circle, get the shape, transform it, and then stroke the shape as the final step. “The Gear” that does this is a method whose job it is to get the affine transform that converts a unit circle onto a given bounding box.
A Complex class
In addition to providing methods, having a complex class allows you to see what is in math land and what’s in screen land. I consistently use “Complex” for math co-ordinates, and “Point” for screen coordinates.
A matrix class
Rather than writing or using some über matrix class, I have gone minimal. The class handles 2×2 complex matrices, and that’s all. It holds the coordinates in an array of 8 doubles. The main job of the class, really, is to hold my decisions about whether the matrix is by row or by column – to keep track of which elements hold the parts of A, B,C and D.

I am assuming a single-threaded model, and so my scratch variables are all static final. This might be a mistake.

A moebus transformation class
Extends matrix, includes obvious gear.
A circle class
Extends matrix. We represent projective circles as per my bible and cookbook: Hans Schwerdtfeger’s “The Geometry of Complex Numbers”.

I have a little test app. Below the canvas are two sliders. One does a elliptic transform with fixed points at (-1,0)(1,0), and one does a rotation around (0,0). There’s a button to refers the order in which the transforms are composed. The app draws various things – point, lines and whatnot – transformed by the sliders. It correctly handles the java “Insets” and borders.

Currently I am trying to get circles drawing correctly.

The method for doing this has signature:

public Shape getShape(Shape clip)

Why do we need to pass the clip in? Because a circle may be “inside-out” when projected stereographically onto the plane. It will be inside-out if the inside of the circle covers the point at infinity. To make this happen, the “shape” returned by this method is the circle (drawn anticlockwise) and the clipping boundary (drawn clockwise). To keep any stroking from being visible, I take the clip rectangle of the canvas and add a 50-pixel fudge factor around it. If no-one is using strokewidths of 100 or more, I’m ok. Of course, this clip rectangle has to be converted into math space in order for it to be correct when its converted back again.

Now … working out if a circle is inside out or not is straightforward for circles. Circles are represented by a hermitian matrix

Γ(z) = Az(z*) + Bz + C(z*) + D

The “inside” of the circle is when Γ(z) is positive (or is it negative?), the border of the circle is at Γ(z) = 0. A circle is an inside-out circle when Re(A) < 0.

But I'm having difficulty with lines. It's not arbitrary. When a circle is smoothly transformed from a positive to a negative circle (the circle passes over the point at infinity), it's important to fill the correct side of the line. One check might be: find the value of c(0) and work it out from there, but this fails if the line passes through 0.

I'm suspecting that I'll have to do something like:

Find the line Γ' at right-angles to the line Γ which passes through 0. The construction of this line will automagically take into account the "direction" of Γ. In the matrix representation of Γ', A and D will both be zero, and C will simply be the conjugate of B. So you should be able to work out which side of circle Γ should be filled from that.

Drawing the shape is another issue. It will be something like:

Work out where the line Γ intersects the boundaries of the clipping rectangle (extended off the screen). Note that in the case of horizontal and vertical lines, this will be NaN.
Choose to use either the spots where Γ hits the vertical edges of the clip rect, or the spots where it hits the horizontal edges. Note that these may be off screen. …
No, actually that won't work well. What I really want to do is construct a triangle from the correct corner of the bounding box (which is off screen, remember) to …
No, that won't work either. Drat. My cases are:

  • Horizontal line
  • Horizontal line entirely off screen
  • Vertical line
  • Vertical line entirely off screen
  • Line passing through diagonally adjacent corners
  • Line passing through diagonally adjacent corners of the bbox
  • Line that can safely be represented as going through horizontally opposite sides of the bbox
  • Line that can safely be represented as going through horizontally opposite sides of the bbox, but owing to its vertical position it is off screen
  • Line that can safely be represented as going through vertically opposite sides of the bbox
  • Line that can safely be represented as going through vertically opposite sides of the bbox, but owing to its horizontal position it is off screen

Times 2, because the “filled” half plane may be either side of the line. Note that the “entirely off screen” lines are all the same: either a null shape is returned, or the bounding box as a shape.

Sigh. This kind of code is a drag to test, because you never know if you might have missed some weird combination that makes your screen flicker as the parameters pass over a badly-handled spot.

I do think that all cases can be done as a triangle that extends off screen, except for horizontal and vertical lines, which are easy to test for.

—-

Hang on. I have a clip rect. I have a method that will tell me if a point is “inside” the circle. All I have to do is find out if the corners of the rectangle are inside or outside, and work from there. There are 14 cases, not including cases where the line passes through a corner.


Approximating Circles with Bezier Curves 2

January 1, 2012

Were’s the code for addcurve. Note that there’s a new parameter “first” which is true if the segment being added is the very first segment of the circle. It’s pretty obvious how to use it, and I won’t go back and show you how to back-fit it.

One important thing, however, is that there was a bit of instability in the “chop 90 dgerees off” algorithm. The fix is:


// are we in the first quadrant?
if (acos >= -1e-6 && acos90 >= 0) {
	// a fudge factor. The algorithm is ok with angles slightly
	// more than 90, but not with negative ones.
	break;
}

Also, somehow I managed to mix up the two control points during the final rotation into place. not sure how, but the fix seems to work. The result is damn close to the java “Arc2D” result. One pixel off, at most.


private static void arc_addcurve(GeneralPath pp, Point2D.Double c, double r, Point2D.Double p1hat,
		Point2D.Double p2hat, boolean first) {
	// find midpoint

	midp2.setLocation((p1hat.x + p2hat.x) / 2, (p1hat.y + p2hat.y) / 2);
	hat(midp2, midp2hat);

	// construct vector 90 degress clockwise from midp.

	midp290hat.x = -midp2hat.y;
	midp290hat.y = midp2hat.x;

	// projection of p1hat onto midphat gives us cos
	final double cosTheta = p1hat.x * midp2hat.x + p1hat.y * midp2hat.y;

	// projection of p1hat onto midp90hat gives us -sin
	final double sinTheta = -(p1hat.x * midp290hat.x + p1hat.y * midp290hat.y);

	// at which point, we apply the solution directly out of wikipedia
	final double x2_1 = (4 - cosTheta) / 3;
	final double y2_1 = (1 - cosTheta) * (3 - cosTheta) / 3 / sinTheta;

	final double x3_1 = x2_1;
	final double y3_1 = -y2_1;

	// rotate by midphat to get the final control point vectors
	// I am not at all certain how I managed to scramble this,
	// but it seems to work now.

	final double x3 = x2_1 * midp2hat.x - y2_1 * midp2hat.y;
	final double y3 = y2_1 * midp2hat.x + x2_1 * midp2hat.y;

	final double x2 = x3_1 * midp2hat.x - y3_1 * midp2hat.y;
	final double y2 = y3_1 * midp2hat.x + x3_1 * midp2hat.y;

	// and draw the cubic!
	if (first) {
		pp.lineTo(c.x + p1hat.x * r, c.y + p1hat.y * r);
	}
	
	pp.curveTo(c.x + x2 * r, c.y + y2 * r, //
			c.x + x3 * r, c.y + y3 * r, //
			c.x + p2hat.x * r, c.y + p2hat.y * r);
}

Approximating circles with bezier cirves

December 31, 2011

So, anyway. I have for some time been intending to so some work with elliptical geometry. I have looked at hyperbolic geometry, which works great for laying out tree structures but doesn’t work well for graphs with a lot of connections. So, elliptical.

By using the stereographic projection, I can work with circular regions. I can do hierarchy by putting circles within circles. Mobius transformations for the geometry, and generalized circles for my drawing. Great. But how do I represent a line segment? A serious issue, as drawings of graphs tend to be made up of them.

I can represent a line segment as two circles. A circle Γ1 containing the segment , and a circle Γ2 cutting Γ1 at the endpoints of the segment γ1, γ2. A generalised circle has an inside and an outside, and can be left or right handed (in left handed circles, the “inside” is outside). A circle switches sense when transformed by a transform that turns it inside out, so identifying the segment as that part of the border of Γ1 that is “inside” Γ2 will identify a line segment and will behave ok under arbitrary mobius transforms.

Great! Now, there are a pencil of circles that will serve as Γ2 (all circles passing through the endpoints off the segment). Unfortunately, Γ1 is in that pencil. What’s a reliable way of picking a suitable Γ2 that is never Γ1? Well – the circle at right-angles to Γ1 passing through γ1 and γ2 will fit the bill perfectly.

How to find it easily?

Hmm. Map the two endpoints γ1, γ2 onto (0,0) and (1,0) and the center of Γ1 onto (∞.∞) with a transform T. The line segment γ becomes the straight line from 0 to 1. Circle 2 is then a constant (c=(.5,0), r=.5). Transform that circle by T-1 to get Γ2.

Excellent! How to draw the arc?

Well, I don’t want to dick around with cosines – java Arc2D uses degrees clockwise rather than radians (it’s build for people drawing UIs, not people doing math) – so approximating it with a bezier is the way to go. Had a look at the Aleksas Riškus’ paper, but it didn’t work for me the first time I tried it, so I’ll have a go myself.

Which brings me to the meat of this post: suitable control points for a cubic bezier curve approximating an arc.


Well, let’s make it a little simpler. Let’s assume our arc, and ∴ γ1, γ2, are on the unit circle. We cant assume anything about the position, because I don’t want to fiddle about with rotations. But it’s easy enough to adjust our result to translate and scale it into position

I want a bezier curve starting at γ1, ending at γ2, symmetrical, having control points on lines tangent to the circle. There is therefore only one parameter – k, the magic number, the length of the “control arms”, the velocity of the initial traectory of the curve.

Now … I *can* make this simpler. Construct a unti vector ŷ pointing at the midpoint of γ1, γ2 (this will need to be handled specially for angles > π). Rotate our circle (yes, I know I promised not to do this) so that this vector is vertical. Our magic number k alters the height of the resulting bezier curve. It’s clear that I don’t really need to wory about the x value. That is, when solving the underlying cubic, I don’t have to concern myself with the fact that there are two coordinates. I can get the solution for k for a cubic that’s centered around the y axis given the height of the control points above the x axis, and work out that by getting the projection of either control point of the curve I want onto that unit vector.

How to handle the >180 case? Well, given the unit vector, γ1 should be to the right of it. If it’s to the left, reverse the vector.

Hmm. Ok: at this point, wikipedia becomes useful, having a straight-up solution for the problem.


Actually … I will want to break up the arc if it’s too long, because this algorithm becomes very crap for large angles. So the actual arc drawing does not have to worry about handling reverse midpoints. How to break up the arc? Well: cos(theta) is simply the dot product of the unit vectors, right? So if it’s <.5, then use a single arc. Else, if it's less than acos(π/3) = sqrt(3)/2 , then break it up into two arcs with the midpoint method. Else, break it up into two arcs by taking 90 degrees off counterclockwise from γ1. This will work reliably and is easy to calculate, at the price of the result not being precisely symmetrical: a long arc will be drawn as a series of 22.5 degree chunks and a bit of scrap.


So! My method will be

    public static Shape arc(
     Point2D c, // center of the arc
     Point2D p1, // first point
     Point2D p2  // a ray xc->p2 cuts the circle 
                 // counterclockwise from point 1)

Let’s start coding!!

ok! The algorithm to break the curve into segments is a joy and a wonder. Works great. I use statics because this is explicitly single-threaded. IO know you worry about performance last, but I’m a bit oldschool.

static Point2D.Double p1 = new Point2D.Double();
static Point2D.Double p2 = new Point2D.Double();
static Point2D.Double p1hat = new Point2D.Double();
static Point2D.Double p1hat90 = new Point2D.Double();
static Point2D.Double p2hat = new Point2D.Double();

public static Shape arc(Point2D.Double c, // center of the arc
		Point2D.Double _p1, // first point
		Point2D.Double _p2 // a ray xc->p2 cuts the circle
			// counterclockwise from point 1
) {
	double rad = Math.hypot(_p1.x - c.x, _p1.y - c.y);
	p1.setLocation(_p1.x - c.x, _p1.y - c.y);
	p2.setLocation(_p2.x - c.x, _p2.y - c.y);
	GeneralPath pp = new GeneralPath();
	pp.moveTo(_p1.x, _p1.y);
	double acos;
	double acos90;
	for (;;) {
		hat(p1, p1hat);
		hat(p2, p2hat);

	// vector 90 degrees anticlockwise from p1hat
		p1hat90.x = -p1hat.y;
		p1hat90.y = p1hat.x;
		acos = p1hat.x * p2hat.x + p1hat.y * p2hat.y;
		acos90 = p1hat90.x * p2hat.x + p1hat90.y * p2hat.y;
		if (acos >= 0 && acos90 >= 0) {
			break;
		}
		// not in the first quadrant.
		// take off 90 degrees
		arc_twosegments(pp, c, rad, p1hat, p1hat90);
		p1.setLocation(p1hat90);
	}
	if (acos >= .707) { // cos(π/4)
		arc_addcurve(pp, c, rad, p1hat, p2hat);
	} else { // a bit of a fudge factor
		arc_twosegments(pp, c, rad, p1hat, p2hat);
	}
	return pp;
}

static Point2D.Double midp = new Point2D.Double();
static Point2D.Double midphat = new Point2D.Double();

private static void arc_twosegments(GeneralPath pp, Point2D.Double c, double rad, Point2D.Double p1hat,
		Point2D.Double p2hat) {
	midp.setLocation((p1hat.x + p2hat.x) / 2, (p1hat.y + p2hat.y) / 2);
	hat(midp, midphat);
	midp.x = midphat.x * rad;
	midp.y = midphat.y * rad;
	arc_addcurve(pp, c, rad, p1hat, midphat);
	arc_addcurve(pp, c, rad, midphat, p2hat);
}

private static void arc_addcurve(GeneralPath pp, Point2D.Double c, double rad, Point2D.Double p1hat,
		Point2D.Double p2hat) {
	if (BOING) {
		// test code
		pp.lineTo(c.x + p1hat.x * rad, c.y + p1hat.y * rad);
		pp.lineTo(c.x + p2hat.x * rad, c.y + p2hat.y * rad);
		return;
	}
}

private static void hat(Point2D.Double a, Point2D.Double b) {
	double zz = Math.hypot(a.x, a.y);
	b.x = a.x / zz;
	b.y = a.y / zz;
}

Right! So now we have to write the money bit – arc_addcurve. This is the bit that does the bezier.

TBC…