Thread: Algorithms to smoothen lines using java and eclipse

the final product of my this project is to create an application to simulate the traffic condition on the road.. the user will sketch out the road using GUI done by the other programmer, my task is to come out with an algorithm to smoothen these road to ensure the vehicles are able to run on these road smoothly.. the road would have straight ones and curve/bends.. any guide to help jump start would be much appreciated..

thanks for any help render

Originally Posted by copeg

I presume this would be done using Swing? You could write an algorithm that encompasses Bezier Curves or NURBS...for instance using a sliding window to average out several points then using these points to calculate the appropriate control point(s) for the curve (for instance: actionscript 3 - Finding control points for bezier curve - Stack Overflow ).

correct me if i m wrong.. but the ref link is drawing the curve.. my case is an object supposedly travelling on the bend of the curve road.. is is the same??

sorry for nt being clear...

my program will have a few road on the map.. these roads will be straight or curve and cars would be travelling on them.. what i would like to achieve is when the cars are moving on curve, its movement must be smooth and not have any jaggy effect... in other words, movement of the cars on the road should be smooth and not jagged

the part that cause the not smooth movement is at the curve part.. the programme is short of a simulation of the traffic condition on the road itself. if i use the addition of subtraction of coordinate for the car when it is on the curve the jaggy thing will occur.. the road will consist of several control node will includes its x-coor, y-coor and whether it will be a curve..

bezierCurve.jpg

the picture attached is my expected result... but my current code only show the area highlighted by the orange box... the blue lines symbolise that the part is supposed to be a curve... my code will get the input from the text file... for each line... the 1st int value is the x-coord, 2nd int is the y-coord and lastly the third int value will be the flag to check if it will be a curve... the flag will be a 1 if it is a curve.. and 1 curve will be 3 1s flags...

 
import java.awt.*;
import java.applet.*;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
public class SmoothTest extends Applet {
 
    Button draw1Button, draw2Button, modifyButton, deleteButton, clearButton;
    myCanvas canvas;
    TextField statusBar;
 
    public void init() {
        GridBagLayout layout = new GridBagLayout();
        setLayout(layout);
 
        GridBagConstraints constraints = new GridBagConstraints();
 
        draw1Button = new Button("Draw Bezier");
        draw2Button = new Button("Draw B-Spline");
        modifyButton = new Button("Modify");
        deleteButton = new Button("Delete curve");
        clearButton = new Button("Clear All");
 
        constraints.fill = GridBagConstraints.BOTH;
        constraints.weightx = 1;
        layout.setConstraints(draw1Button, constraints);
        add(draw1Button);
 
        layout.setConstraints(draw2Button, constraints);
        add(draw2Button);
 
        layout.setConstraints(modifyButton, constraints);
        add(modifyButton);
 
        constraints.gridwidth = GridBagConstraints.RELATIVE;
        layout.setConstraints(deleteButton, constraints);
        add(deleteButton);
 
        constraints.gridwidth = GridBagConstraints.REMAINDER;
        layout.setConstraints(clearButton, constraints);
        add(clearButton);
 
        canvas = new myCanvas();
        constraints.weighty = 1;
        layout.setConstraints(canvas, constraints);
        add(canvas);
        //canvas.test();
 
       //g.drawLine(476, 429, 490, 411);
        statusBar = new TextField("Draw Bezier: click to add a point, double click to finish drawing", 45);
        statusBar.setEditable(false);
 
        constraints.weighty = 0;
        layout.setConstraints(statusBar, constraints);
        add(statusBar);
 
        resize(1280, 760);              //Set window size
 
    }
 
 
}
 
class myCanvas extends Canvas {
 
    PointList pts[];
    int nline;
    int curObj;
    boolean drawing;
    int action;
    final int DRAW_BEZIER = 1, DRAW_BSPLINE = 2, MODIFY = 3, DELETE = 4;
    ErrorFrame errDlg;
    // double buffering
    Image img = null;
    Graphics backg;
 
    public myCanvas() {
        pts = new PointList[200];
        nline = -1;
        drawing = false;
        action = DRAW_BEZIER;
 
        errDlg = new ErrorFrame(" Too many points!");
    }
 
    void setcursor(boolean working) {
        Cursor curs;
        if (working) {
            curs = new Cursor(Cursor.HAND_CURSOR);
        } else {
            curs = new Cursor(Cursor.DEFAULT_CURSOR);
        }
        setCursor(curs);
    }
 
    public void test(){
 
        if (action == DRAW_BEZIER || action == DRAW_BSPLINE) {
            System.out.println(nline);
 
            pts[0].draw(backg);
 
               // nline++;
                System.out.println("drawing false");
                    pts[nline] = new bezierLine();
 
 
                    if (!pts[nline].done()) {
                        if (!errDlg.isShowing()) {
                            errDlg.show();
                        }
                        nline--;
                    }
              //repaint();     
        }
 
 
       nline=0; 
    }
 
 
 
 
    public void paint(Graphics g) {
        update(g);
 
    }
 
    public void update(Graphics g) {    //Don't bother
        int i, n;
        int w=0;
        PointList temp[] = new PointList[30];
        Dimension d = size();
        int flag1=-1, x21=0,y21=0,x22=0,y22=0;
        int flag2=-1;
        if (img == null) {
            img = createImage(d.width, d.height);
            backg = img.getGraphics();
        }
 
        backg.setColor(new Color(255, 255, 255));    //Set color for background
        backg.fillRect(0, 0, d.width, d.height);  //Draw Backround
 
        // draw border
        backg.setColor(new Color(0, 0, 0));
        backg.drawRect(1, 1, d.width - 3, d.height - 3);
 
       /* for (n = 0; n <= nline; n++) {
            pts[n].draw(backg);
        }*/
 
        g.setColor(Color.red);
        try
        {
             Scanner br= new Scanner(new FileReader("route1.txt"));
             while (br.hasNextInt())
             {
 
                 if (w==0)// 1st run
                 {
                     w=1;
                    x21=br.nextInt();
                    y21=br.nextInt();
                    flag1=br.nextInt();
                    x22=br.nextInt();
                    y22=br.nextInt();
                    flag2=br.nextInt();
                    if (flag1==0 && flag2==0)
                    {
 
                        g.drawLine(x21, y21, x22, y22);
                        x21=x22;
                        y21=y22;
                        flag1=flag2;
                    }
                 }
                else
                 {
                   if (flag1==0 && flag2==0)
                    {
 
                        g.drawLine(x21, y21, x22, y22);
                        x21=x22;
                        y21=y22;
                        flag1=flag2;
                    }
                   else if(flag1==0 && flag2==1)// start of curve found
                   {
 
 
 
 
                      g.drawLine(x21, y21, x22, y22);
                      temp[nline].addCurve(x22, y22);
                       nline++;
                       x21=x22;
                        y21=y22;
                        flag1=flag2;
                   }
                   else if (flag1==1 && flag2==1)// mid curve
                   {
 
 
                       temp[nline].addCurve(x22, y22);
                       nline++;
                       flag2=flag1;
                   }
                   else if (flag1==1 && flag2==0)// end of curve
                   {
 
                     //  System.out.println("Flag1: "+flag1 +" Flag2: "+flag2);
                       temp[nline].addCurve(x22, y22);
                        nline++;
                       x21=x22;
                       y21=y22;
                       flag1=flag2;
                       for (int z=0;z<=nline;z++)
                       {
                          temp[z]= new bezierLine();
                          temp[z].draw(g);
                       }
 
                       temp[0].resetCurve();
                        nline=0;
                   }
                 }
 
                 x22=br.nextInt();
                    y22=br.nextInt();
                    flag2=br.nextInt();  
 
 
             }
        }
        catch(Exception e)
        {
 
        }
 
    }
}
 
class ErrorFrame extends Frame {
 
    Label label;
    Button button;
    String errMsg;
 
    ErrorFrame(String msg) {
        super("Error!");
        errMsg = msg;
 
        BorderLayout layout = new BorderLayout();
        setLayout(layout);
 
        label = new Label(errMsg);
        add("North", label);
 
        button = new Button("Ok");
        add("South", button);
 
        resize(200, 100);
    }
 
    public boolean action(Event evt, Object arg) {
        if (arg == "Ok") {
            dispose();
        }
        return true;
    }
}
 
class PointList {
 
    Point pt[];
    int num;
    int x, y, z; 	// color
    boolean showLine;
    int curPt;
    final int MAXCNTL = 150;
    final int range = 5;
 
    PointList() {
        num = 0;
        curPt = -1;
        pt = new Point[MAXCNTL];
        x = (int) (Math.random() * 255);
        y = (int) (Math.random() * 255);
        z = (int) (Math.random() * 255);
 
    }
void addCurve(int x3,int y3)
{
     pt[num] = new Point(x3,y3);
        num++;
}
 
 
void resetCurve ()
{
    num=0;
}
    void changeModPoint(int x, int y) {
        pt[curPt].x = x;
        pt[curPt].y = y;
    }
 
    boolean createFinal() {
        return true;
    }
 
    boolean done() {
        return true;
    }
 
    void setShow(boolean show) {
        showLine = show;
    }
 
    int inRegion(int x, int y) {
        int i;
        for (i = 0; i < num; i++) {
            if (Math.abs(pt[i].x - x) < range && Math.abs(pt[i].y - y) < range) {
                curPt = i;
                return i;
            }
        }
        curPt = -1;
        return -1;
    }
 
    void draw(Graphics g) {
 
        int i;
        int l = 3;
        for (i = 0; i < num - 1; i++) {
 
            g.drawLine(pt[i].x - l, pt[i].y, pt[i].x + l, pt[i].y);
            g.drawLine(pt[i].x, pt[i].y - l, pt[i].x, pt[i].y + l);
 
        }
 
        g.drawLine(pt[i].x - l, pt[i].y, pt[i].x + l, pt[i].y);
        g.drawLine(pt[i].x, pt[i].y - l, pt[i].x, pt[i].y + l);
 
    }
 
 
}
 
class bezierLine extends PointList {
 
    Point bpt[];
    int bnum;
    boolean ready;
    final int MAXPOINT = 1800;
    final int ENOUGH = 2;
    final int RECURSION = 900;
    int nPointAlloc;
    int enough;		// control how well we draw the curve.
    int nRecur;		// counter of number of recursion
    Point buffer[][];
    int nBuf, nBufAlloc;
 
    bezierLine() {
        bpt = new Point[MAXPOINT];
        nPointAlloc = MAXPOINT;
        bnum = 0;
        enough = ENOUGH;
        showLine = true;
        ready = false;
        buffer = null;
    }
 
    protected int distance(Point p0, Point p1, Point p2) {
        int a, b, y1, x1, d1, d2;
 
        if (p1.x == p2.x && p1.y == p2.y) {
            return Math.min(Math.abs(p0.x - p1.x), Math.abs(p0.y - p1.y));
        }
 
        a = p2.x - p1.x;
        b = p2.y - p1.y;
        y1 = b * (p0.x - p1.x) + a * p1.y;
        x1 = a * (p0.y - p1.y) + b * p1.x;
        d1 = Math.abs(y1 - a * p0.y);
        d2 = Math.abs(x1 - b * p0.x);
        if (a == 0) {
            return Math.abs(d2 / b);
        }
        if (b == 0) {
            return Math.abs(d1 / a);
        }
        return Math.min(Math.abs(d1 / a), Math.abs(d2 / b));
    }
 
    protected void curve_split(Point p[], Point q[], Point r[], int num) {
 
        int i, j;
 
 
        for (i = 0; i < num; i++) {
            q[i].copy(p[i]);
        }
        for (i = 1; i <= num - 1; i++) {
 
            r[num - i].copy(q[num - 1]);
            for (j = num - 1; j >= i; j--) {
 
                q[j].x = (q[j - 1].x + q[j].x) / 2;
                q[j].y = (q[j - 1].y + q[j].y) / 2;
            }
        }
 
        r[0].copy(q[num - 1]);
    }
 
 
    private Point get_buf (int num) 
        []
    {
 
      Point b[];
        if (buffer == null) {
            buffer = new Point[500][num];
            nBufAlloc = 500;
            nBuf = 0;
        }
        if (nBuf == 0) {
            b = new Point[num];
            for (int i = 0; i < num; i++) {
                b[i] = new Point();
            }
            return b;
        } else {
            nBuf--;
            b = buffer[nBuf];
            return b;
        }
    }
 
    protected boolean bezier_generation(Point pt[], int num, Point result[], int n[]) {
        Point qt[], rt[];	// for split
        int d[], i, max;
 
        nRecur++;
        if (nRecur > RECURSION) {
            return false;
        }
 
        d = new int[MAXCNTL];
        for (i = 1; i < num - 1; i++) {
            d[i] = distance(pt[i], pt[0], pt[num - 1]);
        }
        max = d[1];
        for (i = 2; i < num - 1; i++) {
            if (d[i] > max) {
                max = d[i];
            }
        }
        if (max <= enough || nRecur > RECURSION) {
            if (n[0] == 0) {
                if (bnum > 0) {
                    result[0].copy(pt[0]);
                } else {
                    result[0] = new Point(pt[0]);
                }
                n[0] = 1;
            }
            //reuse
            if (bnum > n[0]) {
                result[n[0]].copy(pt[num - 1]);
            } else {
                result[n[0]] = new Point(pt[num - 1]);
            }
            n[0]++;
            if (n[0] == MAXPOINT - 1) {
                return false;
            }
        } else {
 
            qt = get_buf(num);
            rt = get_buf(num);
            curve_split(pt, qt, rt, num);
            if (!bezier_generation(qt, num, result, n)) {
                return false;
            }
 
            if (!bezier_generation(rt, num, result, n)) {
                return false;
            }
 
        }
        return true;
    }
 
    public boolean try_bezier_generation(Point pt[], int num, Point result[], int n[]) {
        int oldN = n[0];
 
        if (enough == ENOUGH && num > 6) {
            enough += 3;
        }
 
        nRecur = 0;
 
        while (!bezier_generation(pt, num, bpt, n)) {
 
            n[0] = oldN;
            enough += 5;
            nRecur = 0;
        }
        return true;
    }
 
    boolean createFinal() {
        int n[];
        n = new int[1];
        if (!try_bezier_generation(pt, num, bpt, n)) {
            bnum = 0;
            return false;
        } else {
            bnum = n[0];
            return true;
        }
    }
 
    boolean done() {
        num--;
        showLine = false;
        ready = true;
        return createFinal();
    }
 
    void draw(Graphics g) {
        g.setColor(Color.red);
 
        if (ready) {
            for (int i = 0; i < bnum - 1; i++) {
                g.drawLine(bpt[i].x, bpt[i].y, bpt[i + 1].x, bpt[i + 1].y);
            }
        }
    }
}
 
 
 
class Point {
 
    int x, y;
 
    Point(Point p) {
        x = p.x;
        y = p.y;
    }
 
    Point(int _x, int _y) {
        x = _x;
        y = _y;
    }
 
    Point() {
        x = 0;
        y = 0;
    }
 
    void copy(Point p) {
        x = p.x;
        y = p.y;
    }
}