基于Y向连贯性算法的多边形扫描线生成（适用于凸多边形和凹多边形）【原理+java实现】

package com.dam.entity.sanLine;
/**
 * @Author dam
 * @create 2023/9/15 14:38
 */
public class Edge {
    public double z;
    public double yMax;
    /**
     * y加一时，z的增量
     */
    public double k;
    public Edge(double z, int yMax, double k) {
        this.z = z;
        this.yMax = yMax;
        this.k = k;
    }
}

/**
 * 扫描线生成，使用连贯性算法
 *
 * @param part
 */
private void vScanLineConstruct1(Part part) {
    List<Integer> vSLineList = new ArrayList<>();
    // 边表
    HashMap<Integer, List<Edge>> edgeTable = new HashMap<>();
    /*
    边表构造
    遍历每一条边，将边的信息放入到相应的桶中，即放入边的两点中y值较小的那个桶中
     */
    for (int i = 0; i < part.offSetOuterContour.size(); i++) {
        double[] pointI = part.offSetOuterContour.get((i) % part.offSetOuterContour.size());
        double[] pointJ = part.offSetOuterContour.get((i + 1) % part.offSetOuterContour.size());
        // 两个点中较小的y
        int yMin = Math.min((int) Math.round(pointI[0]), (int) Math.round(pointJ[0]));
        int yMax = Math.max((int) Math.round(pointI[0]), (int) Math.round(pointJ[0]));
        if (yMin == yMax) {
            // 对于垂直线，不需要添加到边表中
            continue;
        }
        double z = (int) Math.round(pointI[0]) < (int) Math.round(pointJ[0]) ? pointI[1] : pointJ[1];
        Edge edge = new Edge((int) Math.round(z), yMax, MathUtil.getKOfLine(pointI[0], pointI[1], pointJ[0], pointJ[1]));
        if (!edgeTable.containsKey(yMin)) {
            List<Edge> edgeList = new ArrayList<>();
            edgeList.add(edge);
            edgeTable.put(yMin, edgeList);
        } else {
            edgeTable.get(yMin).add(edge);
        }
    }
    /*
    扫描线构造
     */
    List<Edge> activeEdgeList = new ArrayList<>();
    for (int y = 0; y < part.pixelNumInWidDirection; y++) {
        /// 判断是否有无效边需要移除
        int i = 0;
        while (i < activeEdgeList.size()) {
            Edge edge = activeEdgeList.get(i);
            if (edge.yMax == y) {
                // 当边的yMax==y，该边开始无效，移除边
                activeEdgeList.remove(i);
            } else {
                i++;
            }
        }
        /// 判断是否有新的有效边加入，如果有的话，需要重新排序
        List<Edge> edgeList = edgeTable.get(y);
        if (edgeList != null && edgeList.size() > 0) {
            // 需要将新的边添加到有效边集合中
            activeEdgeList.addAll(edgeList);
            // 因为有新边加入，需要重新排序，首先优先按照z的值来升序排序，对于z相同的，按照k升序排序
            Collections.sort(activeEdgeList, ((o1, o2) -> {
                if (o1.z > o2.z) {
                    return 1;
                } else if (o1.z < o2.z) {
                    return -1;
                } else {
                    if (o1.k > o2.k) {
                        return 1;
                    } else if (o1.k < o2.k) {
                        return -1;
                    } else {
                        return 0;
                    }
                }
            }));
        }
        /// 构造扫描线
        for (int j = 0; j < activeEdgeList.size(); j += 2) {
            vSLineList.add(y);
            vSLineList.add((int)activeEdgeList.get(j).z);
            vSLineList.add((int)Math.ceil(activeEdgeList.get(j + 1).z));
            // 进行增量计算，将z的值增加
            activeEdgeList.get(j).z += activeEdgeList.get(j).k;
            activeEdgeList.get(j + 1).z += activeEdgeList.get(j + 1).k;
        }
    }
    vLineListSort(vSLineList);
    part.vSLineList = vSLineList;
}