45 lines
1.2 KiB
Python
45 lines
1.2 KiB
Python
import sys, os
|
|
sys.path.insert(0, os.path.dirname(__file__))
|
|
from convex_hull import convex_hull, hull_area, point_in_hull
|
|
|
|
def test_square():
|
|
pts = [(0,0),(1,0),(1,1),(0,1),(0.5,0.5)]
|
|
h = convex_hull(pts)
|
|
assert len(h) == 4
|
|
assert hull_area(h) == 1.0
|
|
|
|
def test_triangle():
|
|
h = convex_hull([(0,0),(2,0),(1,2),(1,1)])
|
|
assert len(h) == 3
|
|
assert abs(hull_area(h)-2.0) < 1e-9
|
|
|
|
def test_collinear_excluded():
|
|
h = convex_hull([(0,0),(1,0),(2,0),(2,2),(0,2)])
|
|
# collinear bottom edge middle point excluded
|
|
assert (1,0) not in h
|
|
assert len(h) == 4
|
|
|
|
def test_keep_collinear():
|
|
h = convex_hull([(0,0),(1,0),(2,0),(2,2),(0,2)], keep_collinear=True)
|
|
assert (1,0) in h
|
|
|
|
def test_duplicates():
|
|
h = convex_hull([(0,0),(0,0),(1,0),(0,1)])
|
|
assert len(h) == 3
|
|
|
|
def test_single():
|
|
assert convex_hull([(5,5)]) == [(5,5)]
|
|
|
|
def test_empty():
|
|
assert convex_hull([]) == []
|
|
|
|
def test_point_in():
|
|
h = [(0,0),(2,0),(2,2),(0,2)]
|
|
assert point_in_hull((1,1), h)
|
|
assert point_in_hull((0,0), h) # boundary
|
|
assert not point_in_hull((3,3), h)
|
|
|
|
def test_area_triangle():
|
|
h = [(0,0),(4,0),(0,3)]
|
|
assert abs(hull_area(h)-6.0) < 1e-9
|