Boolean operations on segments of a same line

user_18177837 0
Viewed 53

I have been looking for some guidance on a geometry problem I have 2 segments that lie on the same line and I want to clip both based on any of the boolean operations

Union, Intersection, Difference, Difference-Rev, Xor

The expected result should be a list of segments because cases can return 0,1 or 2 segments

in my current approach, I define a segment as a pair of 2 numbers (coordinates) on the same line

Segment 1 : (2,13)
Segment 2: (8,16)

my first step is make an array of sorted points

points = [2, 8, 13, 16]

second is iterate and label the points by their owner

Segment 1, Segment 2 or Both

Finally, I need to do a selection given a boolean operation and the labels

But currently I'm stuck on the second step and I don't know how to find the labels and then do the selection given the boolean operation, any help ?

Example Outputs Image

boolean-operations geometry
1 Answers

Put triplets [coordinate, begin/end, segment number] in the list.

Sort the list.

Walk through the list. At every point change a code adding or subtracting segment number. So code=3 denotes segement intersection, code=1 corresponds to the first segment only range.

Form resulting ranges depending on operation required and code change. Here I just enumerated operations in your list order.

I'm not sure what to do when end of one segment coinsides with beginning of another. Current sorting puts end before begin, so union will give two separate ranges. If needed, change sign of begin/end field and make code -= p[1] * p[2]

Python code:

def boolops(s1, s2, op):
    pts = [[s1[0], 1, 1], [s1[1], -1, 1],[s2[0], 1, 2],[s2[1], -1, 2]]
    pts.sort()
    #print(pts)
    res = []
    code = 0
    oldcode = 0
    start = -1
    for p in pts:
        code += p[1] * p[2]
        #print(oldcode, code)
        if op == 0:  # union
            if oldcode == 0 and code:
                start = p[0]
            elif oldcode and code == 0:
                res.append([start, p[0]])
        elif op == 1: #intersection
            if code == 3:
                start = p[0]
            elif oldcode == 3:
                res.append([start, p[0]])
        elif op == 2: #diff s1-s2
            if code == 1:
                start = p[0]
            elif oldcode == 1:
                res.append([start, p[0]])
        elif op == 3: #rev diff s2-s1
            if code == 2:
                start = p[0]
            elif oldcode == 2:
                res.append([start, p[0]])
        elif op == 4: #xor
            if code % 3 > 0:
                start = p[0]
            else:
                res.append([start, p[0]])
        oldcode = code
    return res


print(boolops([2,10],[5,12], 0)) 
print(boolops([2,5],[10,12], 0))

print(boolops([2,10],[5,12], 1)) 
print(boolops([2,5],[10,12], 1))

print(boolops([2,10],[5,12], 2))
print(boolops([2,5],[10,12], 2))

print(boolops([2,10],[5,12], 3))
print(boolops([2,5],[10,12], 3))

print(boolops([2,10],[5,12], 4))
print(boolops([2,5],[10,12], 4))

[2, 12]]   #union
[[2, 5], [10, 12]]
[[5, 10]]  #intersection
[]
[[2, 5]]  #diff
[[2, 5]]   
[[10, 12]] #revdiff
[[10, 12]]
[[2, 5], [10, 12]]  #xor
[[2, 5], [10, 12]]

#full coverage tests
print(boolops([2,5],[1,6], 0))
print(boolops([2,5],[1,6], 1))
print(boolops([2,5],[1,6], 2))
print(boolops([2,5],[1,6], 3))
print(boolops([2,5],[1,6], 4)

[[1, 6]]
[[2, 5]]
[]
[[1, 2], [5, 6]]
[[1, 2], [5, 6]]

)

user_8444160
Related