之前的AStar算法学习笔记博客提到了大神的基于AStar算法的RCP布线算法但是大神给的开源码还有存在可以优化的部分这个博客主要是记录自己优化的过程

大神源码链接：RCP：gef智能寻路算法（A star）

我的AStar的算法学习：AStar算法学习笔记

改进与优化

1. 关于终点出现斜线问题

分析：由于坐标是以起始点作为坐标原点的，所以终点极大可能不在有整数坐标的点位上，找不到路径就会出现斜线直连

解决：大神已经给出了解决的代码：算法：Astar寻路算法改进

我补充下这段代码添加的位置：route() 方法最后获取到路径并放到最终存储路径信息的points过程中，将最后的几个点进行处理即：添加points.addPoint(endPoint)之前。当然我更建议将对通过算法获得的路径进行额外的处理的部分封装到独立的函数中，因为处理终点斜线问题只是很多中的一个。

private void pathExtraControl(PointList points, Point endPoint)
    {
        // 对于终点没有在方格上 出现斜线的处理
        int size = points.size();
        if (size < 3)
            return;
        points.removePoint(size - 1);
        Point pointN1 = points.getLastPoint();
        Point pointN2 = points.getPoint(size - 3);

        if (pointN2.x == pointN1.x)
        {
            points.setPoint(new Point(pointN1.x, endPoint.y), size - 2);
        } else if (pointN2.y == pointN1.y)
        {
            points.setPoint(new Point(endPoint.x, pointN1.y), size - 2);
        }
    }

2.部分线可以经过一些图源

分析：在预读取为每个点设置难易度时存在问题

源码自带了标记openList 和 closeList的方法:test() 我也仿写方法标记预读难度的pool池的方法。

PoolHandler类：

public class PoolHandler extends SquareHandle
{
    public ANodeLevel level = ANodeLevel.EASY;

    public void setOwner(GraphicalEditPart editpart)
    {
        super.setOwner(editpart);
    }

    @Override
    protected DragTracker createDragTracker()
    {
        // TODO Auto-generated method stub
        return null;
    }

    public void validate()
    {
        if (isValid())
            return;
        // getLocator().relocate(this);
        // super.validate();
    }

    protected Color getFillColor()
    {
        ANodeLevel localLevel = getLevel();
        Color color = null;
        if (localLevel.equals(ANodeLevel.EASY))
        {
            color = ColorConstants.lightBlue;
        } else if (localLevel.equals(ANodeLevel.NORMAL))
        {
            color = ColorConstants.yellow;
        } else if (localLevel.equals(ANodeLevel.HARD))
        {
            color = ColorConstants.darkBlue;
        } else if (localLevel.equals(ANodeLevel.DEAD))
        {
            color = ColorConstants.black;
        }
        return color;
    }

    public void paintFigure(Graphics g)
    {
        Rectangle r = getBounds();
        r.shrink(1, 1);
        try
        {
            g.setAlpha(130);
            g.setBackgroundColor(getFillColor());
            g.fillRectangle(r.x, r.y, r.width, r.height);
            g.setForegroundColor(getBorderColor());
            g.drawRectangle(r.x, r.y, r.width, r.height);
        } finally
        {
            // We don't really own rect 'r', so fix it.
            r.expand(1, 1);
        }
    }

    public ANodeLevel getLevel()
    {
        return level;
    }
}

调用这个类的方法：调用这个方法的位置于test相同

private void showPool()
    {
        if ((this.style & SHOWPOOL) != SHOWPOOL)
            return;
        Map<Integer, Map<Integer, ANodeLevel>> pool = preReader.getPool();
        LayerManager manager = (LayerManager) editPart.getViewer()
                .getEditPartRegistry().get(LayerManager.ID);
        FreeformLayer layer = (FreeformLayer) manager
                .getLayer(org.eclipse.gef.LayerConstants.HANDLE_LAYER);
        // 移除之前的oldHandlers
        <strong>removeOldHandles(layer, PoolHandler.class);</strong>
        List<ANode> poolList = new ArrayList<ANode>();
        for (Map.Entry<Integer, Map<Integer, ANodeLevel>> entrySet : pool
                .entrySet())
        {
            int x = entrySet.getKey();
            Map<Integer, ANodeLevel> valueMap = entrySet.getValue();
            for (Map.Entry<Integer, ANodeLevel> valueEntry : valueMap
                    .entrySet())
            {
                int y = valueEntry.getKey();
                ANodeLevel level = valueEntry.getValue();
                ANode node = new ANode(x, y);
                node.setLevel(level);
                poolList.add(node);
            }
        }
        for (ANode poolNode : poolList)
        {
            Point p = poolNode.getPoint(preReader.getStartPoint(), D);
            PoolHandler h = new PoolHandler();
            h.level = poolNode.getLevel();
            h.setBounds(<strong>new Rectangle(p.x, p.y, 5, 5)</strong>);
            h.setOwner((GraphicalEditPart) this.editPart);
            layer.add(h);
        }

    }

这个方法里有两个改变: 为了更加方面直观

1.removeOldHandles()方法: 移除特定类型的handle

@SuppressWarnings("unchecked")
    private void removeOldHandles(FreeformLayer layer, Class<?> clazz)
    {
        List<Figure> removeFigures = new ArrayList<Figure>();
        List<Object> layerFigure = layer.getChildren();
        for (Iterator<Object> iterator = layerFigure.iterator(); iterator.hasNext();)
        {
            Object object = (Object) iterator.next();
            if (clazz == TestHandler.class)
            {
                if (object instanceof TestHandler)
                {
                    TestHandler testHandler = (TestHandler) object;
                    removeFigures.add(testHandler);
                }
            } else if (clazz == PoolHandler.class)
            {
                if (object instanceof PoolHandler)
                {
                    PoolHandler poolHandler = (PoolHandler) object;
                    removeFigures.add(poolHandler);
                }
            } else
            {
                // do nothing
            }
        }
        for (Iterator<Figure> iterator = removeFigures.iterator(); iterator.hasNext();)
        {
            Figure object = (Figure) iterator.next();
            layer.remove(object);
        }
    }

2.将handler的大小改为5,5 很小感觉这个更直观的看到难度设置到了哪些点上黑色的点预读的pool设置了难度的部分细心的你一定发现了问题

基于AStar算法的RCP布线优化改进与优化

问题的明确描述应该修改为：预读难度标记错误问题

分析：如上图所示，图源外面的点应该是可访问的难度：normal 而内部的点应该都是不可访问的难度：hard

代码分析：这是计算

public static int calculateIndex(int v1, int v2, int distance)
    {
        int offset = (v1 - v2) % distance;
        return offset > 0 ? (v1 - v2) / distance + 1 : offset == 0 ? (v1 - v2)
                / distance : (v1 - v2) / distance - 1;
    }

v1是rectangle的位置 v2是starPoint的位置

当offset>0 时，开始节点在左侧（上侧）由于/ 会保留结果的整数部分所以+1就可以找到同源中的点

当offset<0 时，开始节点在右侧（下侧）由于/ 会保留结果的整数部分计算位置时无需进行平移而已有代码为-1 则会出现上述情况

处理方法：offset

public static int calculateIndex(int v1, int v2, int distance)
    {
        int offset = (v1 - v2) % distance;
        return offset > 0 ? (v1 - v2) / distance + 1 : (v1 - v2) / distance ;
    }

3.删除共线点

原有算法：

判断条件：通过全等三角形判断位置：在floyd()中

if (fatherNode.xIndex - currentNode.xIndex == grandNode.xIndex
                    - fatherNode.xIndex
                    && fatherNode.yIndex - currentNode.yIndex == grandNode.yIndex
                            - fatherNode.yIndex)

但由于坐标系的原因都是同间距的点简单跟一些就知道只能去除一条直线上的一半的点

更改为：相似判断则可以删除一条线段两端之间所有的点

// 删除共线终点 根据相似三角形 x1/y1=x2/y2 根据： x1y2=x2y1 判断
			// 	     /|
			// 	    / |
			//         /  |
			//        /   |y2
			//       /|   |
			//      / |y1 |
			//     /  |   |
			//    /___|___|
			//     x1
			//    |--x2---|
			if ((fatherNode.xIndex - currentNode.xIndex) * (grandNode.yIndex - currentNode.yIndex) == (grandNode.xIndex - currentNode.xIndex)
					* (fatherNode.yIndex - currentNode.yIndex)) {
				currentNode.setParent(grandNode);
			} else
				currentNode = fatherNode;
		}

基于AStar算法的RCP布线优化改进与优化

改进与优化

1. 关于终点出现斜线问题

2.部分线可以经过一些图源

3.删除共线点

继续阅读

多关键字排序笔记

大和整数，大整数加法大整数加法与乘法（高精度算法）

最好、最坏、平均情况时间复杂度

算法题解：整数中1出现的次数（从1到n整数中1出现的次数）题目描述代码实现解题思路

维纳滤波在图像复原中的应用

吸血鬼数字问题

堆排序（最小堆）C++

Top N 算法

全智通A+常见问题汇总解答—A+内部领料编辑页面，选择全部仓库查询配件不显示结果

全智通A+常见问题汇总解答—A+某个销售单号与其他销售单号编号规则不一致

全智通A+常见问题汇总解答—A+经营情况报表页面的客户账收银情况中的金额有误

连通分量 | Connected Components | C/C++实现问题描述输入示例输出示例讲解AC代码如下

生成格雷码生成格雷码

Android查缺补漏之SpannableString

线性规划网络流之最短增广路算法

解压缩字符串