Optimal_Link_Style 18/16718/19
Chenfeng Zhu [Mon, 22 Jun 2015 02:11:32 +0000 (04:11 +0200)]
One-click to choose an "optimal" path for the link.
Choose the links and click the button to find an optimal path for the links and change the links style.

1. get the current orientation of port instead of the default orientation.
2. get a route to avoid blocks and intersections of lines with less turning.
3. find a route for link connected to a SplitBlock without moving it.

Change-Id: I26ef9c34c5cc1796016a2f38fe9a94b1908153e4

18 files changed:
scilab/CHANGES_5.6.X
scilab/modules/helptools/images/xcos_link_optimal_en_US.png [new file with mode: 0644]
scilab/modules/helptools/images/xcos_link_optimal_fr_FR.png [new file with mode: 0644]
scilab/modules/helptools/images/xcos_menu_format_link_style.png
scilab/modules/xcos/help/en_US/xcos_menu_entries.xml
scilab/modules/xcos/help/fr_FR/xcos_menu_entries.xml
scilab/modules/xcos/help/gui/xcos_menu_entries/en_US/xcos_menu_format_link_style.png
scilab/modules/xcos/help/gui/xcos_menu_entries/fr_FR/xcos_menu_format_link_style.png
scilab/modules/xcos/help/images/xcos_menu_entries/en_US/xcos_link_optimal_en_US.png [new file with mode: 0644]
scilab/modules/xcos/help/images/xcos_menu_entries/fr_FR/xcos_link_optimal_fr_FR.png [new file with mode: 0644]
scilab/modules/xcos/locales/fr_FR.po
scilab/modules/xcos/locales/xcos.pot
scilab/modules/xcos/src/java/org/scilab/modules/xcos/XcosTab.java
scilab/modules/xcos/src/java/org/scilab/modules/xcos/link/BasicLink.java
scilab/modules/xcos/src/java/org/scilab/modules/xcos/link/actions/StyleOptimalAction.java [new file with mode: 0755]
scilab/modules/xcos/src/java/org/scilab/modules/xcos/utils/XcosMessages.java
scilab/modules/xcos/src/java/org/scilab/modules/xcos/utils/XcosRoute.java [new file with mode: 0755]
scilab/modules/xcos/src/java/org/scilab/modules/xcos/utils/XcosRouteUtils.java [new file with mode: 0755]

index c331d1c..36254f1 100644 (file)
@@ -7,6 +7,11 @@ New Features
 * scatter plot with different mark colors is now available:
   TODO : save/load+display+doc of new properties
 
+Xcos
+====
+
+* Optimal - new link style for avoiding links crossing the blocks.
+
 
 Compilation
 ============
diff --git a/scilab/modules/helptools/images/xcos_link_optimal_en_US.png b/scilab/modules/helptools/images/xcos_link_optimal_en_US.png
new file mode 100644 (file)
index 0000000..8c2ba81
Binary files /dev/null and b/scilab/modules/helptools/images/xcos_link_optimal_en_US.png differ
diff --git a/scilab/modules/helptools/images/xcos_link_optimal_fr_FR.png b/scilab/modules/helptools/images/xcos_link_optimal_fr_FR.png
new file mode 100644 (file)
index 0000000..8c2ba81
Binary files /dev/null and b/scilab/modules/helptools/images/xcos_link_optimal_fr_FR.png differ
index 2e246a3..6a06eab 100644 (file)
Binary files a/scilab/modules/helptools/images/xcos_menu_format_link_style.png and b/scilab/modules/helptools/images/xcos_menu_format_link_style.png differ
index 36207cc..cd45b81 100644 (file)
                 </para>
                 <para>
                     First select the link and select the appropriate menu item or use the shortcuts
-                    (<emphasis>H</emphasis>), <emphasis>S</emphasis>, <emphasis>V</emphasis>).
+                    (<emphasis>H</emphasis>), (<emphasis>S</emphasis>), (<emphasis>V</emphasis>), (<emphasis>O</emphasis>).
                     The following list shows the results obtained.
                 </para>
                 <itemizedlist>
                             </imageobject>
                         </mediaobject>
                     </listitem>
+                    <listitem>
+                        <para>
+                            Optimal (<emphasis>O</emphasis>)
+                        </para>
+                        <mediaobject>
+                            <imageobject>
+                                <imagedata fileref="../images/xcos_menu_entries/en_US/xcos_link_optimal_en_US.png"/>
+                            </imageobject>
+                        </mediaobject>
+                    </listitem>
                 </itemizedlist>
             </listitem>
             <listitem>
index d352bf2..1cc3768 100644 (file)
                             </imageobject>
                         </mediaobject>
                     </listitem>
+                    <listitem>
+                        <para>Optimal</para>
+                        <mediaobject>
+                            <imageobject>
+                                <imagedata fileref="../images/xcos_menu_entries/fr_FR/xcos_link_optimal_fr_FR.png"/>
+                            </imageobject>
+                        </mediaobject>
+                    </listitem>
                 </itemizedlist>
                 <para/>
             </listitem>
index 2e246a3..d78e90d 100644 (file)
Binary files a/scilab/modules/xcos/help/gui/xcos_menu_entries/en_US/xcos_menu_format_link_style.png and b/scilab/modules/xcos/help/gui/xcos_menu_entries/en_US/xcos_menu_format_link_style.png differ
index 19c5a41..6a06eab 100644 (file)
Binary files a/scilab/modules/xcos/help/gui/xcos_menu_entries/fr_FR/xcos_menu_format_link_style.png and b/scilab/modules/xcos/help/gui/xcos_menu_entries/fr_FR/xcos_menu_format_link_style.png differ
diff --git a/scilab/modules/xcos/help/images/xcos_menu_entries/en_US/xcos_link_optimal_en_US.png b/scilab/modules/xcos/help/images/xcos_menu_entries/en_US/xcos_link_optimal_en_US.png
new file mode 100644 (file)
index 0000000..8c2ba81
Binary files /dev/null and b/scilab/modules/xcos/help/images/xcos_menu_entries/en_US/xcos_link_optimal_en_US.png differ
diff --git a/scilab/modules/xcos/help/images/xcos_menu_entries/fr_FR/xcos_link_optimal_fr_FR.png b/scilab/modules/xcos/help/images/xcos_menu_entries/fr_FR/xcos_link_optimal_fr_FR.png
new file mode 100644 (file)
index 0000000..8c2ba81
Binary files /dev/null and b/scilab/modules/xcos/help/images/xcos_menu_entries/fr_FR/xcos_link_optimal_fr_FR.png differ
index 0a20329..26aeddd 100644 (file)
@@ -48,6 +48,9 @@ msgstr "Horizontal"
 msgid "Vertical"
 msgstr "Vertical"
 
+msgid "Optimal"
+msgstr "Optimal"
+
 msgid "No trace nor debug printing"
 msgstr "Ni trace d'exĂ©cution ni dĂ©bogage"
 
index 8d5e060..95a0610 100644 (file)
@@ -88,6 +88,12 @@ msgid "Vertical"
 msgstr ""
 
 #
+# File: scilab_fake_localization_file.c, line:
+# File: src/java/org/scilab/modules/xcos/utils/XcosMessages.java, line: 
+msgid "Optimal"
+msgstr ""
+
+#
 # File: scilab_fake_localization_file.c, line: 888
 # File: src/java/org/scilab/modules/xcos/utils/XcosMessages.java, line: 244
 msgid "No trace nor debug printing"
index 998394c..f68e7e4 100644 (file)
@@ -107,6 +107,7 @@ import org.scilab.modules.xcos.configuration.model.DocumentType;
 import org.scilab.modules.xcos.configuration.utils.ConfigurationConstants;
 import org.scilab.modules.xcos.graph.XcosDiagram;
 import org.scilab.modules.xcos.link.actions.StyleHorizontalAction;
+import org.scilab.modules.xcos.link.actions.StyleOptimalAction;
 import org.scilab.modules.xcos.link.actions.StyleStraightAction;
 import org.scilab.modules.xcos.link.actions.StyleVerticalAction;
 import org.scilab.modules.xcos.palette.actions.ViewPaletteBrowserAction;
@@ -485,6 +486,7 @@ public class XcosTab extends SwingScilabDockablePanel implements SimpleTab {
         linkStyle.add(StyleHorizontalAction.createMenu(diagram));
         linkStyle.add(StyleStraightAction.createMenu(diagram));
         linkStyle.add(StyleVerticalAction.createMenu(diagram));
+        linkStyle.add(StyleOptimalAction.createMenu(diagram));
         format.add(linkStyle);
         format.addSeparator();
 
index 94e5445..0a60ee7 100644 (file)
@@ -29,6 +29,7 @@ import org.scilab.modules.gui.menu.ScilabMenu;
 import org.scilab.modules.xcos.actions.EditFormatAction;
 import org.scilab.modules.xcos.block.actions.BorderColorAction;
 import org.scilab.modules.xcos.link.actions.StyleHorizontalAction;
+import org.scilab.modules.xcos.link.actions.StyleOptimalAction;
 import org.scilab.modules.xcos.link.actions.StyleStraightAction;
 import org.scilab.modules.xcos.link.actions.StyleVerticalAction;
 import org.scilab.modules.xcos.link.commandcontrol.CommandControlLink;
@@ -286,6 +287,7 @@ public abstract class BasicLink extends ScilabGraphUniqueObject {
         linkStyle.add(StyleHorizontalAction.createMenu(graph));
         linkStyle.add(StyleStraightAction.createMenu(graph));
         linkStyle.add(StyleVerticalAction.createMenu(graph));
+        linkStyle.add(StyleOptimalAction.createMenu(graph));
 
         menu.add(linkStyle);
 
diff --git a/scilab/modules/xcos/src/java/org/scilab/modules/xcos/link/actions/StyleOptimalAction.java b/scilab/modules/xcos/src/java/org/scilab/modules/xcos/link/actions/StyleOptimalAction.java
new file mode 100755 (executable)
index 0000000..70afc4a
--- /dev/null
@@ -0,0 +1,106 @@
+/*\r
+ * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab\r
+ * Copyright (C) 2015 - Chenfeng ZHU\r
+ *\r
+ * This file must be used under the terms of the CeCILL.\r
+ * This source file is licensed as described in the file COPYING, which\r
+ * you should have received as part of this distribution.  The terms\r
+ * are also available at\r
+ * http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt\r
+ *\r
+ */\r
+\r
+package org.scilab.modules.xcos.link.actions;\r
+\r
+import java.awt.event.ActionEvent;\r
+import java.awt.event.KeyEvent;\r
+\r
+import org.scilab.modules.graph.ScilabComponent;\r
+import org.scilab.modules.graph.ScilabGraph;\r
+import org.scilab.modules.gui.menuitem.MenuItem;\r
+import org.scilab.modules.xcos.graph.XcosDiagram;\r
+import org.scilab.modules.xcos.link.BasicLink;\r
+import org.scilab.modules.xcos.utils.XcosMessages;\r
+import org.scilab.modules.xcos.utils.XcosRoute;\r
+\r
+import com.mxgraph.util.mxConstants;\r
+\r
+/**\r
+ * Implement the set link optimal action.\r
+ */\r
+@SuppressWarnings(value = { "serial" })\r
+public class StyleOptimalAction extends StyleAction {\r
+    /** Name of the action */\r
+    public static final String NAME = XcosMessages.LINK_STYLE_OPTIMAL;\r
+    /** Icon name of the action */\r
+    public static final String SMALL_ICON = "";\r
+    /** Mnemonic key of the action */\r
+    public static final int MNEMONIC_KEY = KeyEvent.VK_O;\r
+\r
+    /**\r
+     * Default constructor the associated graph\r
+     *\r
+     * @param scilabGraph\r
+     *            the graph to associate\r
+     */\r
+    public StyleOptimalAction(ScilabGraph scilabGraph) {\r
+        super(scilabGraph);\r
+    }\r
+\r
+    /**\r
+     * @param scilabGraph\r
+     * @return menu item\r
+     */\r
+    public static MenuItem createMenu(ScilabGraph scilabGraph) {\r
+        return createMenu(scilabGraph, StyleOptimalAction.class);\r
+    }\r
+\r
+    /**\r
+     * Action.\r
+     *\r
+     * @param e\r
+     * @see org.scilab.modules.xcos.link.actions.StyleAction#actionPerformed(java.awt.event.ActionEvent)\r
+     */\r
+    @Override\r
+    public void actionPerformed(ActionEvent e) {\r
+        final XcosDiagram graph = (XcosDiagram) getGraph(e);\r
+\r
+        // action disabled when the cell is edited\r
+        final ScilabComponent comp = ((ScilabComponent) graph.getAsComponent());\r
+        if (comp.isEditing()) {\r
+            return;\r
+        }\r
+\r
+        final Object[] links = getLinks();\r
+\r
+        graph.getModel().beginUpdate();\r
+        try {\r
+            double scale = graph.getView().getScale();\r
+            graph.getView().setScale(1.0);\r
+            graph.setCellStyles(mxConstants.STYLE_NOEDGESTYLE, "1", links);\r
+            reset(graph, links);\r
+            this.updateLinkOptimal(graph, links);\r
+            graph.getView().setScale(scale);\r
+        } finally {\r
+            graph.getModel().endUpdate();\r
+        }\r
+    }\r
+\r
+    /**\r
+     * Update the style of links one by one.\r
+     *\r
+     * @param graph\r
+     * @param links\r
+     */\r
+    public void updateLinkOptimal(XcosDiagram graph, Object[] links) {\r
+        Object[] allChildCells = graph.getChildCells(graph.getDefaultParent());\r
+        XcosRoute route = new XcosRoute();\r
+        for (Object o : links) {\r
+            if (o instanceof BasicLink) {\r
+                BasicLink link = (BasicLink) o;\r
+                route.updateRoute(link, allChildCells, graph);\r
+            }\r
+        }\r
+    }\r
+\r
+}\r
index 564fe63..efa60f9 100644 (file)
@@ -206,6 +206,7 @@ public final class XcosMessages {
     public static final String LINK_STYLE_STRAIGHT = Messages.gettext("Straight");
     public static final String LINK_STYLE_HORIZONTAL = Messages.gettext("Horizontal");
     public static final String LINK_STYLE_VERTICAL = Messages.gettext("Vertical");
+    public static final String LINK_STYLE_OPTIMAL = Messages.gettext("Optimal");
 
     public static final String DEBUG_LEVEL_LABEL = "<html>" + Messages.gettext("Set debugging level (0,1,2,3) <br/> it performs scicos_debug(n)") + "</html>";
     public static final String SET_DEBUG = Messages.gettext("Execution trace and Debug");
diff --git a/scilab/modules/xcos/src/java/org/scilab/modules/xcos/utils/XcosRoute.java b/scilab/modules/xcos/src/java/org/scilab/modules/xcos/utils/XcosRoute.java
new file mode 100755 (executable)
index 0000000..eae33b8
--- /dev/null
@@ -0,0 +1,481 @@
+/*\r
+ * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab\r
+ * Copyright (C) 2015 - Chenfeng ZHU\r
+ *\r
+ * This file must be used under the terms of the CeCILL.\r
+ * This source file is licensed as described in the file COPYING, which\r
+ * you should have received as part of this distribution.  The terms\r
+ * are also available at\r
+ * http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt\r
+ *\r
+ */\r
+\r
+package org.scilab.modules.xcos.utils;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Arrays;\r
+import java.util.List;\r
+\r
+import org.scilab.modules.xcos.block.BasicBlock;\r
+import org.scilab.modules.xcos.block.SplitBlock;\r
+import org.scilab.modules.xcos.graph.XcosDiagram;\r
+import org.scilab.modules.xcos.link.BasicLink;\r
+import org.scilab.modules.xcos.port.BasicPort;\r
+import org.scilab.modules.xcos.port.Orientation;\r
+import org.scilab.modules.xcos.port.command.CommandPort;\r
+import org.scilab.modules.xcos.port.control.ControlPort;\r
+import org.scilab.modules.xcos.port.input.InputPort;\r
+import org.scilab.modules.xcos.port.output.OutputPort;\r
+\r
+import com.mxgraph.model.mxGeometry;\r
+import com.mxgraph.model.mxGraphModel;\r
+import com.mxgraph.model.mxICell;\r
+import com.mxgraph.util.mxPoint;\r
+import com.mxgraph.view.mxCellState;\r
+\r
+public class XcosRoute {\r
+\r
+    private List<mxPoint> listRoute = new ArrayList<mxPoint>(0);\r
+\r
+    /**\r
+     * Update the Edge.\r
+     *\r
+     * @param link\r
+     * @param graph\r
+     */\r
+    public void updateRoute(BasicLink link, Object[] allCells, XcosDiagram graph) {\r
+        mxICell sourceCell = link.getSource();\r
+        mxICell targetCell = link.getTarget();\r
+        Object[] allOtherCells = getAllOtherCells(allCells, link, sourceCell, targetCell);\r
+        if (sourceCell != null && targetCell != null) {\r
+            boolean isGetRoute = this.computeRoute(link, allOtherCells, graph);\r
+            if (isGetRoute) {\r
+                List<mxPoint> list = this.getNonRedundantPoints();\r
+                mxGeometry geometry = new mxGeometry();\r
+                geometry.setPoints(list);\r
+                ((mxGraphModel) (graph.getModel())).setGeometry(link, geometry);\r
+                listRoute.clear();\r
+            } else {\r
+                // if it cannot get the route, keep the same or change it to\r
+                // straight or give a pop windows to inform user.\r
+            }\r
+        }\r
+    }\r
+\r
+    /**\r
+     * Get the turning points for the optimal route. If the straight route is the optimal route,\r
+     * return null.\r
+     *\r
+     * @param link\r
+     * @param allCells\r
+     * @return list of turning points\r
+     */\r
+    private boolean computeRoute(BasicLink link, Object[] allCells, XcosDiagram graph) {\r
+        listRoute.clear();\r
+        mxICell sourceCell = link.getSource();\r
+        mxICell targetCell = link.getTarget();\r
+        // if the link is not connected with BasicPort.\r
+        if (!(sourceCell instanceof BasicPort) || !(targetCell instanceof BasicPort)) {\r
+            return false;\r
+        }\r
+        Orientation sourcePortOrien = null;\r
+        Orientation targetPortOrien = null;\r
+        double srcx = 0;\r
+        double srcy = 0;\r
+        double tgtx = 0;\r
+        double tgty = 0;\r
+        mxPoint sourcePoint = new mxPoint(srcx, srcy);\r
+        mxPoint targetPoint = new mxPoint(tgtx, tgty);\r
+        // if source is a port, get a new start point.\r
+        if (sourceCell instanceof BasicPort) {\r
+            mxCellState state = graph.getView().getState(sourceCell);\r
+            if (state != null) {\r
+                srcx = state.getCenterX();\r
+                srcy = state.getCenterY();\r
+                BasicPort sourcePort = (BasicPort) sourceCell;\r
+                sourcePortOrien = getPortRelativeOrientation(sourcePort, graph);\r
+            }\r
+        }\r
+        // if target is a port, get a new end point.\r
+        if (targetCell instanceof BasicPort) {\r
+            mxCellState state = graph.getView().getState(targetCell);\r
+            if (state != null) {\r
+                tgtx = state.getCenterX();\r
+                tgty = state.getCenterY();\r
+                BasicPort targetPort = (BasicPort) targetCell;\r
+                targetPortOrien = getPortRelativeOrientation(targetPort, graph);\r
+            }\r
+        }\r
+        // if source belongs to a SplitBlock\r
+        if (sourceCell.getParent() instanceof SplitBlock) {\r
+            srcx = sourceCell.getParent().getGeometry().getCenterX();\r
+            srcy = sourceCell.getParent().getGeometry().getCenterY();\r
+        }\r
+        // if target is a SplitBlock\r
+        if (targetCell.getParent() instanceof SplitBlock) {\r
+            tgtx = targetCell.getParent().getGeometry().getCenterX();\r
+            tgty = targetCell.getParent().getGeometry().getCenterY();\r
+        }\r
+        // if two ports are aligned and there are no blocks between them,\r
+        // use straight route.\r
+        if ((XcosRouteUtils.isStrictlyAligned(srcx, srcy, tgtx, tgty))\r
+                && !XcosRouteUtils.checkObstacle(srcx, srcy, tgtx, tgty, allCells)) {\r
+            return true;\r
+        }\r
+        // re-calculate the orientation for the SplitBlock.\r
+        if (sourceCell.getParent() instanceof SplitBlock) {\r
+            sourcePortOrien = this.getNewOrientation(sourceCell, srcx, srcy, targetCell, tgtx, tgty, link, graph);\r
+        }\r
+        if (targetCell.getParent() instanceof SplitBlock) {\r
+            targetPortOrien = this.getNewOrientation(targetCell, tgtx, tgty, sourceCell, srcx, srcy, link, graph);\r
+        }\r
+        sourcePoint = getPointAwayPort(sourceCell, srcx, srcy, sourcePortOrien, allCells, graph);\r
+        targetPoint = getPointAwayPort(targetCell, tgtx, tgty, targetPortOrien, allCells, graph);\r
+        List<mxPoint> list = XcosRouteUtils.getSimpleRoute(sourcePoint, sourcePortOrien, targetPoint,\r
+                             targetPortOrien, allCells);\r
+        if (list != null && list.size() > 0) {\r
+            listRoute.addAll(list);\r
+            return true;\r
+        } else {\r
+            list = XcosRouteUtils.getComplexRoute(sourcePoint, sourcePortOrien, targetPoint, targetPortOrien,\r
+                                                  allCells, XcosRouteUtils.TRY_TIMES);\r
+            if (list != null && list.size() > 0) {\r
+                listRoute.addAll(list);\r
+                return true;\r
+            }\r
+        }\r
+        return false;\r
+    }\r
+\r
+    /**\r
+     * Remove the redundancy points from the route.\r
+     *\r
+     * @return a list without non-redundant points\r
+     */\r
+    private List<mxPoint> getNonRedundantPoints() {\r
+        List<mxPoint> list = new ArrayList<mxPoint>(0);\r
+        if (listRoute.size() > 2) {\r
+            list.add(listRoute.get(0));\r
+            for (int i = 1; i < listRoute.size() - 1; i++) {\r
+                mxPoint p1 = list.get(list.size() - 1);\r
+                mxPoint p2 = listRoute.get(i);\r
+                mxPoint p3 = listRoute.get(i + 1);\r
+                if (XcosRouteUtils.pointInLineSegment(p2.getX(), p2.getY(), p1.getX(), p1.getY(), p3.getX(),\r
+                                                      p3.getY())) {\r
+                    // if p2 is in the line segment between p1 and p3, remove it.\r
+                    continue;\r
+                } else {\r
+                    list.add(p2);\r
+                }\r
+            }\r
+            list.add(listRoute.get(listRoute.size() - 1));\r
+        } else {\r
+            // if the route has less than 3 points, there is no redundancy.\r
+            list.addAll(listRoute);\r
+        }\r
+        return list;\r
+    }\r
+\r
+    /**\r
+     * According to the relative position (orientation) of the port, get a point which is\r
+     * XcosRoute.BEAUTY_DISTANCE away from the port and out of block.\r
+     *\r
+     * @param port\r
+     * @param portX\r
+     * @param portY\r
+     * @param graph\r
+     * @return\r
+     */\r
+    private mxPoint getPointAwayPort(mxICell port, double portX, double portY, Orientation orien,\r
+                                     Object[] allCells, XcosDiagram graph) {\r
+        mxPoint point = new mxPoint(portX, portY);\r
+        double distance = XcosRouteUtils.BEAUTY_AWAY_DISTANCE;\r
+        if (port.getParent() instanceof SplitBlock) {\r
+            distance = XcosRouteUtils.SPLITBLOCK_AWAY_DISTANCE;\r
+        }\r
+        switch (orien) {\r
+            case EAST:\r
+                point.setX(point.getX() + distance);\r
+                while (Math.abs(point.getX() - portX) > XcosRouteUtils.BEAUTY_AWAY_REVISION\r
+                        && (XcosRouteUtils.checkObstacle(portX, portY, point.getX(), point.getY(), allCells) || XcosRouteUtils\r
+                            .checkPointInBlocks(point.getX(), point.getY(), allCells))) {\r
+                    point.setX(point.getX() - XcosRouteUtils.BEAUTY_AWAY_REVISION);\r
+                }\r
+                break;\r
+            case SOUTH:\r
+                point.setY(point.getY() + distance);\r
+                while (Math.abs(point.getY() - portY) > XcosRouteUtils.BEAUTY_AWAY_REVISION\r
+                        && (XcosRouteUtils.checkObstacle(portX, portY, point.getX(), point.getY(), allCells) || XcosRouteUtils\r
+                            .checkPointInBlocks(point.getX(), point.getY(), allCells))) {\r
+                    point.setY(point.getY() - XcosRouteUtils.BEAUTY_AWAY_REVISION);\r
+                }\r
+                break;\r
+            case WEST:\r
+                point.setX(point.getX() - distance);\r
+                while (Math.abs(point.getX() - portX) > XcosRouteUtils.BEAUTY_AWAY_REVISION\r
+                        && (XcosRouteUtils.checkObstacle(portX, portY, point.getX(), point.getY(), allCells) || XcosRouteUtils\r
+                            .checkPointInBlocks(point.getX(), point.getY(), allCells))) {\r
+                    point.setX(point.getX() + XcosRouteUtils.BEAUTY_AWAY_REVISION);\r
+                }\r
+                break;\r
+            case NORTH:\r
+                point.setY(point.getY() - distance);\r
+                while (Math.abs(point.getY() - portY) > XcosRouteUtils.BEAUTY_AWAY_REVISION\r
+                        && (XcosRouteUtils.checkObstacle(portX, portY, point.getX(), point.getY(), allCells) || XcosRouteUtils\r
+                            .checkPointInBlocks(point.getX(), point.getY(), allCells))) {\r
+                    point.setY(point.getY() + XcosRouteUtils.BEAUTY_AWAY_REVISION);\r
+                }\r
+                break;\r
+        }\r
+        return point;\r
+    }\r
+\r
+    /**\r
+     * As BasicPort.getOrientation is the default orientation, the Orientation is not correct when\r
+     * the block is mirrored or flipped. This method could get the current Orientation of the port.\r
+     *\r
+     * @param port\r
+     * @param graph\r
+     * @return\r
+     */\r
+    private Orientation getPortRelativeOrientation(BasicPort port, XcosDiagram graph) {\r
+        // the coordinate (x,y) for the port.\r
+        double portx = graph.getView().getState(port).getCenterX();\r
+        double porty = graph.getView().getState(port).getCenterY();\r
+        // the coordinate (x,y) and the width-height for the parent block\r
+        mxICell parent = port.getParent();\r
+        double blockx = graph.getView().getState(parent).getCenterX();\r
+        double blocky = graph.getView().getState(parent).getCenterY();\r
+        double blockw = parent.getGeometry().getWidth();\r
+        double blockh = parent.getGeometry().getHeight();\r
+        // calculate relative coordinate based on the center of parent block.\r
+        portx -= blockx;\r
+        porty -= blocky;\r
+        Orientation orientation = port.getOrientation();\r
+        if ((portx) >= blockw * Math.abs(porty) / blockh) { // x>=w*|y|/h\r
+            orientation = Orientation.EAST;\r
+        } else if (porty >= blockh * Math.abs(portx) / blockw) { // y>=h*|x|/w\r
+            orientation = Orientation.SOUTH;\r
+        } else if (portx <= -blockw * Math.abs(porty) / blockh) { // x<=-w*|y|/h\r
+            orientation = Orientation.WEST;\r
+        } else if (porty <= -blockh * Math.abs(portx) / blockw) { // y<=-h*|x|/w\r
+            orientation = Orientation.NORTH;\r
+        }\r
+        return orientation;\r
+    }\r
+\r
+    /**\r
+     * Special use to calculate the orientation when\r
+     * <ol>\r
+     * <li>it is a SplitBlock.</li>\r
+     * <li>there is no connection.</li>\r
+     * <ol>\r
+     *\r
+     * @param cell\r
+     * @param cx\r
+     * @param cy\r
+     * @param otherCell\r
+     * @param ox\r
+     * @param oy\r
+     * @param link\r
+     * @param graph\r
+     * @return\r
+     */\r
+    private Orientation getNewOrientation(mxICell cell, double cx, double cy, mxICell otherCell, double ox,\r
+                                          double oy, BasicLink link, XcosDiagram graph) {\r
+        Orientation orientation = Orientation.EAST;\r
+        if (cell.getParent() instanceof SplitBlock) {\r
+            SplitBlock block = (SplitBlock) cell.getParent();\r
+            Orientation inputOrien = this.getSplitBlockInputOrientation(block, graph);\r
+            if ((cell instanceof InputPort) || (cell instanceof ControlPort)) {\r
+                // if it is the InputPort/ControlPort of the SplitBlock,\r
+                orientation = inputOrien;\r
+            } else if ((cell instanceof OutputPort) || (cell instanceof CommandPort)) {\r
+                // if it is one of the OutputPorts/CommandPorts of the SplitBlock,\r
+                // it depends on the Orientation of InputPort and the other OutputPort.\r
+                BasicPort port = (BasicPort) cell;\r
+                BasicPort otherPort = null;\r
+                if (port == block.getOut1()) {\r
+                    otherPort = block.getOut2();\r
+                } else {\r
+                    otherPort = block.getOut1();\r
+                }\r
+                mxICell otherLink = otherPort.getEdgeAt(0);\r
+                if (otherLink instanceof BasicLink) {\r
+                    mxICell otherTarget = ((BasicLink) otherLink).getTarget();\r
+                    mxPoint otgtPoint = this.getCenterPoint(otherTarget, graph);\r
+                    double otx = otgtPoint.getX();\r
+                    double oty = otgtPoint.getY();\r
+                    double otcx = cx - otx;\r
+                    double otcy = cy - oty;\r
+                    double otox = ox - otx;\r
+                    double otoy = oy - oty;\r
+                    double value = (otcx * otoy) - (otox * otcy);\r
+                    if (ox >= cx && oy <= cy) {\r
+                        // when target is on NORTHEAST to source\r
+                        if (value >= 0 && inputOrien != Orientation.NORTH) {\r
+                            // other OutputPort is on the right\r
+                            orientation = Orientation.NORTH;\r
+                        } else if (inputOrien != Orientation.EAST) {\r
+                            // other OutputPort is on the left\r
+                            orientation = Orientation.EAST;\r
+                        } else {\r
+                            orientation = Orientation.NORTH;\r
+                        }\r
+                    } else if (ox >= cx && oy >= cy) {\r
+                        // when target is on SOUTHEAST to source\r
+                        if (value >= 0 && inputOrien != Orientation.EAST) {\r
+                            // other OutputPort is on the right\r
+                            orientation = Orientation.EAST;\r
+                        } else if (inputOrien != Orientation.SOUTH) {\r
+                            // other OutputPort is on the left\r
+                            orientation = Orientation.SOUTH;\r
+                        } else {\r
+                            orientation = Orientation.EAST;\r
+                        }\r
+                    } else if (ox <= cx && oy <= cy) {\r
+                        // when target is on NORTHWEST to source\r
+                        if (value >= 0 && inputOrien != Orientation.WEST) {\r
+                            // other OutputPort is on the right\r
+                            orientation = Orientation.WEST;\r
+                        } else if (inputOrien != Orientation.NORTH) {\r
+                            // other OutputPort is on the left\r
+                            orientation = Orientation.NORTH;\r
+                        } else {\r
+                            orientation = Orientation.WEST;\r
+                        }\r
+                    } else if (ox <= cx && oy >= cy) {\r
+                        // when target is on SOUTHWEST to source\r
+                        if (value >= 0 && inputOrien != Orientation.SOUTH) {\r
+                            // other OutputPort is on the right\r
+                            orientation = Orientation.SOUTH;\r
+                        } else if (inputOrien != Orientation.WEST) {\r
+                            // other OutputPort is on the left\r
+                            orientation = Orientation.WEST;\r
+                        } else {\r
+                            orientation = Orientation.SOUTH;\r
+                        }\r
+                    }\r
+                }\r
+            }\r
+        }\r
+        return orientation;\r
+    }\r
+\r
+    /**\r
+     * Get the Orientation of the InputPort of a SplitBlock.\r
+     *\r
+     * @param block\r
+     *            the SplitBlock\r
+     * @return the orientation of its InputPort.\r
+     */\r
+    private Orientation getSplitBlockInputOrientation(SplitBlock block, XcosDiagram graph) {\r
+        Orientation orientation = Orientation.EAST;\r
+        BasicPort inp = block.getIn();\r
+        // the position of the Input\r
+        double inX = block.getGeometry().getCenterX();\r
+        double inY = block.getGeometry().getCenterY();\r
+        mxICell link = inp.getEdgeAt(0);\r
+        // the position of the source\r
+        double srcX = 0;\r
+        double srcY = 0;\r
+        if (link instanceof BasicLink) {\r
+            mxICell source = ((BasicLink) link).getSource();\r
+            mxPoint srcPoint = this.getCenterPoint(source, graph);\r
+            srcX = srcPoint.getX();\r
+            srcY = srcPoint.getY();\r
+        }\r
+        // the relative position of source to Input\r
+        double dx = srcX - inX;\r
+        double dy = srcY - inY;\r
+        if (dx >= Math.abs(dy)) { // x>=|y|\r
+            orientation = Orientation.EAST; // source is on the east of Input.\r
+        } else if (dy >= Math.abs(dx)) { // y>=|x|\r
+            orientation = Orientation.SOUTH;\r
+        } else if (dx <= -Math.abs(dy)) { // x<=-|y|\r
+            orientation = Orientation.WEST;\r
+        } else if (dy <= -Math.abs(dx)) { // y<=-|x|\r
+            orientation = Orientation.NORTH;\r
+        }\r
+        return orientation;\r
+    }\r
+\r
+    /**\r
+     * Get the position of a cell.\r
+     *\r
+     * @param cell\r
+     * @return\r
+     */\r
+    private mxPoint getCenterPoint(mxICell cell, XcosDiagram graph) {\r
+        mxPoint point = new mxPoint(0, 0);\r
+        if (cell instanceof BasicPort) {\r
+            BasicPort port = (BasicPort) cell;\r
+            mxICell parent = port.getParent();\r
+            if (parent instanceof SplitBlock) {\r
+                // if it belongs to a SplitBlock, use SplitBlock's geometry.\r
+                point.setX(parent.getGeometry().getCenterX());\r
+                point.setY(parent.getGeometry().getCenterY());\r
+            } else {\r
+                mxCellState state = graph.getView().getState(cell);\r
+                if (state != null) {\r
+                    point.setX(state.getCenterX());\r
+                    point.setY(state.getCenterY());\r
+                }\r
+            }\r
+        } else if (cell instanceof BasicBlock) {\r
+            // if it is a block, use its geometry.\r
+            BasicBlock block = (BasicBlock) cell;\r
+            point.setX(block.getGeometry().getCenterX());\r
+            point.setY(block.getGeometry().getCenterY());\r
+        }\r
+        return point;\r
+    }\r
+\r
+    /**\r
+     * Remove the selves from the array of all.<br/>\r
+     * except for selves, SplitBlock and the ports of links in selves. add other ports of blocks.\r
+     *\r
+     * @param all\r
+     * @param self\r
+     *            If self's source port or target port belongs to a SpliBlock, remove this\r
+     *            SplitBlock, too.\r
+     * @return a new array of all objects excluding selves\r
+     */\r
+    private Object[] getAllOtherCells(Object[] all, Object... self) {\r
+        List<Object> listNotObs = new ArrayList<Object>(0);\r
+        listNotObs.addAll(Arrays.asList(self));\r
+        for (Object obj : self) {\r
+            // if self contains a link\r
+            if (obj instanceof BasicLink) {\r
+                BasicLink link = (BasicLink) obj;\r
+                // in these selves, if the source/target of this link belongs to a SplitBlock,\r
+                // remove it.\r
+                if (link.getSource() != null && link.getSource().getParent() instanceof SplitBlock) {\r
+                    listNotObs.add(link.getSource().getParent());\r
+                }\r
+                if (link.getTarget() != null && link.getTarget().getParent() instanceof SplitBlock) {\r
+                    listNotObs.add(link.getTarget().getParent());\r
+                }\r
+            }\r
+        }\r
+        List<Object> listnew = new ArrayList<Object>(0);\r
+        for (Object o : all) {\r
+            // if it does not belongs to self,\r
+            if (!listNotObs.contains(o) && !(o instanceof SplitBlock)) {\r
+                // only add normal Blocks.\r
+                listnew.add(o);\r
+                // add the ports of the block.\r
+                if (o instanceof BasicBlock) {\r
+                    BasicBlock block = (BasicBlock) o;\r
+                    for (int i = 0; i < block.getChildCount(); i++) {\r
+                        if (!listNotObs.contains(block.getChildAt(i))) {\r
+                            listnew.add(block.getChildAt(i));\r
+                        }\r
+                    }\r
+                }\r
+            }\r
+        }\r
+        Object[] newAll = listnew.toArray();\r
+        return newAll;\r
+    }\r
+}\r
diff --git a/scilab/modules/xcos/src/java/org/scilab/modules/xcos/utils/XcosRouteUtils.java b/scilab/modules/xcos/src/java/org/scilab/modules/xcos/utils/XcosRouteUtils.java
new file mode 100755 (executable)
index 0000000..85b6b12
--- /dev/null
@@ -0,0 +1,958 @@
+/*\r
+ * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab\r
+ * Copyright (C) 2015 - Chenfeng ZHU\r
+ *\r
+ * This file must be used under the terms of the CeCILL.\r
+ * This source file is licensed as described in the file COPYING, which\r
+ * you should have received as part of this distribution.  The terms\r
+ * are also available at\r
+ * http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt\r
+ *\r
+ */\r
+\r
+package org.scilab.modules.xcos.utils;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Collections;\r
+import java.util.LinkedHashMap;\r
+import java.util.List;\r
+import java.util.Map;\r
+\r
+import org.scilab.modules.xcos.block.BasicBlock;\r
+import org.scilab.modules.xcos.block.SplitBlock;\r
+import org.scilab.modules.xcos.link.BasicLink;\r
+import org.scilab.modules.xcos.port.BasicPort;\r
+import org.scilab.modules.xcos.port.Orientation;\r
+\r
+import com.mxgraph.model.mxCell;\r
+import com.mxgraph.model.mxGeometry;\r
+import com.mxgraph.model.mxICell;\r
+import com.mxgraph.util.mxPoint;\r
+import com.mxgraph.util.mxUtils;\r
+\r
+/**\r
+ * Provide methods to calculate the route.\r
+ *\r
+ */\r
+public abstract class XcosRouteUtils {\r
+\r
+    /**\r
+     * The error which can be accepted as it is aligned strictly.\r
+     */\r
+    public final static double ALIGN_STRICT_ERROR = 2;\r
+\r
+    /**\r
+     * The distance for a point away to the port.\r
+     */\r
+    public final static double BEAUTY_AWAY_DISTANCE = 40;\r
+    public final static double BEAUTY_AWAY_REVISION = 10;\r
+    public final static double SPLITBLOCK_AWAY_DISTANCE = 15;\r
+\r
+    /**\r
+     * Define a normal half size of block to avoid.\r
+     */\r
+    public final static double NORMAL_BLOCK_SIZE = 40;\r
+\r
+    /**\r
+     * Times trying to find a complex route.\r
+     */\r
+    public final static int TRY_TIMES = 3;\r
+\r
+    /**\r
+     * Check whether the two points are strictly aligned(vertical or horizontal) or not. (The\r
+     * accepted error is <code>XcosRoute.ALIGN_STRICT_ERROR</code>)\r
+     *\r
+     * @param x1\r
+     *            the x-coordinate of the first point\r
+     * @param y1\r
+     *            the y-coordinate of the first point\r
+     * @param x2\r
+     *            the x-coordinate of the second point\r
+     * @param y2\r
+     *            the y-coordinate of the second point\r
+     * @return <b>true</b> if two points are aligned.\r
+     */\r
+    protected static boolean isStrictlyAligned(double x1, double y1, double x2, double y2) {\r
+        double error = XcosRouteUtils.ALIGN_STRICT_ERROR;\r
+        if (Math.abs(x2 - x1) < error) {\r
+            return true;\r
+        }\r
+        if (Math.abs(y2 - y1) < error) {\r
+            return true;\r
+        }\r
+        return false;\r
+    }\r
+\r
+    /**\r
+     * Get all points of one link including the source port and target port.\r
+     *\r
+     * @param link\r
+     * @return\r
+     */\r
+    protected static List<mxPoint> getLinkPoints(BasicLink link) {\r
+        List<mxPoint> list = new ArrayList<mxPoint>(0);\r
+        mxPoint offset;\r
+        // add the source point.\r
+        mxICell source = link.getSource();\r
+        if (source != null) {\r
+            mxGeometry sourceGeo = source.getGeometry();\r
+            double sourceX = sourceGeo.getCenterX();\r
+            double sourceY = sourceGeo.getCenterY();\r
+            mxICell sourceParent = source.getParent();\r
+            mxGeometry srcParGeo = sourceParent.getGeometry();\r
+            if (srcParGeo == null) {\r
+                srcParGeo = new mxGeometry(0, 0, 0, 0);\r
+            }\r
+            offset = sourceGeo.getOffset();\r
+            if (offset == null) {\r
+                offset = new mxPoint(0, 0);\r
+            }\r
+            if (sourceGeo.isRelative()) {\r
+                sourceX = srcParGeo.getX() + sourceGeo.getX() * srcParGeo.getWidth() + offset.getX();\r
+                sourceY = srcParGeo.getY() + sourceGeo.getY() * srcParGeo.getHeight() + offset.getY();\r
+            } else {\r
+                sourceX = srcParGeo.getX() + sourceGeo.getX() + offset.getX();\r
+                sourceY = srcParGeo.getY() + sourceGeo.getY() + offset.getY();\r
+            }\r
+            list.add(new mxPoint(sourceX, sourceY));\r
+        }\r
+        // add all the turning points.\r
+        if (link.getGeometry().getPoints() != null) {\r
+            list.addAll(link.getGeometry().getPoints());\r
+        }\r
+        // add the target point.\r
+        mxICell target = link.getTarget();\r
+        if (target != null) {\r
+            mxGeometry targetGeo = target.getGeometry();\r
+            double targetX = targetGeo.getCenterX();\r
+            double targetY = targetGeo.getCenterY();\r
+            mxICell targetParent = target.getParent();\r
+            mxGeometry tgtParGeo = targetParent.getGeometry();\r
+            if (tgtParGeo == null) {\r
+                tgtParGeo = new mxGeometry(0, 0, 0, 0);\r
+            }\r
+            offset = targetGeo.getOffset();\r
+            if (offset == null) {\r
+                offset = new mxPoint(0, 0);\r
+            }\r
+            if (targetGeo.isRelative()) {\r
+                targetX = tgtParGeo.getX() + targetGeo.getX() * tgtParGeo.getWidth() + offset.getX();\r
+                targetY = tgtParGeo.getY() + targetGeo.getY() * tgtParGeo.getHeight() + offset.getY();\r
+            } else {\r
+                targetX = tgtParGeo.getX() + targetGeo.getX() + offset.getX();\r
+                targetY = tgtParGeo.getY() + targetGeo.getY() + offset.getY();\r
+            }\r
+            list.add(new mxPoint(targetX, targetY));\r
+        }\r
+        return list;\r
+    }\r
+\r
+    /**\r
+     * Check whether there are blocks between two points.\r
+     *\r
+     * @param x1\r
+     *            the x-coordinate of the first point of the line\r
+     * @param y1\r
+     *            the y-coordinate of the first point of the line\r
+     * @param x2\r
+     *            the x-coordinate of the second point of the line\r
+     * @param y2\r
+     *            the y-coordinate of the second point of the line\r
+     * @param allCells\r
+     * @return <b>true</b> if there is at least one blocks in the line.\r
+     */\r
+    protected static boolean checkObstacle(double x1, double y1, double x2, double y2, Object[] allCells) {\r
+        for (Object o : allCells) {\r
+            if (o instanceof mxCell) {\r
+                mxCell c = (mxCell) o;\r
+                if (c instanceof BasicLink) {\r
+                    BasicLink l = (BasicLink) c;\r
+                    if (checkLinesIntersection(x1, y1, x2, y2, l)) {\r
+                        // check intersection.\r
+                        // return true;\r
+                    }\r
+                    if (checkLinesCoincide(x1, y1, x2, y2, l)) {\r
+                        // check superimposition.\r
+                        return true;\r
+                    }\r
+                    if (pointInLink(x1, y1, l) || pointInLink(x2, y2, l)) {\r
+                        return true;\r
+                    }\r
+                } else {\r
+                    mxGeometry geo = c.getGeometry();\r
+                    mxGeometry newGeo = new mxGeometry(geo.getX(), geo.getY(), geo.getWidth(), geo.getHeight());\r
+                    // if it is a BasicPort, re-calculate its geometry position.\r
+                    if (c.getParent().getGeometry() != null && c instanceof BasicPort) {\r
+                        double x = c.getParent().getGeometry().getX() + newGeo.getX();\r
+                        newGeo.setX(x);\r
+                        double y = c.getParent().getGeometry().getY() + newGeo.getY();\r
+                        newGeo.setY(y);\r
+                    }\r
+                    mxPoint interction = newGeo.intersectLine(x1, y1, x2, y2);\r
+                    if (interction != null) {\r
+                        return true;\r
+                    }\r
+                }\r
+            }\r
+        }\r
+        return false;\r
+    }\r
+\r
+    /**\r
+     * Check whether a point is in the range of one block (including the ports).\r
+     *\r
+     * @param x\r
+     *            the x-coordinate of the point\r
+     * @param y\r
+     *            the y-coordinate of the point\r
+     * @param allCells\r
+     * @return <b>true</b> if one point is in one block.\r
+     */\r
+    protected static boolean checkPointInBlocks(double x, double y, Object[] allCells) {\r
+        for (Object o : allCells) {\r
+            if (o instanceof BasicBlock) {\r
+                BasicBlock block = (BasicBlock) o;\r
+                // if it is a BasicBlock, re-calculate its size with its port.\r
+                double ix = 0;\r
+                double iy = 0;\r
+                double iw = 0;\r
+                double ih = 0;\r
+                mxGeometry g = block.getGeometry();\r
+                for (int i = 0; i < block.getChildCount(); i++) {\r
+                    mxICell child = block.getChildAt(i);\r
+                    if (child.getGeometry() == null) {\r
+                        continue;\r
+                    }\r
+                    mxGeometry childGeo = new mxGeometry(child.getGeometry().getX(), child.getGeometry().getY(),\r
+                                                         child.getGeometry().getWidth(), child.getGeometry().getHeight());\r
+                    if (child.getGeometry().isRelative()) {\r
+                        childGeo.setX(g.getWidth() * childGeo.getX());\r
+                        childGeo.setY(g.getHeight() * childGeo.getY());\r
+                    }\r
+                    if (childGeo.getX() < 0) {\r
+                        ix = childGeo.getX();\r
+                        iw = Math.abs(ix);\r
+                    }\r
+                    if (childGeo.getX() + childGeo.getWidth() > g.getWidth()) {\r
+                        iw += childGeo.getX() + childGeo.getWidth() - g.getWidth();\r
+                    }\r
+                    if (childGeo.getY() < 0) {\r
+                        iy = childGeo.getY();\r
+                        ih = Math.abs(iy);\r
+                    }\r
+                    if (childGeo.getY() + childGeo.getHeight() > Math.max(block.getGeometry().getHeight(), ih)) {\r
+                        ih += childGeo.getY() + childGeo.getHeight() - g.getHeight();\r
+                    }\r
+                }\r
+                double blockx = g.getX() + ix;\r
+                double blocky = g.getY() + iy;\r
+                double width = g.getWidth() + iw;\r
+                double height = g.getHeight() + ih;\r
+                if (x >= blockx && x <= (blockx + width) && y >= blocky && y < (blocky + height)) {\r
+                    return true;\r
+                }\r
+            }\r
+        }\r
+        return false;\r
+    }\r
+\r
+    /**\r
+     * Check whether two lines have intersection or not.\r
+     *\r
+     * @param x1\r
+     *            the x-coordinate of the first point of the first line\r
+     * @param y1\r
+     *            the y-coordinate of the first point of the first line\r
+     * @param x2\r
+     *            the x-coordinate of the second point of the first line\r
+     * @param y2\r
+     *            the y-coordinate of the second point of the first line\r
+     * @param link\r
+     *            the second link\r
+     * @return <b>true</b> if two lines have intersection(s).\r
+     */\r
+    private static boolean checkLinesIntersection(double x1, double y1, double x2, double y2, BasicLink link) {\r
+        List<mxPoint> listPoints = getLinkPoints(link);\r
+        if (listPoints == null || listPoints.size() <= 1) {\r
+        } else {\r
+            for (int i = 1; i < listPoints.size(); i++) {\r
+                mxPoint point3 = listPoints.get(i - 1);\r
+                mxPoint point4 = listPoints.get(i);\r
+                double x3 = point3.getX();\r
+                double y3 = point3.getY();\r
+                double x4 = point4.getX();\r
+                double y4 = point4.getY();\r
+                mxPoint point = mxUtils.intersection(x1, y1, x2, y2, x3, y3, x4, y4);\r
+                if (point != null) {\r
+                    return true;\r
+                }\r
+            }\r
+        }\r
+        return false;\r
+    }\r
+\r
+    /**\r
+     * Check whether two lines coincide or not. The lines are vertical or horizontal. <br/>\r
+     * <b>NOTE:</b> This method is used to check coincidence, NOT intersection!\r
+     *\r
+     * @param x1\r
+     *            the x-coordinate of the first point of the first line\r
+     * @param y1\r
+     *            the y-coordinate of the first point of the first line\r
+     * @param x2\r
+     *            the x-coordinate of the second point of the first line\r
+     * @param y2\r
+     *            the y-coordinate of the second point of the first line\r
+     * @param link\r
+     *            the second line\r
+     * @return <b>true</b> if two lines coincide completely or partly.\r
+     */\r
+    private static boolean checkLinesCoincide(double x1, double y1, double x2, double y2, BasicLink link) {\r
+        // mxICell source = line.getSource();\r
+        // mxICell target = line.getTarget();\r
+        List<mxPoint> listPoints = new ArrayList<mxPoint>(0);\r
+        if (link.getGeometry().getPoints() == null || link.getGeometry().getPoints().size() == 0) {\r
+            // if the edge is straight or vertical or horizontal style, there is\r
+            // no way to check.\r
+        } else {\r
+            listPoints.add(getLinkPortPosition(link, true));\r
+            listPoints.addAll(link.getGeometry().getPoints());\r
+            listPoints.add(getLinkPortPosition(link, false));\r
+            for (int i = 1; i < listPoints.size(); i++) {\r
+                mxPoint point3 = listPoints.get(i - 1);\r
+                mxPoint point4 = listPoints.get(i);\r
+                double x3 = point3.getX();\r
+                double y3 = point3.getY();\r
+                double x4 = point4.getX();\r
+                double y4 = point4.getY();\r
+                if (linesCoincide(x1, y1, x2, y2, x3, y3, x4, y4)) {\r
+                    return true;\r
+                }\r
+            }\r
+        }\r
+        return false;\r
+    }\r
+\r
+    /**\r
+     * Check whether two lines coincide or not.\r
+     *\r
+     * @param x1\r
+     *            the x-coordinate of the first point of the first line\r
+     * @param y1\r
+     *            the y-coordinate of the first point of the first line\r
+     * @param x2\r
+     *            the x-coordinate of the second point of the first line\r
+     * @param y2\r
+     *            the y-coordinate of the second point of the first line\r
+     * @param x3\r
+     *            the x-coordinate of the first point of the second line\r
+     * @param y3\r
+     *            the y-coordinate of the first point of the second line\r
+     * @param x4\r
+     *            the x-coordinate of the second point of the second line\r
+     * @param y4\r
+     *            the y-coordinate of the second point of the second line\r
+     * @return <b>true</b> if two lines coincide.\r
+     */\r
+    private static boolean linesCoincide(double x1, double y1, double x2, double y2, double x3, double y3,\r
+                                         double x4, double y4) {\r
+        x1 = Math.round(x1);\r
+        y1 = Math.round(y1);\r
+        x2 = Math.round(x2);\r
+        y2 = Math.round(y2);\r
+        x3 = Math.round(x3);\r
+        y3 = Math.round(y3);\r
+        x4 = Math.round(x4);\r
+        y4 = Math.round(y4);\r
+        if (linesStrictlyCoincide(x1, y1, x2, y2, x3, y3, x4, y4)) {\r
+            return true;\r
+        }\r
+        if (x1 == x2) {\r
+            for (double xi = x1 - ALIGN_STRICT_ERROR; xi < x1 + ALIGN_STRICT_ERROR; xi++) {\r
+                xi = Math.round(xi);\r
+                if (linesStrictlyCoincide(xi, y1, xi, y2, x3, y3, x4, y4)) {\r
+                    return true;\r
+                }\r
+            }\r
+        } else if (y1 == y2) {\r
+            for (double yi = y1 - ALIGN_STRICT_ERROR; yi < y1 + ALIGN_STRICT_ERROR; yi++) {\r
+                yi = Math.round(yi);\r
+                if (linesStrictlyCoincide(x1, yi, x2, yi, x3, y3, x4, y4)) {\r
+                    return true;\r
+                }\r
+            }\r
+        }\r
+        return false;\r
+    }\r
+\r
+    /**\r
+     * Check whether two lines strictly coincide or not.\r
+     *\r
+     * @param x1\r
+     *            the x-coordinate of the first point of the first line\r
+     * @param y1\r
+     *            the y-coordinate of the first point of the first line\r
+     * @param x2\r
+     *            the x-coordinate of the second point of the first line\r
+     * @param y2\r
+     *            the y-coordinate of the second point of the first line\r
+     * @param x3\r
+     *            the x-coordinate of the first point of the second line\r
+     * @param y3\r
+     *            the y-coordinate of the first point of the second line\r
+     * @param x4\r
+     *            the x-coordinate of the second point of the second line\r
+     * @param y4\r
+     *            the y-coordinate of the second point of the second line\r
+     * @return <b>true</b> if two lines coincide.\r
+     */\r
+    private static boolean linesStrictlyCoincide(double x1, double y1, double x2, double y2, double x3, double y3,\r
+            double x4, double y4) {\r
+        // the first line is inside the second line.\r
+        if (pointInLineSegment(x1, y1, x3, y3, x4, y4) && pointInLineSegment(x2, y2, x3, y3, x4, y4)) {\r
+            return true;\r
+        }\r
+        // the second line is inside the first line.\r
+        if (pointInLineSegment(x3, y3, x1, y1, x2, y2) && pointInLineSegment(x4, y4, x1, y1, x2, y2)) {\r
+            return true;\r
+        }\r
+        double i = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);\r
+        // two lines are parallel.\r
+        if (i == 0) {\r
+            if (pointInLineSegment(x1, y1, x3, y3, x4, y4) || pointInLineSegment(x2, y2, x3, y3, x4, y4)\r
+                    || pointInLineSegment(x3, y3, x1, y1, x2, y2) || pointInLineSegment(x4, y4, x1, y1, x2, y2)) {\r
+                return true;\r
+            }\r
+        }\r
+        return false;\r
+    }\r
+\r
+    /**\r
+     * Check whether a point is in the Link.\r
+     *\r
+     * @param x\r
+     *            the x-coordinate of the point\r
+     * @param y\r
+     *            the y-coordinate of the point\r
+     * @param link\r
+     * @return <b>true</b> if one point is in the Link.\r
+     */\r
+    private static boolean pointInLink(double x, double y, BasicLink link) {\r
+        List<mxPoint> listPoints = link.getPoints(0, false);\r
+        if (listPoints == null || listPoints.size() <= 1) {\r
+        } else {\r
+            for (int i = 1; i < listPoints.size(); i++) {\r
+                mxPoint point1 = listPoints.get(i - 1);\r
+                mxPoint point2 = listPoints.get(i);\r
+                double x1 = point1.getX();\r
+                double y1 = point1.getY();\r
+                double x2 = point2.getX();\r
+                double y2 = point2.getY();\r
+                if (x1 == x2 && x != x1) {\r
+                    continue;\r
+                }\r
+                if (y1 == y2 && y != y1) {\r
+                    continue;\r
+                }\r
+                if (pointInLineSegment(x, y, x1, y1, x2, y2)) {\r
+                    return true;\r
+                }\r
+            }\r
+        }\r
+        return false;\r
+    }\r
+\r
+    /**\r
+     * Check whether the point is in the line segment or not.\r
+     *\r
+     * @param x1\r
+     *            the x-coordinate of the point\r
+     * @param y1\r
+     *            the y-coordinate of the point\r
+     * @param x2\r
+     *            the x-coordinate of the first point of the line\r
+     * @param y2\r
+     *            the y-coordinate of the first point of the line\r
+     * @param x3\r
+     *            the x-coordinate of the second point of the line\r
+     * @param y3\r
+     *            the y-coordinate of the second point of the line\r
+     * @return <b>true</b> if the point is in the line segment.\r
+     */\r
+    protected static boolean pointInLineSegment(double x1, double y1, double x2, double y2, double x3, double y3) {\r
+        if (((x3 - x2) * (y1 - y2) == (x1 - x2) * (y3 - y2)) && (x1 >= Math.min(x2, x3) && x1 <= Math.max(x2, x3))\r
+                && (y1 >= Math.min(y2, y3) && y1 <= Math.max(y2, y3))) {\r
+            return true;\r
+        }\r
+        return false;\r
+    }\r
+\r
+    /**\r
+     * In the method, only 4 turning points at most are supported.\r
+     *\r
+     * @param p1\r
+     *            the point away from the first port\r
+     * @param p2\r
+     *            the point away from the second port\r
+     * @param allCells\r
+     *            all the possible\r
+     * @return\r
+     */\r
+    public static List<mxPoint> getSimpleRoute(mxPoint p1, mxPoint p2, Object[] allCells) {\r
+        return getSimpleRoute(p1, null, p2, null, allCells);\r
+    }\r
+\r
+    /**\r
+     * In the method, only 4 turning points at most are supported.\r
+     *\r
+     * @param p1\r
+     *            the point away from the first port\r
+     * @param o1\r
+     *            the orientation of the first port\r
+     * @param p2\r
+     *            the point away from the second port\r
+     * @param o2\r
+     *            the orientation of the second port\r
+     * @param allCells\r
+     *            all the possible\r
+     * @return\r
+     */\r
+    public static List<mxPoint> getSimpleRoute(mxPoint p1, Orientation o1, mxPoint p2, Orientation o2,\r
+            Object[] allCells) {\r
+        // point1 and point2 are not in the vertical or horizontal line.\r
+        List<mxPoint> listSimpleRoute = new ArrayList<mxPoint>(0);\r
+        List<Double> listX = new ArrayList<Double>(0);\r
+        List<Double> listY = new ArrayList<Double>(0);\r
+        double distance = XcosRouteUtils.NORMAL_BLOCK_SIZE;\r
+        double x1 = p1.getX();\r
+        double y1 = p1.getY();\r
+        double x2 = p2.getX();\r
+        double y2 = p2.getY();\r
+        // simplest situation: directly connect.\r
+        if (o1 == Orientation.EAST || o1 == Orientation.WEST) {\r
+            // if the start is horizontal,\r
+            if (!checkObstacle(x1, y1, x2, y1, allCells) && !checkObstacle(x2, y1, x2, y2, allCells)) {\r
+                listSimpleRoute.add(new mxPoint(x2, y1));\r
+                if (o2 != Orientation.NORTH && o2 != Orientation.SOUTH) {\r
+                    listSimpleRoute.add(p2);\r
+                }\r
+                return listSimpleRoute;\r
+            }\r
+            if (!checkObstacle(x1, y1, x1, y2, allCells) && !checkObstacle(x1, y2, x2, y2, allCells)) {\r
+                listSimpleRoute.add(p1);\r
+                listSimpleRoute.add(new mxPoint(x1, y2));\r
+                if (o2 != Orientation.EAST && o2 != Orientation.WEST) {\r
+                    listSimpleRoute.add(p2);\r
+                }\r
+                return listSimpleRoute;\r
+            }\r
+        } else if (o1 == Orientation.NORTH || o1 == Orientation.SOUTH) {\r
+            // if the start is vertical,\r
+            if (!checkObstacle(x1, y1, x1, y2, allCells) && !checkObstacle(x1, y2, x2, y2, allCells)) {\r
+                listSimpleRoute.add(new mxPoint(x1, y2));\r
+                if (o2 != Orientation.EAST && o2 != Orientation.WEST) {\r
+                    listSimpleRoute.add(p2);\r
+                }\r
+                return listSimpleRoute;\r
+            }\r
+            if (!checkObstacle(x1, y1, x2, y1, allCells) && !checkObstacle(x2, y1, x2, y2, allCells)) {\r
+                listSimpleRoute.add(p1);\r
+                listSimpleRoute.add(new mxPoint(x2, y1));\r
+                if (o2 != Orientation.NORTH && o2 != Orientation.SOUTH) {\r
+                    listSimpleRoute.add(p2);\r
+                }\r
+                return listSimpleRoute;\r
+            }\r
+        }\r
+        if (o1 == Orientation.EAST || o1 == Orientation.WEST) {\r
+            // check the nodes in x-coordinate\r
+            double xmax = Math.max(x1 + distance, x2 + distance);\r
+            double xmin = Math.min(x1 - distance, x2 - distance);\r
+            for (double xi = xmin; xi <= xmax; xi++) {\r
+                if (!checkObstacle(x1, y1, xi, y1, allCells) && !checkObstacle(xi, y1, xi, y2, allCells)\r
+                        && !checkObstacle(xi, y2, x2, y2, allCells)) {\r
+                    listX.add(xi);\r
+                }\r
+            }\r
+            if (listX.size() > 0) {\r
+                double x = choosePoint(listX, x1, x2);\r
+                listSimpleRoute.add(new mxPoint(x, y1));\r
+                listSimpleRoute.add(new mxPoint(x, y2));\r
+                if (o2 != Orientation.EAST && o2 != Orientation.WEST) {\r
+                    listSimpleRoute.add(p2);\r
+                }\r
+                return listSimpleRoute;\r
+            }\r
+            // check the nodes in y-coordinate\r
+            double ymax = Math.max(y1 + distance, y2 + distance);\r
+            double ymin = Math.min(y1 - distance, y2 - distance);\r
+            for (double yi = ymin; yi <= ymax; yi++) {\r
+                if (!checkObstacle(x1, y1, x1, yi, allCells) && !checkObstacle(x1, yi, x2, yi, allCells)\r
+                        && !checkObstacle(x2, yi, x2, y2, allCells)) {\r
+                    listY.add(yi);\r
+                }\r
+            }\r
+            if (listY.size() > 0) {\r
+                double y = choosePoint(listY, y1, y2);\r
+                listSimpleRoute.add(p1);\r
+                listSimpleRoute.add(new mxPoint(x1, y));\r
+                listSimpleRoute.add(new mxPoint(x2, y));\r
+                if (o2 != Orientation.NORTH && o2 != Orientation.SOUTH) {\r
+                    listSimpleRoute.add(p2);\r
+                }\r
+                return listSimpleRoute;\r
+            }\r
+        } else if (o1 == Orientation.NORTH || o1 == Orientation.SOUTH) {\r
+            // check the nodes in y-coordinate\r
+            double ymax = Math.max(y1 + distance, y2 + distance);\r
+            double ymin = Math.min(y1 - distance, y2 - distance);\r
+            for (double yi = ymin; yi <= ymax; yi++) {\r
+                if (!checkObstacle(x1, y1, x1, yi, allCells) && !checkObstacle(x1, yi, x2, yi, allCells)\r
+                        && !checkObstacle(x2, yi, x2, y2, allCells)) {\r
+                    listY.add(yi);\r
+                }\r
+            }\r
+            if (listY.size() > 0) {\r
+                double y = choosePoint(listY, y1, y2);\r
+                listSimpleRoute.add(new mxPoint(x1, y));\r
+                listSimpleRoute.add(new mxPoint(x2, y));\r
+                if (o2 != Orientation.NORTH && o2 != Orientation.SOUTH) {\r
+                    listSimpleRoute.add(p2);\r
+                }\r
+                return listSimpleRoute;\r
+            }\r
+            // check the nodes in x-coordinate\r
+            double xmax = Math.max(x1 + distance, x2 + distance);\r
+            double xmin = Math.min(x1 - distance, x2 - distance);\r
+            for (double xi = xmin; xi <= xmax; xi++) {\r
+                if (!checkObstacle(x1, y1, xi, y1, allCells) && !checkObstacle(xi, y1, xi, y2, allCells)\r
+                        && !checkObstacle(xi, y2, x2, y2, allCells)) {\r
+                    listX.add(xi);\r
+                }\r
+            }\r
+            if (listX.size() > 0) {\r
+                double x = choosePoint(listX, x1, x2);\r
+                listSimpleRoute.add(p1);\r
+                listSimpleRoute.add(new mxPoint(x, y1));\r
+                listSimpleRoute.add(new mxPoint(x, y2));\r
+                if (o2 != Orientation.EAST && o2 != Orientation.WEST) {\r
+                    listSimpleRoute.add(p2);\r
+                }\r
+                return listSimpleRoute;\r
+            }\r
+        }\r
+        return listSimpleRoute;\r
+    }\r
+\r
+    /**\r
+     * Choose a better point (which is the average number in the widest range in a certain density)\r
+     * from the list which contains discrete numbers.\r
+     *\r
+     * @param list\r
+     * @return\r
+     */\r
+    private static double choosePoint(List<Double> list, double p1, double p2) {\r
+        if (list == null || list.size() == 0) {\r
+            return 0;\r
+        }\r
+        Collections.sort(list);\r
+        double nMax = Math.max(p1, p2);\r
+        double nMin = Math.min(p1, p2);\r
+        double start = list.get(0);\r
+        double start_temp = list.get(0);\r
+        double end = list.get(0);\r
+        double end_temp = list.get(0);\r
+        double mid_temp = (end_temp + start_temp) / 2;\r
+        double mid = (end + start) / 2;\r
+        boolean restart = true;\r
+        for (int i = 1; i < list.size(); i++) {\r
+            if (Math.abs(list.get(i) - list.get(i - 1)) <= 1.1) {\r
+                end_temp = list.get(i);\r
+                restart = false;\r
+            } else {\r
+                if (restart) {\r
+                    start_temp = list.get(i);\r
+                    continue;\r
+                }\r
+                mid_temp = (end_temp + start_temp) / 2;\r
+                mid = (end + start) / 2;\r
+                if ((mid_temp < nMin || mid_temp > nMax) && (mid < nMax && mid > nMin)) {\r
+                    // if the new one is out of two points and the previous one\r
+                    // is inside,\r
+                    start_temp = list.get(i);\r
+                    end_temp = list.get(i);\r
+                    restart = true;\r
+                } else if ((Math.abs(end_temp - start_temp) > Math.abs(end - start))\r
+                           || (mid_temp < nMax && mid_temp > nMin) && (mid < nMin || mid > nMax)) {\r
+                    // if the new one in between two points and the previous one\r
+                    // is out of them, or if the new one is longer than the\r
+                    // previous one,\r
+                    start = start_temp;\r
+                    end = end_temp;\r
+                    start_temp = list.get(i);\r
+                    end_temp = list.get(i);\r
+                    restart = true;\r
+                }\r
+            }\r
+        }\r
+        mid_temp = (end_temp + start_temp) / 2;\r
+        mid = (end + start) / 2;\r
+        if ((mid_temp < nMin || mid_temp > nMax) && (mid < nMax && mid > nMin)) {\r
+        } else if ((Math.abs(end_temp - start_temp) > Math.abs(end - start))\r
+                   || ((mid_temp < nMax && mid_temp > nMin) && (mid < nMin || mid > nMax))) {\r
+            start = start_temp;\r
+            end = end_temp;\r
+        }\r
+        return (start + end) / 2;\r
+    }\r
+\r
+    /**\r
+     * Based on getSimpleRoute().\r
+     *\r
+     * @param p1\r
+     *            the point away from the first port\r
+     * @param o1\r
+     *            the orientation of the first port\r
+     * @param p2\r
+     *            the point away from the second port\r
+     * @param o2\r
+     *            the orientation of the second port\r
+     * @param allCells\r
+     *            all the possible obstacles\r
+     * @param times\r
+     * @return\r
+     */\r
+    public static List<mxPoint> getComplexRoute(mxPoint p1, Orientation o1, mxPoint p2, Orientation o2,\r
+            Object[] allCells, int times) {\r
+        if (times <= 0) {\r
+            return null;\r
+        }\r
+        double newPosition = NORMAL_BLOCK_SIZE;\r
+        List<mxPoint> listComplexRoute = new ArrayList<mxPoint>(0);\r
+        List<mxPoint> listTmp = new ArrayList<mxPoint>(0);\r
+        listComplexRoute.add(p1);\r
+        Map<Orientation, mxPoint> mapNewP1 = new LinkedHashMap<Orientation, mxPoint>(0);\r
+        if (o1 == Orientation.EAST || o1 == null) {\r
+            // to EAST\r
+            mxPoint npE = new mxPoint(p1.getX() + newPosition, p1.getY());\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npE.getX(), npE.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npE, Orientation.EAST, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.EAST, npE);\r
+            }\r
+            // to NORTH\r
+            mxPoint npN = new mxPoint(p1.getX(), p1.getY() - newPosition);\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npN.getX(), npN.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npN, Orientation.NORTH, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.NORTH, npN);\r
+            }\r
+            // to SOUTH\r
+            mxPoint npS = new mxPoint(p1.getX(), p1.getY() + newPosition);\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npS.getX(), npS.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npS, Orientation.SOUTH, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.SOUTH, npS);\r
+            }\r
+            if (o1 == null) {\r
+                // to WEST\r
+                mxPoint npW = new mxPoint(p1.getX() - newPosition, p1.getY());\r
+                if (!checkObstacle(p1.getX(), p1.getY(), npW.getX(), npW.getY(), allCells)) {\r
+                    listTmp = getSimpleRoute(npW, Orientation.WEST, p2, o2, allCells);\r
+                    if (listTmp != null && listTmp.size() > 0) {\r
+                        listComplexRoute.addAll(listTmp);\r
+                        return listComplexRoute;\r
+                    }\r
+                    mapNewP1.put(Orientation.WEST, npW);\r
+                }\r
+            }\r
+        } else if (o1 == Orientation.SOUTH) {\r
+            mxPoint npS = new mxPoint(p1.getX(), p1.getY() + newPosition);\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npS.getX(), npS.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npS, Orientation.SOUTH, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.SOUTH, npS);\r
+            }\r
+            mxPoint npW = new mxPoint(p1.getX() - newPosition, p1.getY());\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npW.getX(), npW.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npW, Orientation.WEST, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.WEST, npW);\r
+            }\r
+            mxPoint npE = new mxPoint(p1.getX() + newPosition, p1.getY());\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npE.getX(), npE.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npE, Orientation.EAST, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.EAST, npE);\r
+            }\r
+        } else if (o1 == Orientation.WEST) {\r
+            mxPoint npW = new mxPoint(p1.getX() - newPosition, p1.getY());\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npW.getX(), npW.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npW, Orientation.WEST, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.WEST, npW);\r
+            }\r
+            mxPoint npN = new mxPoint(p1.getX(), p1.getY() - newPosition);\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npN.getX(), npN.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npN, Orientation.NORTH, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.NORTH, npN);\r
+            }\r
+            mxPoint npS = new mxPoint(p1.getX(), p1.getY() + newPosition);\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npS.getX(), npS.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npS, Orientation.SOUTH, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.SOUTH, npS);\r
+            }\r
+        } else if (o1 == Orientation.NORTH) {\r
+            mxPoint npN = new mxPoint(p1.getX(), p1.getY() - newPosition);\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npN.getX(), npN.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npN, Orientation.NORTH, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.NORTH, npN);\r
+            }\r
+            mxPoint npW = new mxPoint(p1.getX() - newPosition, p1.getY());\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npW.getX(), npW.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npW, Orientation.WEST, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.WEST, npW);\r
+            }\r
+            mxPoint npE = new mxPoint(p1.getX() + newPosition, p1.getY());\r
+            if (!checkObstacle(p1.getX(), p1.getY(), npE.getX(), npE.getY(), allCells)) {\r
+                listTmp = getSimpleRoute(npE, Orientation.EAST, p2, o2, allCells);\r
+                if (listTmp != null && listTmp.size() > 0) {\r
+                    listComplexRoute.addAll(listTmp);\r
+                    return listComplexRoute;\r
+                }\r
+                mapNewP1.put(Orientation.EAST, npE);\r
+            }\r
+        }\r
+        for (Map.Entry<Orientation, mxPoint> np1 : mapNewP1.entrySet()) {\r
+            listTmp = getComplexRoute(np1.getValue(), np1.getKey(), p2, o2, allCells, times - 1);\r
+            if (listTmp != null && listTmp.size() > 1) {\r
+                listComplexRoute.addAll(listTmp);\r
+                return listComplexRoute;\r
+            }\r
+        }\r
+        listComplexRoute.clear();\r
+        return listComplexRoute;\r
+    }\r
+\r
+    /**\r
+     * Get the Orientation of a port to its parent.\r
+     *\r
+     * @param port\r
+     * @return\r
+     */\r
+    protected Orientation getPortOrientation(BasicPort port) {\r
+        if (port.getParent() == null) {\r
+            return Orientation.EAST;\r
+        }\r
+        // the coordinate (x,y) for the port.\r
+        mxGeometry portGeo = port.getGeometry();\r
+        double portX = portGeo.getCenterX();\r
+        double portY = portGeo.getCenterY();\r
+        // the coordinate (x,y) and the width-height for the parent block\r
+        mxICell parent = port.getParent();\r
+        mxGeometry parentGeo = parent.getGeometry();\r
+        double blockW = parentGeo.getWidth();\r
+        double blockH = parentGeo.getHeight();\r
+        if (portGeo.isRelative()) {\r
+            portX *= blockW;\r
+            portY *= blockH;\r
+        }\r
+        // calculate relative coordinate based on the center of parent block.\r
+        portX -= blockW / 2;\r
+        portY -= blockH / 2;\r
+        Orientation orientation = Orientation.EAST;\r
+        if ((portX) >= blockW * Math.abs(portY) / blockH) { // x>=w*|y|/h\r
+            orientation = Orientation.EAST;\r
+        } else if (portY >= blockH * Math.abs(portX) / blockW) { // y>=h*|x|/w\r
+            orientation = Orientation.SOUTH;\r
+        } else if (portX <= -blockW * Math.abs(portY) / blockH) { // x<=-w*|y|/h\r
+            orientation = Orientation.WEST;\r
+        } else if (portY <= -blockH * Math.abs(portX) / blockW) { // y<=-h*|x|/w\r
+            orientation = Orientation.NORTH;\r
+        }\r
+        return orientation;\r
+    }\r
+\r
+    /**\r
+     * Get the position of the source/target of a link. If dest is true, return source's position.\r
+     * If dest is false, return target's position.\r
+     *\r
+     * @param link\r
+     * @param dest\r
+     * @return the point of the position\r
+     */\r
+    private static mxPoint getLinkPortPosition(BasicLink link, boolean dest) {\r
+        mxPoint point = new mxPoint();\r
+        mxICell port = null;\r
+        if (dest) {\r
+            port = link.getSource();\r
+        } else {\r
+            port = link.getTarget();\r
+        }\r
+        if (port == null) {\r
+            return null;\r
+        }\r
+        if (port.getParent() instanceof SplitBlock) {\r
+            SplitBlock block = (SplitBlock) port.getParent();\r
+            point.setX(block.getGeometry().getCenterX());\r
+            point.setY(block.getGeometry().getCenterY());\r
+        } else if (port.getParent() instanceof BasicBlock) {\r
+            mxGeometry portGeo = port.getGeometry();\r
+            double portX = portGeo.getCenterX();\r
+            double portY = portGeo.getCenterY();\r
+            double portW = portGeo.getWidth();\r
+            double portH = portGeo.getHeight();\r
+            BasicBlock parent = (BasicBlock) port.getParent();\r
+            mxGeometry parentGeo = parent.getGeometry();\r
+            double blockX = parentGeo.getX();\r
+            double blockY = parentGeo.getY();\r
+            double blockW = parentGeo.getWidth();\r
+            double blockH = parentGeo.getHeight();\r
+            if (portGeo.isRelative()) {\r
+                portX *= blockW;\r
+                portY *= blockH;\r
+            }\r
+            point.setX(blockX + portX + portW / 2);\r
+            point.setY(blockY + portY + portH / 2);\r
+        }\r
+        return point;\r
+    }\r
+\r
+}\r