Codebase list
debian/0.2.2-2

 ``` 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``` ```# Helper functions for use in the lsi implementation. ev = 0.0000001 # floating-point comparison def approx_equal(a, b, tol): return abs(a - b) < tol # compares x-values of two pts # used for ordering in T def compare_by_x(k1, k2): if approx_equal(k1, k2, ev): return 0 elif k1 < k2: return -1 else: return 1 # higher y value is "less"; if y value equal, lower x value is "less" # used for ordering in Q def compare_by_y(k1, k2): if approx_equal(k1, k2, ev): if approx_equal(k1, k2, ev): return 0 elif k1 < k2: return -1 else: return 1 elif k1 > k2: return -1 else: return 1 # tests if s0 and s1 represent the same segment (i.e. pts can be in 2 different orders) def segs_equal(s0, s1): x00 = s0 y00 = s0 x01 = s0 y01 = s0 x10 = s1 y10 = s1 x11 = s1 y11 = s1 if (approx_equal(x00, x10, ev) and approx_equal(y00, y10, ev)): if (approx_equal(x01, x11, ev) and approx_equal(y01, y11, ev)): return True if (approx_equal(x00, x11, ev) and approx_equal(y00, y11, ev)): if (approx_equal(x01, x10, ev) and approx_equal(y01, y10, ev)): return True return False # get m for a given seg in (p1, p2) form def get_slope(s): x0 = s y0 = s x1 = s y1 = s if (x1-x0)==0: return None else: return float(y1-y0)/(x1-x0) # given a point p, return the point on s that shares p's y-val def get_x_at(s, p): m = get_slope(s) # TODO: this should check if p's x-val is octually on seg; we're assuming # for now that it would have been deleted already if not if m == 0: # horizontal segment return p # ditto; should check if y-val on seg if m is None: # vertical segment return (s, p) x1 = s-(s-p)/m return (x1, p) # returns the point at which two line segments intersect, or None if no intersection. def intersect(seg1, seg2): p = seg1 r = (seg1-seg1, seg1-seg1) q = seg2 s = (seg2-seg2, seg2-seg2) denom = r*s-r*s if denom == 0: return None numer = float(q-p)*s-(q-p)*s t = numer/denom numer = float(q-p)*r-(q-p)*r u = numer/denom if (t < 0 or t > 1) or (u < 0 or u > 1): return None x = p+t*r y = p+t*r return (x, y) ```