Package list
464ff713-9d15-4539-ba6d-39003ae9b060/main

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106``` ```# Implementation of the Bentley-Ottmann algorithm, described in deBerg et al, ch. 2. # See README for more information. # Author: Sam Lichtenberg # Email: splichte@princeton.edu # Date: 09/02/2013 from pauvre.lsi.Q import Q from pauvre.lsi.T import T from pauvre.lsi.helper import * # "close enough" for floating point ev = 0.00000001 # how much lower to get the x of a segment, to determine which of a set of segments is the farthest right/left lower_check = 100 # gets the point on a segment at a lower y value. def getNextPoint(p, seg, y_lower): p1 = seg p2 = seg if (p1-p2)==0: return (p+10, p) slope = float(p1-p2)/(p1-p2) if slope==0: return (p1, p-y_lower) y = p-y_lower x = p1-(p1-y)/slope return (x, y) """ for each event point: U_p = segments that have p as an upper endpoint C_p = segments that contain p L_p = segments that have p as a lower endpoint """ def handle_event_point(p, segs, q, t, intersections): rightmost = (float("-inf"), 0) rightmost_seg = None leftmost = (float("inf"), 0) leftmost_seg = None U_p = segs (C_p, L_p) = t.contain_p(p) merge_all = U_p+C_p+L_p if len(merge_all) > 1: intersections[p] = [] for s in merge_all: intersections[p].append(s) merge_CL = C_p+L_p merge_UC = U_p+C_p for s in merge_CL: # deletes at a point slightly above (to break ties) - where seg is located in tree # above intersection point t.delete(p, s) # put segments into T based on where they are at y-val just below p for s in merge_UC: n = getNextPoint(p, s, lower_check) if n > rightmost: rightmost = n rightmost_seg = s if n < leftmost: leftmost = n leftmost_seg = s t.insert(p, s) # means only L_p -> check newly-neighbored segments if len(merge_UC) == 0: neighbors = (t.get_left_neighbor(p), t.get_right_neighbor(p)) if neighbors and neighbors: find_new_event(neighbors.value, neighbors.value, p, q) # of newly inserted pts, find possible intersections to left and right else: left_neighbor = t.get_left_neighbor(p) if left_neighbor: find_new_event(left_neighbor.value, leftmost_seg, p, q) right_neighbor = t.get_right_neighbor(p) if right_neighbor: find_new_event(right_neighbor.value, rightmost_seg, p, q) def find_new_event(s1, s2, p, q): i = intersect(s1, s2) if i: if compare_by_y(i, p) == 1: if not q.find(i): q.insert(i, []) # segment is in ((x, y), (x, y)) form # first pt in a segment should have higher y-val - this is handled in function def intersection(S): s0 = S if s0 > s0: s0 = (s0, s0) q = Q(s0, [s0]) q.insert(s0, []) intersections = {} for s in S[1:]: if s > s: s = (s, s) q.insert(s, [s]) q.insert(s, []) t = T() while q.key: p, segs = q.get_and_del_min() handle_event_point(p, segs, q, t, intersections) return intersections ```