[Bprocessor-commit] model/src/net/sourceforge/bprocessor/model SurfaceAnalysis.java, NONE, 1.1

[Michael L. <he...@us...>]

Update of /cvsroot/bprocessor/model/src/net/sourceforge/bprocessor/model
In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv9712/src/net/sourceforge/bprocessor/model

Added Files:
	SurfaceAnalysis.java 
Log Message:
Moved new pencil algorithme to a SurfaceAnalysis class

--- NEW FILE: SurfaceAnalysis.java ---
//---------------------------------------------------------------------------------
// $Id: SurfaceAnalysis.java,v 1.1 2006/12/12 09:33:54 henryml Exp $
//
// Copyright (c) 2005      The BProcessor Team (http://bprocessor.sourceforge.net) 
// Released under the Lesser GNU Public License v2.1
//---------------------------------------------------------------------------------

package net.sourceforge.bprocessor.model;

import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Surface Analysis
 *
 */
public class SurfaceAnalysis {
  /**
   * 
   * @param systems Collection of CoordinateSystem
   * @param edge Edge
   * @return True if edge is contained in a CoordinateSystem
   */
  private boolean contains(Collection systems, Edge edge) {
    Iterator iter = systems.iterator();
    while (iter.hasNext()) {
      CoordinateSystem system = (CoordinateSystem) iter.next();
      if (system.plane().contains(edge)) {
        return true;
      }
    }
    return false;
  }
  
  /**
   * 
   * @param systems Collection of CoordinateSystem
   * @param system CoordinateSystem
   * @return true if system is contained in collection
   */
  private boolean contains(Collection systems, CoordinateSystem system) {
    Iterator iter = systems.iterator();
    Plane plane = system.plane();
    while (iter.hasNext()) {
      CoordinateSystem current = (CoordinateSystem) iter.next();
      if (plane.contains(current.getOrigin())) {
        Vertex n1 = system.getN();
        Vertex n2 = current.getN();
        Vertex cross = n1.cross(n2);
        if (cross.isZero()) {
          return true;
        }
      }
    }
    return false;
  }
  
  /**
   * Remove all coordinatesystems from space
   * @param space Space
   */
  public void clearPlanes(Space space) {
    Collection planes = space.getCoordinateSystems();
    Iterator iter = planes.iterator();
    while (iter.hasNext()) {
      CoordinateSystem current = (CoordinateSystem) iter.next();
      space.remove(current);
    }
  }
  
  
  /**
   * 
   * @param space Space
   * @return collection of CoordinateSystem
   */
  public Collection planeAnalysis(Space space) {
    return planeAnalysis(space, space.getEdges());
  }
  
  /**
   * @param space Space
   * @param start Collection
   * @return Collection of CoordinateSystem
   */
  public Collection planeAnalysis(Space space, Collection start) {
    Collection systems = new LinkedList();
    Collection edges = space.getEdges();
    {
      Set mark = new HashSet();
      Map neighbours = new HashMap();
      {
        Collection vertices = space.getVertices();
        Map edgemap = new HashMap();
        { 
          Iterator iter = vertices.iterator();
          while (iter.hasNext()) {
            Vertex current = (Vertex) iter.next();
            edgemap.put(current, new LinkedList());
          }
        }
        { 
          Iterator iter = edges.iterator();
          while (iter.hasNext()) {
            Edge current = (Edge) iter.next();
            Vertex from = current.getFrom();
            List fl = (List) edgemap.get(from);
            fl.add(current);
            Vertex to = current.getTo();
            List tl = (List) edgemap.get(to);
            tl.add(current);
          }
        }
        {
          Iterator iter = edges.iterator();
          while (iter.hasNext()) {
            Edge current = (Edge) iter.next();
            List incident = new LinkedList();
            {
              Vertex from = current.getFrom();
              List fl = (List) edgemap.get(from);
              Iterator flit = fl.iterator();
              while (flit.hasNext()) {
                Edge edge = (Edge) flit.next();
                if (edge != current) {
                  incident.add(edge);
                }
              }
            }
            {
              Vertex to = current.getTo();
              List tl = (List) edgemap.get(to);
              Iterator tlit = tl.iterator();
              while (tlit.hasNext()) {
                Edge edge = (Edge) tlit.next();
                if (edge != current) {
                  incident.add(edge);
                }
              }
            }
            neighbours.put(current, incident);
          }
        }
      }
      LinkedList queue = new LinkedList(start);
      while (!queue.isEmpty()) {
        Edge current = (Edge) queue.removeFirst();
        if (!mark.contains(current)) {
          mark.add(current);
          List incident = (List) neighbours.get(current);
          List pls = new LinkedList();
          Iterator it = incident.iterator();
          while (it.hasNext()) {
            Edge edge = (Edge) it.next();
            CoordinateSystem system = CoordinateSystem.create(current, edge);
            if (system != null) {
              if (!contains(pls, edge)) {
                if (!contains(systems, system)) {
                  pls.add(system);
                }
              }
            } else {
              queue.addLast(edge);
            }
          }
          systems.addAll(pls);
        }
      }
    }
    return systems;
  }
 
  /**
   * Clear surfaces in specified space
   * @param space Space
   */
  public void clearSurfaces(Space space) {
    Collection surfaces = new LinkedList(space.getSurfaces());
    Iterator iter = surfaces.iterator();
    while (iter.hasNext()) {
      Surface current = (Surface) iter.next();
      space.remove(current);
    }
  }
  
  /**
   * Find surfaces in the space starting with the
   * edges in collection of edges
   * @param space Space
   * @param start collection of edges
   * @return collection of surfaces
   */
  public Collection surfaceAnalysis(Space space, Collection start) {
    Collection systems = planeAnalysis(space, start);
    Iterator iter = systems.iterator();
    Collection added = new LinkedList();
    while (iter.hasNext()) {
      CoordinateSystem current = (CoordinateSystem) iter.next();
      added.addAll(surfaceAnalysis(space, current, start));
    }
    return added;
  }
  
  /**
   * Find surfaces in specified space
   * @param space Space
   */
  public void surfaceAnalysis(Space space) {
    Collection systems = space.getCoordinateSystems();
    Iterator iter = systems.iterator();
    while (iter.hasNext()) {
      CoordinateSystem current = (CoordinateSystem) iter.next();
      surfaceAnalysis(space, current, space.getEdges());
    }
  }
  
  /**
   * Find surfaces in specified space that lies in the specified 
   * coordinatesystem
   * @param space Space
   * @param system CoordinateSystem
   * @param start collection of edges
   * @return collection of Surfaces
   */
  public Collection surfaceAnalysis(Space space, CoordinateSystem system, Collection start) {
    Plane plane = system.plane();
    Map vmap = new LinkedHashMap();
    Map emap = new LinkedHashMap();
    { 
      List vertices = new LinkedList(space.getVertices());
      Entity.sort(vertices);
      Iterator iter = vertices.iterator();
      while (iter.hasNext()) {
        Vertex current = (Vertex) iter.next();
        if (plane.contains(current)) {
          vmap.put(current, new VertexNode(current));
        }
      }
    }
    {
      List edges = new LinkedList(space.getEdges());
      Entity.sort(edges);
      Iterator iter = edges.iterator();
      while (iter.hasNext()) {
        Edge current = (Edge) iter.next();
        VertexNode from = (VertexNode) vmap.get(current.getFrom());
        VertexNode to = (VertexNode) vmap.get(current.getTo());
        if (from != null && to != null) {
          EdgeNode node =  new EdgeNode(current, from, to);
          emap.put(current, node);
          from.add(node);
          to.add(node);
        }
      }
    }
    {
      Iterator iter = vmap.values().iterator();
      while (iter.hasNext()) {
        VertexNode current = (VertexNode) iter.next();
        current.sort(system);
      }
    }
    {
      Set keys = emap.keySet();
      Collection surfaces = space.getSurfaces();
      Iterator iter = surfaces.iterator();
      while (iter.hasNext()) {
        Surface current = (Surface) iter.next();
        if (keys.containsAll(current.getEdges())) {
          SurfaceNode surfacenode = new SurfaceNode(current);
          int direction = Surface.direction(current.getEdges(), system);
          if (direction == Surface.RIGHT) {
            Iterator eit = current.getEdges().iterator();
            VertexNode from = (VertexNode) vmap.get(current.getFirstVertex());
            while (eit.hasNext()) {
              Edge edge = (Edge) eit.next();
              EdgeNode node = (EdgeNode) emap.get(edge);
              VertexNode to = node.other(from);
              node.setRight(to, surfacenode);
              from = to;
            }
          }
          if (direction == Surface.LEFT) {
            Iterator eit = current.getEdges().iterator();
            VertexNode from = (VertexNode) vmap.get(current.getFirstVertex());
            while (eit.hasNext()) {
              Edge edge = (Edge) eit.next();
              EdgeNode node = (EdgeNode) emap.get(edge);
              VertexNode to = node.other(from);
              node.setLeft(to, surfacenode);
              from = to;
            }
          }
        }
      }
    }
    Set added = new HashSet();
    Set removed = new HashSet();
    {
      Iterator iter = start.iterator();
      while (iter.hasNext()) {
        Edge current = (Edge) iter.next();
        if (emap.containsKey(current)) {
          EdgeNode node = (EdgeNode) emap.get(current);
          surfaceAnalysis(node, system, added, removed);
        }
      }
    }
    {
      Iterator iter = removed.iterator();
      while (iter.hasNext()) {
        Surface current = (Surface) iter.next();
        space.remove(current);
      }
    }
    {
      Iterator iter = added.iterator();
      while (iter.hasNext()) {
        Surface current = (Surface) iter.next();
        space.add(current);
      }
    }
    {
      Iterator iter = added.iterator();
      while (iter.hasNext()) {
        Surface current = (Surface) iter.next();
        Geometry.holeAnalysis(current);
      }
    }
    return added;
  }
  
  private List rightContour(EdgeNode start) {
    List edges = new LinkedList();
    VertexNode to = start.to;
    EdgeNode current = start;
    EdgeNode next = null;
    while (next != start) {
      edges.add(current.edge);
      next = current.succ(to);
      if (next.left == next.right) {
        next = next.succ(to);
      }
      to = next.other(to);
      current = next;
    }
    return edges;
  }
  
  private List leftContour(EdgeNode start) {
    List edges = new LinkedList();
    VertexNode to = start.to;
    EdgeNode current = start;
    EdgeNode next = null;
    while (next != start) {
      edges.add(current.edge);
      next = current.pred(to);
      if (next.left == next.right) {
        next = next.pred(to);
      }
      to = next.other(to);
      current = next;
    }
    return edges;
  }
  
  private void assign(Surface surface, Collection surfaces) {
    if (!surfaces.isEmpty()) {
      Surface other = (Surface) surfaces.iterator().next();
      Vertex n1 = surface.normal();
      Vertex n2 = other.normal();
      if (n1.dot(n2) > 0) {
        surface.setBackDomain(other.getBackDomain());
        surface.setBackMaterial(other.getBackMaterial());
        surface.setFrontDomain(other.getFrontDomain());
        surface.setFrontMaterial(other.getFrontMaterial());
      } else {
        surface.setBackDomain(other.getFrontDomain());
        surface.setBackMaterial(other.getFrontMaterial());
        surface.setFrontDomain(other.getBackDomain());
        surface.setFrontMaterial(other.getBackMaterial());
      }
    }
  }
  
  private void surfaceAnalysis (EdgeNode start, CoordinateSystem system,
     Set added, Set removed) {
    if (start.left == null) {
      SurfaceNode s = new SurfaceNode();
      VertexNode to = start.to;
      EdgeNode current = start;
      while (current.getLeft(to) != s) {
        s.consume(current.getLeft(to));
        current.setLeft(to, s);
        current = current.pred(to);
        to = current.other(to);
      }
      if (start.left != start.right) {
        List edges = leftContour(start);
        if (edges.size() > 2) {
          int turn = Surface.direction(edges, system);
          if (turn == Surface.LEFT) {
            Surface surface = new Surface(edges);
            assign(surface, s.surfaces);
            added.add(surface);
            removed.addAll(s.surfaces);
          }
        }
      }
    }
    if (start.right == null) {
      SurfaceNode s = new SurfaceNode();
      VertexNode to = start.to;
      EdgeNode current = start;
      while (current.getRight(to) != s) {
        s.consume(current.getRight(to));
        current.setRight(to, s);
        current = current.succ(to);
        to = current.other(to);
      }
      if (start.right != start.left) {
        List edges = rightContour(start);
        if (edges.size() > 2) {
          int turn = Surface.direction(edges, system);
          if (turn == Surface.RIGHT) {
            Surface surface = new Surface(edges);
            assign(surface, s.surfaces);
            added.add(surface);
            removed.addAll(s.surfaces);
          }
        }
      }
    }
  }
  
  /**
   * VertexNode
   */
  public class VertexNode {
    /** vertex */
    private Vertex vertex;
    /** edges */
    private List edges;
    
    /** 
     * Constructor
     * @param vertex Vertex
     */
    public VertexNode(Vertex vertex) {
      this.vertex = vertex;
      edges = new LinkedList();
    }
    
    /**
     * 
     * @param edge Edge
     */
    public void add(EdgeNode edge) {
      edges.add(edge);
    }
    
    /**
     * 
     * @param system CoordinateSystem
     */
    public void sort(CoordinateSystem system) {
      /**
       * Entry
       */
      class Entry implements Comparable {
        protected double dx;
        protected double dy;
        protected EdgeNode node;
        
        /**
         * 
         * @param node EdgeNode
         * @param dx double
         * @param dy double
         */
        public Entry(EdgeNode node, double dx, double dy) {
          this.node = node;
          this.dx = dx;
          this.dy = dy;
        }
        /**
         * @param other Object
         * @return int
         */
        public int compareTo(Object other) {
          Entry entry = (Entry) other;
          if (this.dx == 0) {
            return -1;
          }
          if (entry.dx == 0) {
            return 1;
          }
          if ((this.dy / this.dx) < (entry.dy / entry.dx)) {
            return -1;
          } else {
            return 1;
          }
        }
      }
      {
        List left = new LinkedList();
        List right = new LinkedList();

        Iterator iter = edges.iterator();
        while (iter.hasNext()) {
          EdgeNode current = (EdgeNode) iter.next();
          VertexNode other = current.other(this);
          Vertex delta = other.vertex.minus(vertex);
          double dx = system.getI().dot(delta);
          double dy = system.getJ().dot(delta);
          Entry entry = new Entry(current, dx, dy);
          if (dx == 0) {
            if (dy < 0) {
              right.add(entry);
            }
            if (dy > 0) {
              left.add(entry);
            }
          } else {
            if (dx > 0) {
              right.add(entry);
            }
            if (dx < 0) {
              left.add(entry);
            }
          }
        }

        Object[] rights = right.toArray();
        Arrays.sort(rights);
        Object[] lefts = left.toArray();
        Arrays.sort(lefts);
        List result = new LinkedList();
        for (int i = 0; i < rights.length; i++) {
          result.add(((Entry) rights[i]).node);
        }
        for (int i = 0; i < lefts.length; i++) {
          result.add(((Entry) lefts[i]).node);
        }
        edges = result;
      }
      {
        EdgeNode previous = (EdgeNode) edges.get(edges.size() - 1);
        Iterator iter = edges.iterator();
        while (iter.hasNext()) {
          EdgeNode current = (EdgeNode) iter.next();
          if (previous.to == this) {
            previous.toSucc = current;
          }
          if (previous.from == this) {
            previous.fromSucc = current; 
          }
          if (current.to == this) {
            current.toPred = previous;
          }
          if (current.from == this) {
            current.fromPred = previous;
          }
          previous = current;
        }
      }
    }
    
    /**
     * @return String
     */
    public String toString() {
      return "{" + vertex.getName() + " " + edges + "}";
    }
  }
  
  /**
   * EdgeNode
   */
  public class EdgeNode {
    /** edge */
    private Edge edge;
    /** from */
    private VertexNode from;
    /** to */
    private VertexNode to;
    /** successor arround to */
    private EdgeNode toSucc;
    /** predecessor around to */
    private EdgeNode toPred;
    /** sucessor around from */
    private EdgeNode fromSucc;
    /** predecessor around from */
    private EdgeNode fromPred;
    /** left surface */
    private SurfaceNode left;
    /** right surface */
    private SurfaceNode right;
    
    /**
     * 
     * @param edge Edge
     * @param from VertexNode
     * @param to VertexNode
     */
    public EdgeNode(Edge edge, VertexNode from, VertexNode to) {
      this.edge = edge;
      this.from = from;
      this.to = to;
    }
    
    /**
     * 
     * @param end VertexNode
     * @return VertexNode
     */
    public VertexNode other(VertexNode end) {
      if (end == from) {
        return to;
      }
      if (end == to) {
        return from;
      }
      return null;
    }
    
    /**
     * 
     * @param end VertexNode
     * @return EdgeNode
     */
    public EdgeNode succ(VertexNode end) {
      if (end == to) {
        return toSucc;
      }
      if (end == from) {
        return fromSucc;
      }
      return null;
    }
    
    /**
     * 
     * @param end VertexNode
     * @return EdgeNode
     */
    public EdgeNode pred(VertexNode end) {
      if (end == to) {
        return toPred;
      }
      if (end == from) {
        return fromPred;
      }
      return null;
    }
    
    /**
     * 
     * @param end VertexNode
     * @return SurfaceNode
     */
    public SurfaceNode getLeft(VertexNode end) {
      if (end == to) {
        return left;
      }
      if (end == from) {
        return right;
      }
      return null;
    }
    
    /**
     * @param end VertexNode
     * @param left SurfaceNode
     */
    public void setLeft(VertexNode end, SurfaceNode left) {
      if (end == to) {
        this.left = left;
      }
      if (end == from) {
        this.right = left;
      }
    }
    
    /**
     * 
     * @param end VertexNode
     * @return SurfaceNode
     */
    public SurfaceNode getRight(VertexNode end) {
      if (end == to) {
        return right;
      }
      if (end == from) {
        return left;
      }
      return null;
    }
    
    /**
     * 
     * @param end VertexNode
     * @param right SurfaceNode
     */
    public void setRight(VertexNode end, SurfaceNode right) {
      if (end == to) {
        this.right = right;
      }
      if (end == from) {
        this.left = right;
      }
    }
    
    /**
     * @return String
     */
    public String toString() {
      return "{" + edge.getName() 
         + " fp:" + ((fromPred == null) ? "nil" : fromPred.edge.getName())
         + " fs:" + ((fromSucc == null) ? "nil" : fromSucc.edge.getName())
         + " tp:" + ((toPred == null) ? "nil" : toPred.edge.getName())
         + " ts:" + ((toSucc == null) ? "nil" : toSucc.edge.getName())
        + "}";
    }
  }
  
  /**
   * SurfaceNode
   */
  public class SurfaceNode {
    /**
     * The set of surfaces is the surfaces is in the model prior to
     * surface analysis. Newly created surfaces inherit properties from
     * the existing surfaces that are later deleted.
     * 
     * Unless the geometry was malformed, there is only one surface related
     * to this SurfaceNode. More than one surface means that an edge is part
     * of more than two surfaces in a plane. This can happen easily with 
     * the current geometric tools.
     */
    private Set surfaces;
    
    /**
     * Constructs this SurfaceNode with an empty set of surfaces
     */
    public SurfaceNode() {
      super();
      surfaces = new HashSet();
    }
    /**
     * Constructs this SurfaceNode with the given surface in the set
     * of surfaces
     * @param surface a surface related to this SurfaceNode
     */
    public SurfaceNode(Surface surface) {
      super();
      surfaces = new HashSet();
      surfaces.add(surface);
    }
    
    /**
     * Adds the surfaces from another SurfaceNode to the set of
     * surfaces of this SurfaceNode. The other SurfaceNode may
     * be null.
     * @param other possibly null SurfaceNode from wich to add surfaces
     */
    public void consume(SurfaceNode other) {
      if (other != null) {
        surfaces.addAll(other.surfaces);
      }
    }
  }
}