#!/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()