CODEWITHSUNDEEP
javaalgorithmgraphicslibgdxgraphics2d
Dmitry Stril
Dmitry Stril

Reputation: 1465

Polylines outline construction / Drawing thick polylines

I'm facing a task where I have to draw polylines using polygons. As an input parameters I have an array of points and thickness value. See picture below. enter image description here

I have points that form black polyline and thickness e.g. 10px. Now I need to calculate points and construct a blue polyline to form a polygon and then render it.

There are some articles related to this:

But I find them a bit complicated and difficult to understand. Aren't there any existing libraries or more simple algorithms to implement this. No rounded joints are required. I'm using java and libGDX.

Upvotes: 2

Views: 1502

Answers (2)

gpasch
gpasch

Reputation: 2682

The algorithm is as follows:

for each line:
  find the parallel line upwards:
    find the perpendicular: has a slope m2 in approximate
    check which side is right (compare angles)
    find the two points of the parallel line by solving a small equation problem (A, B, C)
  if this line is the first one keep it (l1)
  else find the intersection with the previous line (l1, l2): this will give the next articulation point

The yellow line is the one you want; the red line is the general parallel line. The articulation points are in green. You can print this bufferedimage in some component.

Notes: the width of the polygon cannot be fixed as you realize because at articulation points the distance will be larger. What is guaranteed is that the distance between line segments is constant.

int[] approximate(int[] p, int[] p2, double dr, int l) { // l is the distance, dr is 0 for the beginning of the segment and 1 for the end
          double d=Math.sqrt(Math.pow(p[0]-p2[0], 2)+Math.pow(p[1]-p2[1], 2));
          double ix=p[0]+dr*(p2[0]-p[0]), iy=p[1]+dr*(p2[1]-p[1]);
          double x1=0, x2=0, y1=0, y2=0;
          if(p2[0]==p[0]) {
            x1=ix+l; x2=ix-l; y1=iy; y2=iy;
          }
          else {
          double m=1.0*(p2[1]-p[1])/(p2[0]-p[0]);
          if(Math.abs(m)==0) {
            x1=ix; x2=ix; y1=iy+l; y2=iy-l;
          }
          else {
            double m2=-1/m;
            double c=iy-m2*ix;
            double A=1+m2*m2, B=-2*(ix-m2*c+m2*iy), C=ix*ix+iy*iy+c*c-2*c*iy-l*l;
            x1=(-B+Math.sqrt(B*B-4*A*C))/(2*A); x2=(-B-Math.sqrt(B*B-4*A*C))/(2*A); y1=m2*x1+c; y2=m2*x2+c;
          }
          }
          int[] cp1={p2[0]-p[0], p2[1]-p[1]}, cp2={(int)x1-p[0], (int)y1-p[1]}, xy=new int[2];
          int cpp=compareAngles(cp1, cp2);
          if(cpp>0) { xy[0]=(int)x1; xy[1]=(int)y1; } else { xy[0]=(int)x2; xy[1]=(int)y2; }
          return xy;
  }

  void poly() {
    int[][] p={{100, 400}, {110, 440}, {250, 300}, {350, 400}, {300, 310}};
    BufferedImage bim=new BufferedImage(500, 500, BufferedImage.TYPE_INT_RGB);
    Graphics2D g=(Graphics2D)bim.getGraphics();
    g.setColor(Color.white);
    g.fillRect(0, 0, 500, 500);
    g.setStroke(new BasicStroke(5f));
    g.setColor(Color.black);
    Line2D.Double l1=new Line2D.Double(), l2=new Line2D.Double();
    int[] currentp=new int[2], lastp=new int[2];
    for(int i=0; i<p.length-1; i++) {
      g.setColor(Color.black);
      g.drawLine(p[i][0], p[i][1], p[i+1][0], p[i+1][1]);
      int[] p1=approximate(p[i], p[i+1], 0, 10), p2=approximate(p[i], p[i+1], 1, 10);
      g.setColor(Color.red);
      g.drawLine(p1[0], p1[1], p2[0], p2[1]);
      if(i==0) { l1=new Line2D.Double(p1[0], p1[1], p2[0], p2[1]); currentp[0]=p1[0]; currentp[1]=p1[1]; }
      else {
        l2=new Line2D.Double(p1[0], p1[1], p2[0], p2[1]);
        int[] pi=intersectionPoint(l1, l2);
        g.setColor(Color.green);
        g.fillOval(pi[0], pi[1], 5, 5);
        g.setColor(Color.yellow);
        g.drawLine(currentp[0], currentp[1], pi[0], pi[1]);
        currentp[0]=pi[0]; currentp[1]=pi[1];
        l1.setLine(l2);
      }
      if(i==p.length-2) { lastp[0]=p2[0]; lastp[1]=p2[1]; }
    }
    g.setColor(Color.yellow);
    g.drawLine(currentp[0], currentp[1], lastp[0], lastp[1]);
  }

  public int[] intersectionPoint(Line2D.Double l1, Line2D.Double l2) {
    return intersectionPoint((int)l1.getX1(), (int)l1.getY1(), (int)l1.getX2(), (int)l1.getY2(), (int)l2.getX1(), (int)l2.getY1(), (int)l2.getX2(), (int)l2.getY2());
  }

  public int[] intersectionPoint(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    int[] xy={(int)(1.0*((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))),
                (int)(1.0*((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)))};
    return xy;
  }


  public int compareAngles(int[] a, int[] b) {
    int cp=a[0]*b[1]-a[1]*b[0];
    return -cp;
  }

Upvotes: 2

m.antkowicz
m.antkowicz

Reputation: 13571

I'm not really sure why you want to implement some advanced graphics alghoritms in framework which first place duty is to render things easily :)

Libgdx has built-in ShapeRenderer that allows you to draw simple shapes. All you have to do is to calculate new vertices basing on thickness and pass them to the ShapeRenderer to draw circles and lines that connects these circles.

To make it super-easy you can even use 

    rectLine(float x1, float y1, float x2, float y2, float width)

method that allows you to draw line of given thickness. So only what you need to do is to iterate over points and draw all lines like in this pseudo code:

    for point in points:
        if thereIsANextPoint():
            next = getNextPoint()

            sr.rectLine(point.x, point.y, next.x, next .y, thickness)

The nice description of how to use ShapeRenderer is included in reference I've attached above

I guess that there can be a little problem with joinings between points (because of different angles for example) I think that rendering circles above this joins will be good workarround :)

Upvotes: 0

Related Questions