Átfedő radiális intervallumok, python

EDIT3:

Mint kiderült, az összes lehetséges variáció átgondolása bonyolultabb, mint azt első pillantásra gondoltam. A kódom ezen harmadik iterációjának minden lehetséges bemenetre helyesnek kell lennie. A megnövekedett komplexitás miatt a vektorizált numpy változatot elvetettem. A generátor verziója a következő:

def overlapping_sectors3(sectors, interval):
    """
    Yields overlapping radial intervals.

    Returns the overlapping intervals between each of the sector-intervals
    and the comparison-interval.

    Args:
        sectors: List of intervals. 
            Interval borders must be in [0, 2*pi).
        interval: Single interval aginst which the overlap is calculated.
            Interval borders must be in [0, 2*pi).
    Yields:
        A list of intervals marking the overlaping areas.
            Interval borders are guaranteed to be in [0, 2*pi).
    """
    i_lhs, i_rhs = interval 
    if i_lhs > i_rhs:   
        for s_lhs, s_rhs in sectors:
            if s_lhs > s_rhs:
                # CASE 1
                o_lhs = max(s_lhs, i_lhs)
                # o_rhs = min(s_rhs+2*np.pi, i_rhs+2*np.pi)
                o_rhs = min(s_rhs, i_rhs)
                # since o_rhs > 2pi > o_lhs
                yield o_lhs, o_rhs 

                #o_lhs = max(s_lhs+2pi, i_lhs)
                # o_rhs = min(s_rhs+4pi, i_rhs+2pi)
                # since  o_lhs and o_rhs > 2pi
                o_lhs = s_lhs 
                o_rhs = i_rhs
                if o_lhs < o_rhs:
                    yield o_lhs, o_rhs
            else:
                # CASE 2
                o_lhs = max(s_lhs, i_lhs)
                # o_rhs = min(s_rhs, i_rhs+2*np.pi)
                o_rhs = s_rhs   # since i_rhs + 2pi > 2pi > s_rhs
                if o_lhs < o_rhs:
                    yield o_lhs, o_rhs

                # o_lhs = max(s_lhs+2pi, i_lhs) 
                # o_rhs = min(s_rhs+2pi, i_rhs+2pi)  
                # since s_lhs+2pi > 2pi > i_lhs and both o_lhs and o_rhs > 2pi
                o_lhs = s_lhs   
                o_rhs = min(s_rhs, i_rhs)
                if o_lhs < o_rhs:
                    yield o_lhs, o_rhs
    else:
        for s_lhs, s_rhs in sectors:
            if s_lhs > s_rhs:
                # CASE 3
                o_lhs = max(s_lhs, i_lhs)
                o_rhs = i_rhs
                if o_lhs < o_rhs:
                    yield o_lhs, o_rhs
                o_lhs = i_lhs
                o_rhs = min(s_rhs, i_rhs)
                if o_lhs < o_rhs:
                    yield o_lhs, o_rhs
            else:
                # CASE 4
                o_lhs = max(s_lhs, i_lhs)
                o_rhs = min(s_rhs, i_rhs)
                if o_lhs < o_rhs:
                    yield o_lhs, o_rhs

Ezzel tesztelhető:

import numpy as np
from collections import namedtuple

TestCase = namedtuple('TestCase', ['sectors', 'interval', 'expected', 'remark'])
testcases = []
def newcase(sectors, interval, expected, remark=None):
    testcases.append( TestCase(sectors, interval, expected, remark) )

newcase(
    [[280,70]],
    [270,90],
    [[280,70]],
    "type 1"
)

newcase(
    [[10,150]],
    [270,90],
    [[10,90]],
    "type 2"
)

newcase(
    [[10,150]],
    [270,350],
    [],
    "type 4"
)


newcase(
    [[50,350]],
    [10,90],
    [[50,90]],
    "type 4"
)

newcase(
    [[30,0]],
    [300,60],
    [[30,60],[300,0]],
    "type 1"
)


newcase(
    [[30,5]],
    [300,60],
    [[30,60],[300,5]],
    "type 1"
)

newcase(
    [[30,355]],
    [300,60],
    [[30,60],[300,355]],
    "type 3"
)


def isequal(A,B):
    if len(A) != len(B):
        return False
    A = np.array(A).round()
    B = np.array(B).round()
    a = set(map(tuple, A))
    b = set(map(tuple, B))
    return a == b

for caseindex, case in enumerate(testcases):
    print("### testcase %2d ###" % caseindex)
    print("sectors : %s" % case.sectors)
    print("interval: %s" % case.interval)
    if case.remark:
        print(case.remark)
    sectors = np.array(case.sectors)/180*np.pi
    interval = np.array(case.interval)/180*np.pi
    result = overlapping_sectors3(sectors, interval)
    result = np.array(list(result))*180/np.pi
    if isequal(case.expected, result):
        print('PASS')
    else:
        print('FAIL')
        print('\texp: %s' % case.expected)
        print('\tgot: %s' % result)

A mögöttes logika megértéséhez vegye figyelembe a következőket:

• Minden intervallumnak van egy bal oldala (lhs) és egy jobb oldala (rhs)
• ha lhs > rhs, akkor az intervallum "körbe teker", azaz valójában az [lhs, rhs+2pi] intervallum
• when comparing the current sector aginst the comparison-interval we have to consider four cases
  1. both wrap round
  2. csak az összehasonlítási intervallum kerekít
  3. csak a szektor-intervallum teker
  4. egyik sem tekeredik körbe
• Közönséges intervallumokkal az átfedő intervallum [o_lhs, o_rhs] o_lhs=max(lhs_1, lhs2) és o_rhs=min(rhs_1, rhs_2) iff o_lhs < o_rhs
• Az összes intervallum „elhajlítása” a 2pi hozzáadásával az rhs iff rhs<lhs értékéhez [0, 4*np.pi) intervallumokat eredményez
• [0,2*pi) az első, [2*pi, 4*pi) a második és [4*pi, 6*pi) a harmadik körülírást fogjuk nevezni.

A négy eset:

• 4. eset: egyik intervallum sem teker, tehát minden határ az első körülíráson belül van. Csak az átfedést tudjuk kiszámítani, mint bármely orináris intervallum esetében.
• 2. és 3. eset: pontosan egy intervallum kerekít. Ez azt jelenti, hogy az egyik intervallum (nevezzük a-nak) teljesen az első körülíráson belül van, míg a második (nevezzük b-nek) az első és a második körülírást is létrehozza. Ez azt jelenti, hogy a keresztezheti b-t az első és a második körülírásban is. Először az első körülírást vesszük figyelembe. Tartalmaz a_lhs, a_rhs és b_lhs. A b jobb oldalát "kibontottnak" tekintjük, így a b_rhs+2pi. Ez o_lhs=max(a_lhs, b_lhs) és o_rhs=a_rhs értéket eredményez. Most nézzük a második körüljárást. Nem csak b rhs-ét tartalmazza b_rhs+2pi-ban, hanem a [a_lhs+2pi, a_rhs+2pi]-ben lévő a periodikus ismétlődését is. Ennek eredménye: o_lhs=max(a_lhs+2pi, b_lhs) és o_rhs=min(a_rhs+2pi, b_rhs+2pi). A Modulo 2pi egyaránt lefelé vált o_lhs=a_lhs és o_rhs=min(a_rhs, b_rhs) értékre.
• 1. eset: mindkét intervallum az első és a második körülírást adja. Az első metszéspont [0, 4pi)-on belül van, a második megköveteli az egyik intervallum periodikus ismétlését, és így [2pi,6pi)-en belül van.

RÉGI VÁLASZ, elavult:

Itt az én verzióm, numpy vektoros műveletekkel. Valószínűleg javítható az elvontabb numpy függvény használatával, mint például az np.where és hasonlók.

Egy másik ötlet a numpy figyelmen kívül hagyása és valamilyen iterátor/generátor függvény használata. Talán legközelebb megpróbálok valami hasonlót.

import numpy as np

sectors = np.array( [[5.23,0.50], [0.7,1.8], [1.9,3.71],[4.1,5.11]] )
interval = np.array([5.7,2.15])


def normalize_sectors(sectors):
    # normalize might not be the best word here
    idx = sectors[...,0] > sectors[...,1]
    sectors[idx,1] += 2*np.pi

    return sectors

def overlapping_sectors(sectors, interval):
    # 'reverse' modulo 2*pi, so that rhs is always larger than lhs"
    sectors = normalize_sectors(sectors)
    interval = normalize_sectors(interval.reshape(1,2)).squeeze()

    # when comparing two intervals A and B, the intersection is
    #   [max(A.left, B.left), min(A.right, B.right)
    left = np.maximum(sectors[:,0], interval[0])
    right = np.minimum(sectors[:,1], interval[1])

    # construct overlapping intervals
    res = np.hstack([left,right]).reshape((2,-1)).T

    # neither empty (lhs=rhs) nor 'reversed' lhs>rhs intervals are allowed
    res = res[res[:,0] < res[:,1]]

    #reapply modulo
    res = res % (2*np.pi)

    return res

print(overlapping_sectors(sectors, interval))

SZERKESZTÉS: Itt az iterátor alapú verzió. Ugyanolyan jól működik, de úgy tűnik, hogy némileg gyengébb.

def overlapping_sectors2(sectors, interval):
    i_lhs, i_rhs = interval 
    if i_lhs>i_rhs:
        i_rhs += 2*np.pi

    for s_lhs, s_rhs in sectors:
        if s_lhs>s_rhs:
            s_rhs += 2*np.pi

        o_lhs = max(s_lhs, i_lhs)
        o_rhs = min(s_rhs, i_rhs)
        if o_lhs < o_rhs:
            yield o_lhs % (2*np.pi), o_rhs % (2*np.pi)

print(list(overlapping_sectors2(sectors, interval)))

2. SZERKESZTÉS: Most már támogatja az olyan intervallumokat, amelyek két helyen átfedik egymást.

    sectors = np.array( [[30,330]] )/180*np.pi
    interval = np.array( [300,60] )/180*np.pi



def normalize_sectors(sectors):
    # normalize might not be the best word here
    idx = sectors[...,0] > sectors[...,1]
    sectors[idx,1] += 2*np.pi

    return sectors

def overlapping_sectors(sectors, interval):
    # 'reverse' modulo 2*pi, so that rhs is always larger than lhs"
    sectors = normalize_sectors(sectors)

    # if interval rhs is smaller than lhs, the interval crosses 360 degrees
    #   and we have to consider it as two intervals
    if interval[0] > interval[1]:
        interval_1 = np.array([interval[0], 2*np.pi])
        interval_2 = np.array([0, interval[1]])
        res_1 = _overlapping_sectors(sectors, interval_1)
        res_2 = _overlapping_sectors(sectors, interval_2)
        res = np.vstack((res_1, res_2))
    else:
        res = _overlapping_sectors(sectors, interval)

    #reapply modulo
    res = res % (2*np.pi)

    return res

def _overlapping_sectors(sector, interval):       
    # when comparing two intervals A and B, the intersection is
    #   [max(A.left, B.left), min(A.right, B.right)
    left = np.maximum(sectors[:,0], interval[0])
    right = np.minimum(sectors[:,1], interval[1])

    # construct overlapping intervals
    res = np.hstack([left,right]).reshape((2,-1)).T

    # neither empty (lhs=rhs) nor 'reversed' lhs>rhs intervals are allowed
    res = res[res[:,0] < res[:,1]]
    return res

print(overlapping_sectors(sectors, interval)*180/np.pi)


def overlapping_sectors2(sectors, interval):
    i_lhs, i_rhs = interval 

    for s_lhs, s_rhs in sectors:
        if s_lhs>s_rhs:
            s_rhs += 2*np.pi

        if i_lhs > i_rhs:
            o_lhs = max(s_lhs, i_lhs)
            o_rhs = min(s_rhs, 2*np.pi)
            if o_lhs < o_rhs:
                yield o_lhs % (2*np.pi), o_rhs % (2*np.pi)
            o_lhs = max(s_lhs, 0)
            o_rhs = min(s_rhs, i_rhs)
            if o_lhs < o_rhs:
                yield o_lhs % (2*np.pi), o_rhs % (2*np.pi)
        else:
            o_lhs = max(s_lhs, i_lhs)
            o_rhs = min(s_rhs, i_rhs)
            if o_lhs < o_rhs:
                yield o_lhs % (2*np.pi), o_rhs % (2*np.pi)                

print(np.array(list(overlapping_sectors2(sectors, interval)))*180/np.pi)