#!/usr/bin/python '''Unit tests for lsa module''' from __future__ import division from __future__ import print_function import sys import math import pprint #mport signal import functools import subprocess import lsa_mod def equality_test(): '''Test comparing two vectors''' vec1 = lsa_mod.Vector(1, 2) vec2 = lsa_mod.Vector(1, 2) if vec1 == vec2: return True else: sys.stderr.write('{0}: Vector equality failed\n'.format(sys.argv[0], )) return False def inequality_test(): '''Test comparing two vectors''' vec1 = lsa_mod.Vector(1, 2) vec2 = lsa_mod.Vector(1, 2.1) if vec1 != vec2: return True else: sys.stderr.write('{0}: Vector inequality failed\n'.format(sys.argv[0], )) return False def add_test(): '''Test adding two vectors''' vec1 = lsa_mod.Vector(1, 2) vec2 = lsa_mod.Vector(3, 4) vec_sum = vec1 + vec2 if vec_sum.x_coord == 4 and vec_sum.y_coord == 6: return True else: sys.stderr.write('{0}: Vector sum failed\n'.format(sys.argv[0], )) return False def subtract_test(): '''Test subtracting two vectors''' vec1 = lsa_mod.Vector(1, 2) vec2 = lsa_mod.Vector(3, 4) vec_sum = vec1 - vec2 if vec_sum.x_coord == -2 and vec_sum.y_coord == -2: return True else: sys.stderr.write('{0}: Vector subtraction failed\n'.format(sys.argv[0], )) return False def dot_product_test(): '''Test the two forms of dot product''' all_good = True vec1 = lsa_mod.Vector(1, 2) vec2 = lsa_mod.Vector(3, 4) vec_dot_prod = vec1.dot_product(vec2) expected_result = 1*3 + 2*4 if vec_dot_prod != expected_result: sys.stderr.write('{0}: vec1.dot_product(vec2) dot product failed, expected {1}, got {2}\n'.format( sys.argv[0], expected_result, vec_dot_prod)) all_good = False vec_dot_prod = vec1 * vec2 if vec_dot_prod != expected_result: sys.stderr.write('{0}: vec1 * vec2 dot product failed, expected {1}, got {2}\n'.format( sys.argv[0], expected_result , vec_dot_prod)) all_good = False return all_good def cross_product_test(): '''Test the two forms of cross product''' all_good = True vec1 = lsa_mod.Vector(1, 2) vec2 = lsa_mod.Vector(3, 4) vec_cross_prod = vec1.cross_product(vec2) expected_result = 1*4 - 3*2 if vec_cross_prod != expected_result: sys.stderr.write('{0}: vec1.cross_product(vec2) failed, expected {1}, got {2}\n'.format( sys.argv[0], expected_result, vec_cross_prod)) all_good = False vec_cross_prod = vec1 ^ vec2 expected_result = 1*4 - 3*2 if vec_cross_prod != expected_result: sys.stderr.write('{0}: vec1 ^ vec2 failed, expected {1}, got {2}\n'.format( sys.argv[0], expected_result, vec_cross_prod)) all_good = False return all_good def magnitude_test(): '''Test computing a vector's magnitude''' all_good = True vec = lsa_mod.Vector(1, 2) magnitude = vec.magnitude() expected_result = math.sqrt(1 + 4) if magnitude != expected_result: sys.stderr.write('{0}: vec.magnitude() failed, expected {1}, got {2}\n'.format( sys.argv[0], expected_result, magnitude)) all_good = False magnitude = abs(vec) if magnitude != expected_result: sys.stderr.write('{0}: abs(vec) failed, expected {1}, got {2}\n'.format( sys.argv[0], expected_result, magnitude)) all_good = False return all_good def pythagorean_distance_test(): '''Test computing the distance between two vectors''' vec1 = lsa_mod.Vector(0, 1) vec2 = lsa_mod.Vector(1, 1) vec_distance = vec1.distance(vec2) expected_result = 1.0 if abs(vec_distance - expected_result) < lsa_mod.EPSILON: return True else: sys.stderr.write('{0}: pythagorean_distance_test, expected {1}, got {2}\n'.format( sys.argv[0], expected_result, vec_distance)) return False def manhattan_distance_test(): '''Test computing the distance between two vectors''' vec1 = lsa_mod.Vector(1, 1) vec2 = lsa_mod.Vector(2, 2) vec_distance = vec1.manhattan_distance(vec2) expected_result = 2.0 if abs(vec_distance - expected_result) < lsa_mod.EPSILON: return True else: sys.stderr.write('{0}: manhattan_distance_test, expected {1}, got {2}\n'.format( sys.argv[0], expected_result, vec_distance)) return False def line_point_distance_test(): '''Test computing the distance from a line to a point''' line = lsa_mod.Line( lsa_mod.Vector(0, 0), lsa_mod.Vector(1, 0), is_segment=False) point = lsa_mod.Vector(0, 1) line_point_distance = line.point_distance(point) if abs(line_point_distance - 1.0) < lsa_mod.EPSILON: return True else: sys.stderr.write('{0}: distance from line {1} to point {2} was not 1.0, got: {3}\n'.format( sys.argv[0], line, point, line_point_distance)) return False def square_area_test(): '''Test computing the area of a simple polygon''' polygon = lsa_mod.Polygon( lsa_mod.Vector(0, 0), lsa_mod.Vector(0, 1), lsa_mod.Vector(1, 1), lsa_mod.Vector(1, 0), lsa_mod.Vector(0, 0)) area = polygon.area() if abs(area - 1.0) < lsa_mod.EPSILON: return True else: sys.stderr.write('{0}: area of unit square was not 1.0, got {1} instead\n'.format( sys.argv[0], area)) return False def triangle_area_test(): '''Test computing the area of a simple polygon''' polygon = lsa_mod.Polygon( lsa_mod.Vector(0, 0), lsa_mod.Vector(0, 1), lsa_mod.Vector(1, 0), lsa_mod.Vector(0, 0)) area = polygon.area() if abs(area - 0.5) < lsa_mod.EPSILON: return True else: sys.stderr.write('{0}: area of triangle was not 0.5, got {1} instead\n'.format( sys.argv[0], area)) return False def line_intersection_test(): '''Test two intersecting lines''' line1 = lsa_mod.Line(lsa_mod.Vector(0.0, 0.0), lsa_mod.Vector(1.0, 1.0), is_segment=False) line2 = lsa_mod.Line(lsa_mod.Vector(0.0, 1.0), lsa_mod.Vector(1.0, 0.0), is_segment=False) try: point = line1.intersection(line2) except lsa_mod.ParallelException: sys.stderr.write('{0}: lines thought parallel\n'.format(sys.argv[0])) return False if point.x_coord == 0.5 and point.y_coord == 0.5: return True else: sys.stderr.write('{0}: point of intersection was not 0.5, 0.5, got {1} instead\n'.format( sys.argv[0], point)) return False def line_segment_intersection_test(): '''Test two intersecting line segments''' line1 = lsa_mod.Line(lsa_mod.Vector(0.0, 0.0), lsa_mod.Vector(1.0, 1.0), is_segment=True) line2 = lsa_mod.Line(lsa_mod.Vector(0.0, 1.0), lsa_mod.Vector(1.0, 0.0), is_segment=True) try: point = line1.intersection(line2) except lsa_mod.ParallelException: sys.stderr.write('{0}: lines thought parallel\n'.format(sys.argv[0])) return False if point.x_coord == 0.5 and point.y_coord == 0.5: return True else: sys.stderr.write('{0}: point of intersection was not 0.5, 0.5, got {1} instead\n'.format(sys.argv[0], point)) return False def line_seg_nonintersection_test(): '''Test two nonintersecting line segments''' line1 = lsa_mod.Line(lsa_mod.Vector(0.0, 0.0), lsa_mod.Vector(1.0, 1.0), is_segment=True) line2 = lsa_mod.Line(lsa_mod.Vector(1.0, 2.0), lsa_mod.Vector(2.0, 1.0), is_segment=True) try: dummy = line1.intersection(line2) except lsa_mod.DoNotIntersect: return True else: sys.stderr.write('{0}: point of intersection found despite nonintersecting\n'.format(sys.argv[0])) return False def line_parallel_test(): '''Test two parallel lines''' line1 = lsa_mod.Line(lsa_mod.Vector(0, 0), lsa_mod.Vector(1, 1), is_segment=False) line2 = lsa_mod.Line(lsa_mod.Vector(2, 2), lsa_mod.Vector(3, 3), is_segment=False) try: dummy = line1.intersection(line2) except lsa_mod.ParallelException: return True else: sys.stderr.write('{0}: lines were not found parallel\n'.format(sys.argv[0])) return False def generic_intersections(text, expected_points, which): '''Compare some text to the expected result''' lines = lsa_mod.text_lines_to_line_segments(text) lsa_result = lsa_mod.naive_intersections(lines) actual_points = list(lsa_result.intersections.keys()) actual_points.sort(key=lsa_mod.points_key) expected_points.sort(key=lsa_mod.points_key) if actual_points == expected_points: return True else: sys.stderr.write('{}: {}: Expected {}, got {}\n'.format(sys.argv[0], which, expected_points, actual_points)) return False def naive_intersections_1(): '''Find intersections in 4 line segments''' text = ''' 0 0 3 3 1 0 0 1 1 2 2 1 5 6 6 5 ''' # FIXME: The abutting lines should also come up as intersections, but don't yet! expected_points = [ lsa_mod.Vector(0.5, 0.5), lsa_mod.Vector(1.5, 1.5) ] return generic_intersections(text, expected_points, 'naive_intersections_1') def naive_intersections_2(): '''Find intersections in 2 diagonally abutting line segments''' all_good = True line1 = lsa_mod.Line(lsa_mod.Vector(0.0, 0.0), lsa_mod.Vector(1.0, 1.0), is_segment=True) line2 = lsa_mod.Line(lsa_mod.Vector(1.0, 1.0), lsa_mod.Vector(2.0, 2.0), is_segment=True) lsa_result = lsa_mod.naive_intersections([line1, line2]) if len(lsa_result.intersections) != 1: sys.stderr.write('{}: naive_intersections_2: intersection not detected as single point\n'.format(sys.argv[0])) sys.stderr.write('lsa_result.intersections: {}\n'.format(pprint.pformat(lsa_result.intersections))) all_good = False if len(lsa_result.overlaps) != 0: sys.stderr.write('{}: naive_intersections_2: points misdetected?\n'.format(sys.argv[0])) all_good = False return all_good def naive_intersections_3(): '''Find intersections in 2 right-angle abutting line segments''' text = ''' 0 0 0 1 0 1 1 1 ''' expected_points = [ lsa_mod.Vector(0.0, 1.0) ] return generic_intersections(text, expected_points, 'naive_intersections_3') def naive_intersections_4(): ''' Find intersections in 2 non-intersecting line segments. As infinite lines, they intersect, but as line segments they do not ''' text = ''' 0 0 0 1 10 10 11 11 ''' text2 = ''' 10 10 11 11 0 0 0 1 ''' result1 = generic_intersections(text, [], 'naive_intersections_4') result2 = generic_intersections(text2, [], 'naive_intersections_4') return result1 and result2 def naive_intersections_more_dc(): '''Find the intersections in more of the Washington D.C. data''' all_good = True process = subprocess.Popen(['./TIGER/extract-line-segments', './TIGER/DC/tl_2010_11001_roads' ], stdout=subprocess.PIPE) file_ = process.stdout text_lines = file_.readlines() file_.close() retval = process.returncode assert retval in [ None, 0 ] text_lines = text_lines[:2000] lines = [] for text_line in text_lines: fields = text_line.split() if len(fields) != 4: print('skipping line {}'.format(text_line)) continue value0 = float(fields[0]) value1 = float(fields[1]) value2 = float(fields[2]) value3 = float(fields[3]) line = lsa_mod.Line(lsa_mod.Vector(value0, value1), lsa_mod.Vector(value2, value3), is_segment=True) lines.append(line) lsa_result = lsa_mod.naive_intersections(lines) if len(lsa_result.intersections) != 234: print('{}: len(lsa_result.intersections): {}'.format(sys.argv[0], len(lsa_result.intersections))) all_good = False if len(lsa_result.overlaps) != 1: print('{}: len(lsa_result.overlaps): {}'.format(sys.argv[0], len(lsa_result.overlaps))) all_good = False return all_good def naive_intersections_partial_dc(): '''Find the intersections in the beginning of the Washington D.C. data''' process = subprocess.Popen(['./TIGER/extract-line-segments', './TIGER/DC/tl_2010_11001_roads' ], stdout=subprocess.PIPE) file_ = process.stdout # We read the whole thing to avoid ugly sigpipe's. It's slower though. all_lines = file_.readlines() file_.close() retval = process.returncode assert retval in [ None, 0 ] text_lines = all_lines[:142] expected_points = [lsa_mod.Vector(-77.065654000000009205, 38.954610000000009506)] #print(text_lines) return generic_intersections(text_lines, expected_points, 'naive_intersections_partial_dc') def project_onto_x_axis_test(): '''Test projecting a line segment onto the X axis''' non_projected_line = lsa_mod.Line(lsa_mod.Vector(0.0, 0.0), lsa_mod.Vector(1.0, 1.0), is_segment=True) actual_line = non_projected_line.project_onto_x_axis() expected_line = lsa_mod.Line(lsa_mod.Vector(0.0, 0.0), lsa_mod.Vector(1.0, 0.0), is_segment=True) if actual_line == expected_line: return True else: sys.stderr.write('{}: project_onto_x_axis_test: Projection result was {}, expected {}\n'.format( sys.argv[0], actual_line, expected_line)) return False def project_onto_y_axis_test(): '''Test projecting a line segment onto the Y axis''' non_projected_line = lsa_mod.Line(lsa_mod.Vector(1.0, 1.0), lsa_mod.Vector(2.0, 3.0), is_segment=True) actual_line = non_projected_line.project_onto_y_axis() expected_line = lsa_mod.Line(lsa_mod.Vector(0.0, 1.0), lsa_mod.Vector(0.0, 3.0), is_segment=True) if actual_line == expected_line: return True else: sys.stderr.write('{}: project_onto_y_axis_test: Projection result was {}, expected {}\n'.format( sys.argv[0], actual_line, expected_line)) return False def two_intersecting_lines_test(): ''' Compute the intersection of two lines, and make sure the lines are present in the Intersection object. ''' all_good = True # Two lines that should intersect at 0.5, 0.5 line1 = lsa_mod.Line(lsa_mod.Vector(0.0, 0.0), lsa_mod.Vector(1.0, 1.0), is_segment=True) line2 = lsa_mod.Line(lsa_mod.Vector(0.0, 1.0), lsa_mod.Vector(1.0, 0.0), is_segment=True) if line1 > line2: line1, line2 = line2, line1 line_list = [ line1, line2 ] lsa_result = lsa_mod.naive_intersections(line_list) points = [] intersecting_lines = [] for point, set_of_intersecting_lines in lsa_result.gen_intersections(): points.append(point) intersecting_lines.append(set_of_intersecting_lines) expected_inter_set = set() expected_inter_set.add((line1, line2)) expected_inter_lines = [ expected_inter_set ] assert len(points) == 1 assert points[0] == lsa_mod.Vector(0.5, 0.5) assert len(intersecting_lines) == 1 if intersecting_lines != expected_inter_lines: sys.stderr.write('{}: two_intersecting_lines_test:\nintersecting_lines: {}\nexpected_inter_lines: {}'.format( sys.argv[0], pprint.pformat(intersecting_lines), pprint.pformat(expected_inter_lines), )) raise AssertionError return all_good def three_intersecting_lines_test(): ''' Compute the intersection of three lines, and make sure the lines are present in the Intersection object. ''' # This might be our only test that concerns itself at all with the order of points in a line segment line1 = lsa_mod.Line(lsa_mod.Vector(0.0, 0.0), lsa_mod.Vector(1.0, 1.0), is_segment=True) line2 = lsa_mod.Line(lsa_mod.Vector(0.0, 1.0), lsa_mod.Vector(1.0, 0.0), is_segment=True) line3 = lsa_mod.Line(lsa_mod.Vector(0.5, 0.0), lsa_mod.Vector(0.5, 1.0), is_segment=True) lines = [line1, line2, line3] expected_point = lsa_mod.Vector(0.5, 0.5) expected_line_set = set() expected_line_set.add((line1, line2)) expected_line_set.add((line1, line3)) expected_line_set.add((line3, line2)) expected_lines = [ expected_line_set ] lsa_result = lsa_mod.naive_intersections(lines) keys = list(lsa_result.intersections.keys()) assert len(keys) == 1 key = keys[0] if key != expected_point: sys.stderr.write('{}: three_intersecting_lines_test: keys not as expected: Got {}, expected {}\n'.format( sys.argv[0], key, expected_point)) return False actual_lines = list(lsa_result.intersections.values()) if actual_lines != expected_lines: sys.stderr.write('{}: three_intersecting_lines_test: values not as expected:\nGot:\n{}\n{}\n\nexpected:\n{}\n{}\n'.format( sys.argv[0], type(actual_lines), pprint.pformat(actual_lines), type(expected_lines), pprint.pformat(expected_lines))) return False return True def overlap_par_line_segs_test(): '''Test some overlapping, parallel line segments''' all_good = True line = functools.partial(lsa_mod.Line, is_segment=True, verbose=False) vector = lsa_mod.Vector for line1, line2, expected_result in [ (line(vector(0, 0), vector(3, 0)), line(vector(1, 0), vector(2, 0)), line(vector(1, 0), vector(2, 0))), (line(vector(0, 1), vector(0, 2)), line(vector(0, 1), vector(0, 2)), line(vector(0, 1), vector(0, 2))), (line(vector(0, 0), vector(0, 2)), line(vector(0, 1), vector(0, 3)), line(vector(0, 1), vector(0, 2))), (line(vector(0, 0), vector(0, 2)), line(vector(0, 1), vector(0, 3)), line(vector(0, 1), vector(0, 2))), (line(vector(0, 0), vector(0, 1)), line(vector(0, 1), vector(0, 2)), line(vector(0, 1), vector(0, 1))), (line(vector(0, 0), vector(1, 0)), line(vector(1, 0), vector(2, 0)), line(vector(1, 0), vector(1, 0))), ]: actual_result = line1.parallel_overlap(line2) if actual_result != expected_result: sys.stderr.write('{}: line1 {}, line2 {}, actual_reasult {} != expected_result {}\n'.format( sys.argv[0], line1, line2, actual_result, expected_result, )) all_good = False return all_good def line_magnitude_test(): '''Test computing the magnitude of a line segment''' all_good = True line = lsa_mod.Line(lsa_mod.Vector(0, 0), lsa_mod.Vector(1, 1), is_segment=True) if abs(line.magnitude() - math.sqrt(2)) >= lsa_mod.EPSILON: sys.stderr.write('{}: line_magnitude_test: Unexpected magnitude\n'.format(sys.argv[0])) all_good = False return all_good def is_point_test(): '''Test Line.is_point()''' all_good = True line1 = lsa_mod.Line(lsa_mod.Vector(0, 0), lsa_mod.Vector(0, 1), is_segment=True) if line1.is_point(): sys.stderr.write('{}: is_point_test: {} detected as point but should not be\n'.format(sys.argv[0], line1)) all_good = False line2 = lsa_mod.Line(lsa_mod.Vector(1.1, 1.1), lsa_mod.Vector(1.1, 1.1), is_segment=True) if not line2.is_point(): sys.stderr.write('{}: is_point_test: {} not detected as point but should be\n'.format(sys.argv[0], line2)) all_good = False line3 = lsa_mod.Line(lsa_mod.Vector(1.1, 1.2), lsa_mod.Vector(1.1, 1.1), is_segment=True) if line3.is_point(): sys.stderr.write('{}: is_point_test: {} detected as point but should not be\n'.format(sys.argv[0], line3)) all_good = False line4 = lsa_mod.Line(lsa_mod.Vector(0, 0), lsa_mod.Vector(0, 0.01), is_segment=True) if line4.is_point(): sys.stderr.write('{}: is_point_test: {} detected as point but should not be\n'.format(sys.argv[0], line4)) all_good = False return all_good def midpoint_test(): '''Test the midpoint method''' all_good = True point_a = lsa_mod.Vector(0, 0) point_b = lsa_mod.Vector(1, 1) line = lsa_mod.Line(point_a, point_b, is_segment=True) midpoint = line.midpoint() if midpoint.x_coord == 0.5 and midpoint.y_coord == 0.5: pass else: sys.stderr.write('{}: midpoint_test: not 0.5, 0.5\n'.format(sys.argv[0], )) all_good = False return all_good def naive_inter_and_over_1(): '''Test intersections and overlaps together''' all_good = True line1 = lsa_mod.Line(lsa_mod.Vector(0.0, 1.0), lsa_mod.Vector(1.0, 0.0), is_segment=True) line2 = lsa_mod.Line(lsa_mod.Vector(0.0, 0.0), lsa_mod.Vector(1.0, 1.0), is_segment=True) line3 = lsa_mod.Line(lsa_mod.Vector(5.0, 5.0), lsa_mod.Vector(6.0, 5.0), is_segment=True) line4 = lsa_mod.Line(lsa_mod.Vector(0.0, 0.5), lsa_mod.Vector(1.0, 0.5), is_segment=True) line5 = lsa_mod.Line(lsa_mod.Vector(10.0, 10.0), lsa_mod.Vector(30.0, 30.0), is_segment=True) line6 = lsa_mod.Line(lsa_mod.Vector(20.0, 20.0), lsa_mod.Vector(40.0, 40.0), is_segment=True) line_list = [ line1, line2, line3, line4, line5, line6 ] lsa_result = lsa_mod.naive_intersections(line_list) if len(lsa_result.intersections) != 1: sys.stderr.write('{}: len(lsa_result.intersections) != 1\n'.format(sys.argv[0])) print(len(lsa_result.intersections)) pprint.pprint(lsa_result.intersections) all_good = False if len(lsa_result.overlaps) != 1: sys.stderr.write('{}: len(lsa_result.overlaps) != 1\n'.format(sys.argv[0])) print(len(lsa_result.overlaps)) pprint.pprint(lsa_result.overlaps) all_good = False return all_good def main(): '''Main function''' all_good = True all_good &= equality_test() all_good &= inequality_test() all_good &= add_test() all_good &= subtract_test() all_good &= dot_product_test() all_good &= cross_product_test() all_good &= magnitude_test() all_good &= pythagorean_distance_test() all_good &= manhattan_distance_test() all_good &= line_point_distance_test() all_good &= square_area_test() all_good &= triangle_area_test() all_good &= line_intersection_test() all_good &= line_segment_intersection_test() all_good &= line_parallel_test() all_good &= line_seg_nonintersection_test() all_good &= project_onto_x_axis_test() all_good &= project_onto_y_axis_test() all_good &= two_intersecting_lines_test() all_good &= three_intersecting_lines_test() all_good &= line_magnitude_test() all_good &= overlap_par_line_segs_test() all_good &= is_point_test() all_good &= midpoint_test() all_good &= naive_intersections_1() all_good &= naive_intersections_2() all_good &= naive_intersections_3() all_good &= naive_intersections_4() all_good &= naive_intersections_partial_dc() all_good &= naive_inter_and_over_1() all_good &= naive_intersections_more_dc() if all_good: sys.exit(0) else: sys.stderr.write('{}: One or more tests failed\n'.format(sys.argv[0])) sys.exit(1) main()