Java线段集合分类方案：识别自由段、双曲线、多边形（禁用java.awt）

问题背景 #

项目运行过程中会持续绘制线段，自定义Segment类通过两个PointOnTheArea类型对象表示平面上线段的两个端点，核心类定义如下：

public  class PointOnTheArea implements Point {

    private final double pointX;
    private final double pointY;


    public PointOnTheArea(double x, double y){
        this.pointY = y;
        this.pointX = x;
    }
    public double getX(){
        return pointX;
    }
    public double getY(){
        return pointY;
    }
}


public class Segment {

private PointOnTheArea startingPoint;
private PointOnTheArea endingPoint;
private final SegmentType segmentType; // 标记线段为直线/曲线
private final int radius; // 仅曲线段使用的半径参数
private final Direction dir; // 线段绘制方向，仅平面场景使用
private boolean isTaken = false; // 标记线段是否已归属某一多边形
private final int size; // 线段两端点距离
private final Color myColor; // 线段颜色



public Segment(int x1, int y1, int x2, int y2, SegmentType type, Direction dir, int radius, Color myColor){
    this.segmentType = type;
    this.radius = radius;
    this.dir = dir;
    setSegment(x1, y1, x2, y2);
    this.myColor = myColor;
    this.size = (int) Math.sqrt(Math.pow(x2-x1,2)+Math.pow(y2-y1,2));
}

需要设计线段存储与分类逻辑，将所有线段划分为三类：

• 双曲线段序列：由存在公共连接点的线段依次连接构成，连接规则为某条线段的起点与另一条线段的终点重合
• 多边形：由线段构成的闭合环路，环路中每条线段的终点与下一条线段的起点重合，环路内不存在两个终点共点或两个起点共点的情况；需注意多边形可能从线段列表的第4个元素起始延伸至列表末尾构成，此时前3条线段需单独归类为双曲线段序列
• 自由线段：未与任何其他线段存在连接点的独立线段

初始方案使用LinkedList作为存储结构，无法覆盖所有边界场景，且项目明确禁止使用java.awt包，以下是可落地的实现思路。

具体实现方案 #

1. 前置处理：解决浮点坐标匹配问题 #

由于坐标使用double类型存储，直接用==判断点重合会存在精度误差，首先定义统一的坐标判定阈值，封装匹配工具方法：

// 浮点坐标匹配误差阈值，可根据业务精度调整
private static final double EPS = 1e-6;
private boolean pointMatch(PointOnTheArea p1, PointOnTheArea p2) {
    return Math.abs(p1.getX() - p2.getX()) < EPS && Math.abs(p1.getY() - p2.getY()) < EPS;
}

不要直接重写equals和hashCode用原始double值做哈希，浮点精度问题会导致逻辑一致的点无法匹配

2. 替换存储结构：构建双哈希索引 #

放弃单链表顺序遍历匹配的方案，构建两个哈希索引实现O(1)复杂度的连接关系查询，完全不依赖java.awt包的类：

• Map<PointWrapper, List<Segment>> endPointMap：key为自定义封装的点对象，value为以该点为终点的所有线段列表
• Map<PointWrapper, List<Segment>> startPointMap：key为自定义封装的点对象，value为以该点为起点的所有线段列表

其中PointWrapper为自定义包装类，重写equals时按照上述EPS阈值做坐标匹配，重写hashCode时将坐标按EPS精度取整后生成哈希值，避免浮点误差导致的索引失效。

3. 分类执行流程 #

1. 初始化：遍历所有线段，将isTaken统一置为false，填充上述两个哈希索引
2. 优先识别多边形：
   • 按线段原始绘制顺序做滑动校验，从索引i=0开始，检查i位置出发的线段是否能沿着「当前线段终点 -> 匹配下一条线段起点」的规则串联
   • 串联过程中做两项校验：每一步匹配到的下一条线段有且仅有1条（符合无多起点/多终点共点的要求）、串联过程中能回到起始线段的起点形成闭合
   • 若满足闭合条件且串联线段数≥3，将这组线段标记为多边形，组内所有线段置isTaken=true
   • 针对「多边形从列表第4个元素起始」的场景：如果i=0、1、2位置出发均无法形成闭合环路，i=3位置首次匹配到闭合多边形，则前0-2位线段直接划入双曲线段序列
3. 识别双曲线段序列：
   • 遍历所有未被标记的线段，沿着「终点匹配起点」的规则向两端延伸串联，只要存在可连接的未标记线段就持续扩展，直到两端都没有可匹配的线段
   • 串联得到的长度≥2的线段组即为双曲线段序列，组内所有线段置isTaken=true
4. 识别自由线段：所有遍历完成后仍为isTaken=false的线段，即为无任何连接关系的独立自由线段

4. 边界场景兼容 #

• 若某一个点同时匹配到2条及以上可连接线段，直接判定该点为序列端点，不做跨分支串联，避免错误合并不同绘制序列
• 如果业务中存在绘制方向反向但实际连接的线段，可以额外增加反向匹配逻辑：即当前线段起点匹配另一线段终点、终点匹配另一线段起点时，先做线段方向反转再加入对应序列
• 所有坐标匹配逻辑统一走封装的pointMatch方法，禁止直接比较double原始值

该方案整体时间复杂度为O(n)，相比LinkedList每次顺序遍历匹配的O(n²)效率更高，通过索引预构建的方式可以覆盖所有连接场景，不会出现顺序遍历漏匹配的问题。

内容的提问来源于stack exchange，提问作者Marsh