一尘不染

如果两个线段重叠或相交,则将它们合并在同一圆上

algorithm

我试着两个部分结合起来,如果他们重叠或intersect.My的问题是类似这样和这个。但是,我要结合两个部分。

public class Segment
{
    private readonly double _from;
    private readonly double _to;
    public Segment(double from, double to)
    {
        _from = Normalize(from); // 0 <= x < 360
        _to = Normalize(to);
    }

    public bool Inside(double target)
    {
        if (_from < _to)
            return _from <= target && target <= _to;
        return _from <= target || target <= _to;
    }
}

我正在尝试写一篇TryCombine()

public bool TryCombine(Segment other, out Segment result)
{
    // if not intersect
    // return false

    // else if overlap
    // return true, out larger one

    // else if intersect
    // return true, out a new one with merged bound
}

预期结果

var seg1 = new Segment(0, 100);
var seg2 = new Segment(50, 150);
var seg3 = new Segment(110, -100);
var seg4 = new Segment(10, 50);
Segment result;

seg1.TryCombine(seg2, result); // True, result = Segment(0, 150)
seg1.TryCombine(seg3, result); // False
seg1.TryCombine(seg4, result); // True, result = Segment(0, 100)
seg2.TryCombine(seg3, result); // True, result = Segment(260, 150)

阅读 215

收藏
2020-07-28

共1个答案

一尘不染

您可以在第二个链接中使用我的回答中所述的方法。

ma = (a2 + a1)/ 2  
mb = (b2 + b1)/ 2  
cda = Cos(da)
cdb = Cos(db)

要检查交叉点是否存在以及发生哪种类型的交叉点,请找到4个布尔值

 BStartInsideA = (Cos(ma - b1) >= cda)
 BEndInsideA  =  (Cos(ma - b2) >= cda)
 AStartInsideB = (Cos(mb - a1) >= cdb)
 AEndInsideB =   (Cos(mb - a2) >= cdb)

这些组合可能形成16种可能的结果(并非所有结果都是可靠的)。我将这些结果组合为4位值的位,并在case语句中对其进行处理。

例如,如果第一个值和最后一个值均为true(value0b1001=9),则您具有类似于seg1-seg2的情况的简单交集-因此,请获取AStartans起点,BEnd作为终点并将其标准化(如果较小则将360添加到BEnd比AStart)。

预规范化步骤应提供BEnd> =BStart和AEnd>=AStart(例如,将(3,1)弧转换为具有中点182和半角179的(3,361)

可能的结果(两种额外的情况,4种简单的末端组合,4种单末端重合的情况):

 0000: no intersection
 1111: full circle

 0011: AStart-AEnd
 1001: AStart-BEnd
 0110: BStart-AEnd
 1100: BStart-BEnd

 0111: AStart-AEnd
 1011: AStart-AEnd
 1110: BStart-BEnd
 1101: BStart-BEnd

一位组合和1010,0101看起来不可能

如作者建议的那样,使用通配符:

 At first check for 
   0000: no intersection
   1111: full circle
 then
   **11: AStart-AEnd
   1001: AStart-BEnd
   0110: BStart-AEnd
   11**: BStart-BEnd
2020-07-28