同时聚集重叠范围(矩形问题)

数字表:

要像我在文章中指出的那样以几何方式解决问题,您必须使用sqlserver几何数据类型。不幸的是,要获取几何体值内的每个单独的形状或点,必须按索引调用形状。数字表有助于解决这一问题。所以我先这么做(换成你喜欢的实现)。

create table #numbers (i int);

declare @i int = 1;
while @i <= 100 begin
    insert #numbers values (@i);
    set @i += 1;
end;

第一个必需的任务是将数字范围转换为几何矩形。 Point 创建角点。 STUnion STEnvelope 把这些变成 矩形。此外,由于我们希望在整数相邻时将范围合并在一起,所以在几何转换之前,我们在“到”字段中添加1。

UnionAggregate . 结果是一个直线多边形(长方形)的几何体对象。

几何体对象仍然可以有多个矩形多边形。因此,这些将作为单独的形状列出并输出到 rectilinears

with

    aggregateRectangles as (

        select      student, 
                    rectilinears = geometry::UnionAggregate(rectangle)
        from        @schedule s
        cross apply (select 
                        minPt = geometry::Point(s.fromDate, s.fromPeriod, 0),
                        maxPt = geometry::Point(s.toDate + 1, s.toPeriod + 1, 0)
                    ) extremePoints
        cross apply (select rectangle = minPt.STUnion(maxPt).STEnvelope()) enveloped
        group by    student 

    )

    select      ar.student, 
                r.rectilinear,
                mm.minY,
                mm.maxY
    into        #rectilinears
    from        aggregateRectangles ar
    join        #numbers n on n.i between 1 and ar.rectilinears.STNumGeometries()
    cross apply (select rectilinear = ar.rectilinears.STGeometryN(n.i)) r
    cross apply (select envelope = r.rectilinear.STEnvelope()) e
    cross apply (select 
                    minY = e.envelope.STPointN(1).STY, 
                    maxY = e.envelope.STPointN(3).STY 
                ) mm;

侧注-性能选项:

ToString()

接下来,这些直线必须分解回矩形。拆分器是通过在每个点的x坐标处创建垂直线来创建的。y轴可以很容易地被选择,我只是选择了x作为我自己的语义。这两个轴也可以选择,但这将导致更多的记录不必要。

不幸的是,如果拆分器的宽度为零(理论上是这样设置的,这是不合适的,但是我想您不能用WKT格式正确地表示结果),那么sqlserver不会拆分形状。所以我们需要给拆分器一个缓冲区,这样它们就有了一个区域。有 STBuffer ,虽然我遇到了麻烦,所以我只是手动创建了一个。

with

    createSplitters as (

        select      r.student,
                    rectilinear = geometry::STGeomFromText(r.rectilinear.ToString(), 0),
                    splitters = geometry::UnionAggregate(sp.splitter)
        from        #rectilinears r
        join        #numbers n on n.i between 1 and r.rectilinear.STNumPoints()
        cross apply (select 
                        x = r.rectilinear.STPointN(n.i).STX,
                        buffer = 0.001
                    ) px
        cross apply (select splitter =
                        geometry::Point(x - buffer, minY - buffer, 0).STUnion(
                            geometry::Point(x + buffer, maxY + buffer, 0)
                        ).STEnvelope()
                    ) sp
        group by    r.student,
                    r.rectilinear.ToString()

    )

    select      student,
                rectangle = rectangles.STGeometryN(n.i)
    into        #rectangles
    from        createSplitters sp
    cross apply (select 
                    rectangles = rectilinear.STDifference(sp.splitters)
                ) r
    join        #numbers n on n.i between 1 and r.rectangles.STNumGeometries();

分析范围:

这就是问题的症结所在。剩下的只是从矩形中提取适当的值来给出范围。

为此,我们首先调用 狭窄 以确保矩形仅由其角点表示。然后我们绕过拐角点来消除缓冲区的影响,以及浮点表示的任何问题。我们还从“到”字段中减去1以撤消在转换为几何点之前所做的操作。

select      student,
            fromDate = round(minPt.STX,0),
            toDate = round(maxPt.STX,0) - 1,
            fromPeriod = round(minPt.STY,0),
            toPeriod = round(maxPt.STY,0) - 1
into        #normalized
from        #rectangles r
cross apply (select 
                minPt = r.rectangle.STPointN(1), 
                maxPt = r.rectangle.STPointN(3)
            ) corners
order by    student, fromDate, fromPeriod;

可选-前后可视化:

select      student,
            unnormalized = 
                geometry::Point(fromDate, fromPeriod, 0).STUnion(
                    geometry::Point(toDate, toPeriod, 0)
                ).STEnvelope(),
            normalized = null
from        @schedule s

union all
select      student,
            unnormalized = null,
            normalized = 
                geometry::Point(fromDate, fromPeriod, 0).STUnion(
                    geometry::Point(toDate, toPeriod, 0)
                ).STEnvelope()
from        #normalized;

with 

    a as (    

        select student, fromdate from @schedule union
        select student, todate+1 from @schedule    

    ),

    b as (

        select   *, 
                 todate = (
                     select   min(aa.fromdate) 
                     from a as aa 
                     where aa.student = a.student 
                     and aa.fromdate > a.fromdate
                 ) - 1 
        from     a
    )

    select    *
    from      b
    where     exists (
                  select   * 
                  from     @schedule as s 
                  where    s.student = b.student 
                  and      s.fromdate < b.todate 
                  and      s.todate > b.fromdate
              );