如何详细解析JAVA中扫描线算法的实现步骤？

本文共计2568个文字，预计阅读时间需要11分钟。

首先，教科书上的扫描线算法确实是用C++很好地实现的，网上也有许多源码。相比之下，Java实现的基本上没有。所以肖先生还是选择自己打算自己实现这个算法，毕竟实验操作写这个更实际，他自己又是个实践派。

首先说一下，教科书上的扫描线算法确实是用c++很好实现，而且网上有很多源码，而java实现的基本没有（可能是我没看到），所以肖先生还是打算自己码（实验作业写这个而自己又个是写java的猿0.0）。

对于扫描线的实现过程，我只在这里大概讲下书本上的内容（自己去看），主要还是讲一下自己实现时算法的改动和实现方法。

扫描线算法：顾名思义，就是从Ymin开始扫描，然后构建出NET，之后根据NET建立AET。

贴个图：

实现的时候首先是构造NET，因为对于java来说不能像c++一样直接用指针所以我用对象数组和Node类（如下代码）构造了类似数组+指针的数据结构。在实现了NET后开始通过NET实现AET，在这里我改变了一种实现方式，教科书上是一次次遍历扫描线，然后将NET插入AET后进行排序等一系列操作，而我因为是自己写的数据结构，如果说再建个表按书上的方式来最后还得自己实现链表排序等一系列操作。所以我这里直接用一个包含Arraylist的对象数组代替了。我的方法是：直接从NET开始遍历每个节点，得到节点后将它以及它自己之后会引申出的插入AET的节点（比如当前扫描线y=0 节点 X:1 dx:-1 Ymax:3 那之后会插入AET的就是 0 -1 1 和 -1 -1 2 ）将这些节点不论顺序的先插入AET对应扫描线位置的对象数组的list中，将NET中节点全部遍历完之后再最后对AET中每个对象数组的list进行排序。最后得到了NET在进行打印。