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

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

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

Modified Files:
	SurfaceAnalysis.java 
Added Files:
	Sorter.java 
Log Message:
Refactoring of edge sorting method

--- NEW FILE: Sorter.java ---
//---------------------------------------------------------------------------------
// $Id: Sorter.java,v 1.1 2007/05/02 07:45:26 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.LinkedList;
import java.util.List;

import net.sourceforge.bprocessor.model.SurfaceAnalysis.EdgeNode;
import net.sourceforge.bprocessor.model.SurfaceAnalysis.VertexNode;


/**
 * 
 */
public class Sorter {
  private VertexNode node;
  private CoordinateSystem system;
  
  /**
   * Creater sorter
   * @param node VertexNode
   * @param system CoordinateSystem
   */
  public Sorter(VertexNode node, CoordinateSystem system) {
    this.node = node;
    this.system = 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;
      }
    }
  }

  /**
   * Sort a list of edges around some vertex
   * @param edges List of edges
   * @return Sorted list of edges
   */
  public List<EdgeNode> sort(List<EdgeNode> edges) {
    List result = new LinkedList();
    if (!edges.isEmpty()) {
      {
        List left = new LinkedList();
        List right = new LinkedList();

        for (EdgeNode current : edges) {
          VertexNode other = current.other(node);
          Vertex delta = other.vertex().minus(node.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);
        
        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);
        }
      }
    }
    return result;
  }
}

Index: SurfaceAnalysis.java
===================================================================
RCS file: /cvsroot/bprocessor/model/src/net/sourceforge/bprocessor/model/SurfaceAnalysis.java,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** SurfaceAnalysis.java	29 Mar 2007 09:38:38 -0000	1.7
--- SurfaceAnalysis.java	2 May 2007 07:45:26 -0000	1.8
***************
*** 8,12 ****
  package net.sourceforge.bprocessor.model;
  
- import java.util.Arrays;
  import java.util.Collection;
  import java.util.HashMap;
--- 8,11 ----
***************
*** 20,24 ****
  /**
   * Surface Analysis
-  *
   */
  public class SurfaceAnalysis {
--- 19,22 ----
***************
*** 434,437 ****
--- 432,443 ----
      
      /**
+      * Return vertex
+      * @return vertex
+      */
+     public Vertex vertex() {
+       return vertex;
+     }
+     
+     /**
       * 
       * @param edge Edge
***************
*** 442,546 ****
      
      /**
!      * 
       * @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;
!           }
!         }
!       }
!       
!       if (!edges.isEmpty()) {
!         {
!           List left = new LinkedList();
!           List right = new LinkedList();
! 
!           for (EdgeNode current : edges) {
!             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 = edges.get(edges.size() - 1);
!           for (EdgeNode current : edges) {
!             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;
            }
          }
        }
--- 448,473 ----
      
      /**
!      * Sort edges
       * @param system CoordinateSystem
       */
      public void sort(CoordinateSystem system) {
!       Sorter sorter = new Sorter(this, system);
!       edges = sorter.sort(edges);
!       {
!         EdgeNode previous = edges.get(edges.size() - 1);
!         for (EdgeNode current : edges) {
!           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;
          }
        }