Bentley-Ottmann算法中Segment类的IComparable实现

Question

我正在尝试使用C#实现Bentley-Ottmann算法，该算法在此处有描述。 特别地，在扫描线状态结构中为Segment类实现IComparable<T>时遇到了问题。下面是段类的列表：

public class SweepLineSegment : IComparable<SweepLineSegment>
{
    public int Edge { get; set; }
    public PointF LeftmostVertexPoint { get; set; }
    public PointF RightmostVertexPoint { get; set; } 
    public SweepLineSegment Above { get; set; }
    public SweepLineSegment Below { get; set;} 

    public int CompareTo(SweepLineSegment other)
    {
        ?????
    }
}

我不太清楚在将两个线段添加到扫描线状态结构中时应该如何进行比较。

注：扫描线算法是计算机科学中的一种算法，可以用于解决许多几何问题。

- GEO

---

你能否将问题与 Bentley-Ottmann 算法分离开来？这样做会使更多的人受益。 - Ryan Gates

根据 Bentley-Ottmann 算法，与扫描线相交的线段被保留在结构中，通常是平衡二叉搜索树（AVL 树、RB 树等）。我尝试为 Segment 类实现简单的通用 BST，但我需要知道正确的比较 Segment 类的方法，以便正确地实现它。这种方式与算法密切相关，对我来说并不清楚。 - GEO

那么你的问题简单地说就是：“如何比较两个自定义对象（在这种情况下为Segment）？” - Ryan Gates

Answer 1

你为什么要比较线段呢？四个坐标元组没有任何总序。

如果你想要沿着多边形周长出现的边的顺序，你应该只需跟踪段索引。我猜这就是Edge属性？尝试return Edge.CompareTo(other.Edge)。

但我建议根本不要实现IComparable。你需要它做什么？

- Ben Voigt