My blog has been moved to ariya.ofilabs.com.

Thursday, August 16, 2007

Tracing the diagonals

This is a real-world problem, but could also serve well as an interview question. The task is to create two sequences of numbers which when plotted against each other (ala Lissajous curve) give the following (the knots are there to emphasize the points):

Here was my quick hack to solve it (written for Qt 4.x). The important part is in the constructor, the rest is only to show the result. I'm sure there are way better and much more elegant solutions. Care to share yours?

#define NSIZE 5 // must be odd

#include <QApplication>
#include <QPainter>
#include <QPainterPath>
#include <QWidget>

class W: public QWidget
{
private:
  int* x;
  int* y;
public:
  W(): QWidget(0)
  {
    x = new int[NSIZE*NSIZE];
    y = new int[NSIZE*NSIZE];
    x[0] = y[0] = 0;
    int xs = 1, ys = 0;
    for(int i = 1; i < NSIZE*NSIZE; i++)
    {
      x[i] = x[i-1] + xs;
      y[i] = y[i-1] + ys;
      xs = (x[i]-x[i-1]+y[i]-y[i-1] == 1) ?
           (xs) ? (y[i] ? 1 : -1) : (x[i] ? -1 : 1) :
           (!x[i] || x[i]==NSIZE-1) ? 0 :
           (y[i]==NSIZE-1) ? 1 : xs;
      ys = (x[i]-x[i-1]+y[i]-y[i-1] == 1) ?
           (ys) ? (x[i] ? 1 : -1) : (y[i] ? -1 : 1) :
           (x[i]==NSIZE-1) ? 1 :
           (!y[i] || y[i]==NSIZE-1) ? 0 : ys;
    }
  }

  ~W()
  {
    delete [] x;
    delete [] y;
  }

  #define DD 0.05
  void paintEvent(QPaintEvent*)
  {
    QPainterPath d;
    d.moveTo(x[0],y[0]);
    for(int i = 0; i < NSIZE*NSIZE; i++)
    {
      d.lineTo(x[i], y[i]);
      d.lineTo(x[i]+DD, y[i]+DD);
      d.lineTo(x[i]+DD, y[i]-DD);
      d.lineTo(x[i]-DD, y[i]-DD);
      d.lineTo(x[i]-DD, y[i]+DD);
      d.lineTo(x[i]+DD, y[i]+DD);
      d.lineTo(x[i], y[i]);
    }

    QPainter p(this);
    p.setRenderHint(QPainter::Antialiasing);
    p.fillRect(rect(), Qt::white);
    p.setPen(QPen(Qt::red, DD));
    p.translate(10, 10);
    p.scale((width()-20)/(NSIZE-1), (height()-20)/(NSIZE-1));
    p.drawPath(d);
  }
};

int main( int argc, char ** argv )
{
  QApplication a( argc, argv );

  W* w = new W;
  w->setWindowTitle("Diagonal Tracing");
  w->show();

  a.connect( &a, SIGNAL(lastWindowClosed()), &a, SLOT(quit()) );
  return a.exec();
}

No comments: