VectorOptimizer.java

/**
 * This file is part of LibLaserCut.
 * Copyright (C) 2011 - 2013 Thomas Oster <thomas.oster@rwth-aachen.de>
 * RWTH Aachen University - 52062 Aachen, Germany
 *
 *     LibLaserCut is free software: you can redistribute it and/or modify
 *     it under the terms of the GNU Lesser General Public License as published by
 *     the Free Software Foundation, either version 3 of the License, or
 *     (at your option) any later version.
 *
 *     LibLaserCut is distributed in the hope that it will be useful,
 *     but WITHOUT ANY WARRANTY; without even the implied warranty of
 *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *     GNU Lesser General Public License for more details.
 *
 *     You should have received a copy of the GNU Lesser General Public License
 *     along with LibLaserCut.  If not, see <http://www.gnu.org/licenses/>.
 **/
package com.t_oster.liblasercut.utils;

import com.t_oster.liblasercut.LaserProperty;
import com.t_oster.liblasercut.VectorCommand;
import com.t_oster.liblasercut.VectorPart;
import com.t_oster.liblasercut.platform.Point;
import com.t_oster.liblasercut.platform.Rectangle;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author Thomas Oster <thomas.oster@rwth-aachen.de>
 */
public class VectorOptimizer
{
  public enum OrderStrategy
  {
    FILE,
    NEAREST,
    INNER_FIRST,
    SMALLEST_FIRST
  }

  class Element
  {
    LaserProperty prop;
    Point start;
    List<Point> moves = new LinkedList<Point>();
    void invert()
    {
      if (!moves.isEmpty())
      {
        moves.add(0, start);
        start = moves.remove(moves.size()-1);
        List<Point> inv = new LinkedList<Point>();
        while (!moves.isEmpty())
        {
          inv.add(moves.remove(moves.size()-1));
        }
        moves = inv;
      }
    }
    
   
    
    Point getEnd()
    {
      return moves.isEmpty() ? start : moves.get(moves.size()-1);
    }
    
    /** 
     * compute bounding box of moves, including start point
     * @return Rectangle 
     */
    Rectangle boundingBox() {
      if (start == null) { // TODO may this happen?
        return null;
      }
      Rectangle bb=new Rectangle(start.x,start.y,start.x,start.y);
      for (Point p: moves) {
        bb.add(p);
      }
      return bb;
    }
    
    /**
     * test if this Element represents a closed path (polygon)
     * @return true if start equals end, false otherwise
     */
    boolean isClosedPath() {
      if ((start == null) || moves.isEmpty()) {
        return false;
      }
      return getEnd().equals(start);
    }
  }
  


  private OrderStrategy strategy = OrderStrategy.FILE;

  public VectorOptimizer(OrderStrategy s)
  {
    this.strategy = s;
  }

  private List<Element> divide(VectorPart vp)
  {
    List<Element> result = new LinkedList<Element>();
    Element cur = null;
    Point lastMove = null;
    LaserProperty lastProp = null;
    boolean stop = false;
    for (VectorCommand cmd : vp.getCommandList())
    {
      switch (cmd.getType())
      {
        case MOVETO:
        {
          lastMove = new Point(cmd.getX(), cmd.getY());
          stop = true;
          break;
        }
        case LINETO:
        {
          if (stop)
          {
            stop = false;
            if (cur != null)
            {
              result.add(cur);
            }
            cur = new Element();
            cur.start = lastMove;
            cur.prop = lastProp;
          }
          cur.moves.add(new Point(cmd.getX(), cmd.getY()));
          break;
        }
        case SETPROPERTY:
        {
          lastProp = cmd.getProperty();
          stop = true;
          break;
        }
      }
    }
    if (cur != null)
    {
      result.add(cur);
    }
    return result;
  }

  private double dist(Point a, Point b)
  {
    return Math.sqrt((a.y-b.y)*(a.y-b.y)+(a.x-b.x)*(a.x-b.x));
  }

    
    
    
    // helper classes:
    private abstract class ElementValueComparator implements Comparator<Element> {
        /**
         * get one integer from the element
         * order ascending by this integer
         * inside objects should have the lowest values
         */
        abstract int getValue(Element e);
        
        /**
         * compare by getValue()
         */
        @Override
        public int compare(Element a, Element b) {
            Integer av = new Integer(getValue(a));
            Integer bv = new Integer(getValue(b));
            return av.compareTo(bv);
        }
        
    }
    

    
    
  private List<Element> sort(List<Element> e)
  {
    List<Element> result = new LinkedList<Element>();
    if (e.isEmpty())
    {
      return result;
    }
    switch (strategy)
    {
      case FILE:
      {
        result.addAll(e);
        break;
      }
      case NEAREST:
      {
        result.add(e.remove(0));
        while (!e.isEmpty())
        {
          Point end = result.get(result.size()-1).getEnd();
          //find nearest element
          int next = 0;
          //invert element direction if endpoint is nearer
          boolean invert = false;
          double dst = -1;
          for (int i = 1; i < e.size(); i++)
          {
            //check distance to startpoint
            double nd = dist(e.get(i).start, end);
            if (nd < dst || dst == -1)
            {
              next = i;
              dst = nd;
              invert = false;
            }
            if (!e.get(i).start.equals(e.get(i).getEnd()))
            {
              //check distance to endpoint
              nd = dist(e.get(i).getEnd(), end);
              if (nd < dst || dst == -1)
              {
                next = i;
                dst = nd;
                invert = true;
              }
            }
          }
          //add next
          if (invert)
          {
            Element m = e.remove(next);
            m.invert();
            result.add(m);
          }
          else
          {
            result.add(e.remove(next));
          }
        }
        break;
      }
      case INNER_FIRST: {
        /** cut inside parts first, outside parts later
         * this algorithm is very robust, it works even for unconnected paths that are split into individual lines (e.g. from some DXF imports)
         * it is not completely perfect, as it only considers the bounding-box and not the individual path
         * 
         * see below for documentation of the inner workings
         */
        
        
        class XMinComparator extends ElementValueComparator {
          // compare by XMin a>b
          @Override
          int getValue(Element e) {
            return -e.boundingBox().getXMin();
          }
        }
        
        class YMinComparator extends ElementValueComparator {
          // compare by YMin a>b
          @Override
          int getValue(Element e) {
            return -e.boundingBox().getYMin();
          }
        }
        
        class XMaxComparator extends ElementValueComparator {
          // compare by XMax a<b
          @Override
          int getValue(Element e) {
            return e.boundingBox().getXMax();
          }
        }
        
        class YMaxComparator extends ElementValueComparator {
          // compare by YMax a<b
          @Override
          int getValue(Element e) {
            return e.boundingBox().getYMax();
          }
        }
        result.addAll(e);
        /**
         * HEURISTIC:
         * this algorithm is based on the following observation:
         * let I and O be rectangles, I inside O
         * for explanations, assume that:
         * - the X-axis goes from left to right
         * - the Y-axis goes from bottom to top
         * 
         *         ---------------- O: outside rectangle
         *         |              |
         *         |    ----      |
         * y axis  |    |in| I    |
         * ^       |    ----      |
         * |       |              |
         * |       ----------------
         * |
         *  ------> x axis
         * 
         * look at each border:
         *  right border: I.getXMax() < O.getXMax()
         *   left border: I.getXMin() > O.getXMin()
         *    top border: I.getYMax() < O.getYMax()
         * bottom border: I.getYMin() > O.getYMin()
         * 
         * If we now SORT BY ymax ASCENDING, ymin DESCENDING, xmax ASCENDING, xmin DESCENDING
         *           (higher sorting priority listed first)
         * we get the rectangles sorted inside-out:
         * 1. I
         * 2. O
         * 
         * Because we sort by four values, this still works if 
         * the two rectangles start at the same corner and have the same width,
         * but only differ in height.
         *  
         * If each rectangle is split into four separate lines
         * (e.g. because of a bad DXF import),
         * this still mostly works:
         *  1. O: bottom line
         *  2. I: bottom
         *  3. I: top, left, right (both have same YMax, but top has a higher YMin)
         *  4: O: top, left, right (both have same YMax, but top has a higher YMin)
         * 
         * TRADEOFFS AND LIMITATIONS:
         * This algorithm does not work for paths that have the same bounding-box
         * (e.g. a circle inscribed to a square)
         * 
         * For concave polygons with the same bounding-box,
         * many simple Polygon-inside-Polygon algorithms also fail 
         * (or have a useless definition of "inside" that matches the misbehaviour):
         * Draw a concave polygon, remove one point at a concave edge.
         * The resulting polygon is clearly outside the original, although every edge of it is inside the original!
         * 
         * FUTURE WORK:
         * It would also be nice to sort intersecting polygons, where one polygon
         * is "90% inside" and "10% outside" the other.
         * Real-world example:_A circular hole at the border of a rectangle.
         * Due to rounding errors, it may appear slightly outside the rectangle.
         * Mathematically, it is neither fully inside nor fully outside, but the
         * user clearly wants it to be counted as "inside".
         * 
         * POSSIBLE LIBRARIES:
         * http://sourceforge.net/projects/geom-java/
         * http://sourceforge.net/projects/jts-topo-suite
         * 
         * USEFUL METHODS:
         * Element.isClosedPath()
         */
        
        // do the work:
        Collections.sort(result,new XMinComparator());
        Collections.sort(result,new YMinComparator());
        Collections.sort(result,new XMaxComparator());
        Collections.sort(result,new YMaxComparator());
        
        // the result is now mostly sorted
        // TODO somehow sort by intersecting area
        break;
      }
            
    case SMALLEST_FIRST: {
        /** cut smaller parts first, bigger parts later
         Heuristic is explained below...
         */
        
        
        class SmallerComparator extends ElementValueComparator {
            // compare by XMin a>b
            @Override
            int getValue(Element e) {
                return (e.boundingBox().getXMax()-e.boundingBox().getXMin()) * (e.boundingBox().getYMax()-e.boundingBox().getYMin());
            }
        }
        
        
        result.addAll(e);
        /**
         * HEURISTIC:
         * this algorithm is based on the following observation:
         * let S and B be rectangles, S smaller than B
         * for explanations, assume that:
         * - the X-axis goes from left to right
         * - the Y-axis goes from bottom to top
         *
         *         ---------------- B: bigger rectangle
         *         |              |
         *         |    ----      |
         * y axis  |    | S|      |
         * ^       |    ----      |
         * |       |              |
         * |       ----------------
         * |
         *  ------> x axis
         *
         * we get the rectangles sorted by size
         * 1. S
         * 2. B
         */
        
        // do the work:
        Collections.sort(result,new SmallerComparator());
        
        // the result is now mostly sorted
        break;
      }
    }
    return result;
  }

  public VectorPart optimize(VectorPart vp)
  {
    List<Element> opt = this.sort(this.divide(vp));
    LaserProperty cp = opt.isEmpty() ? vp.getCurrentCuttingProperty() : opt.get(0).prop;
    VectorPart result = new VectorPart(cp, vp.getDPI());
    for (Element e : opt)
    {
      if (!e.prop.equals(cp))
      {
        result.setProperty(e.prop);
        cp = e.prop;
      }
      result.moveto(e.start.x, e.start.y);
      for (Point p : e.moves)
      {
        result.lineto(p.x, p.y);
      }
    }
    return result;
  }

}