Tue, 23 Jan 2018 14:09:44 +0200
Added bowtie check
geometry.py | file | annotate | diff | comparison | revisions | |
tests/quadrilaterals.py | file | annotate | diff | comparison | revisions |
--- a/geometry.py Tue Jan 23 12:29:30 2018 +0200 +++ b/geometry.py Tue Jan 23 14:09:44 2018 +0200 @@ -410,3 +410,48 @@ assert(len(polygon.vertices) == 3) a, b, c = polygon.vertices[:3] return cross_product(b - a, b - c) + +def line_intersection_xy(line_1, line_2): + ''' + Computes 2D line intersection. Can return a point outside the given + segments. Z is ignored. + ''' + a, b = line_1.vertices + c, d = line_2.vertices + denominator = (a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x) + x = (c.x - d.x) * (a.x * b.y - a.y * b.x) + x -= (a.x - b.x) * (c.x * d.y - c.y * d.x) + y = (c.y - d.y) * (a.x * b.y - a.y * b.x) + y -= (a.y - b.y) * (c.x * d.y - c.y * d.x) + try: + x /= denominator + y /= denominator + except ZeroDivisionError: + return None + else: + return Vertex(x, y, 0) + +def line_segment_intersection_xy(line_1, line_2): + ''' + Computes 2D line intersection. Only returns a result if it falls + inside the line segments. Z is ignored. + ''' + from math import inf + intersection = line_intersection_xy(line_1, line_2) + if intersection: + a, b = line_1.vertices + c, d = line_2.vertices + try: + t = (intersection.x - a.x) / (b.x - a.x) + except ZeroDivisionError: + t = inf + try: + u = (intersection.y - a.y) / (b.y - a.y) + except ZeroDivisionError: + u = inf + if 0 < t < 1 or 0 < u < 1: + return intersection + else: + return None + else: + return None
--- a/tests/quadrilaterals.py Tue Jan 23 12:29:30 2018 +0200 +++ b/tests/quadrilaterals.py Tue Jan 23 14:09:44 2018 +0200 @@ -9,7 +9,11 @@ def concave_test(model): ''' Checks that all quadrilaterals are convex. ''' for quadrilateral in model.quadrilaterals: + # Rotate the polygon into the XY plane. Then z is facing + # away from the quadrilateral. geometry = transform_to_xy(quadrilateral.geometry) + # Now do a 2D concavity test: + # https://math.stackexchange.com/a/1745427 z_scores = [ cross_product(v2 - v1, v3 - v1).z for v1, v2, v3 in pairs(geometry.vertices, count = 3) @@ -35,10 +39,23 @@ ) break +def bowtie_test(model): + for quadrilateral in model.quadrilaterals: + geometry = transform_to_xy(quadrilateral.geometry) + vertices = IndexRing(geometry.vertices) + for i in (0, 1): + line_1 = LineSegment(vertices[0 + i], vertices[1 + i]) + line_2 = LineSegment(vertices[2 + i], vertices[3 + i]) + intersection = line_segment_intersection_xy(line_1, line_2) + if intersection: + yield error(quadrilateral, 'self-intersecting') + break + manifest = { 'tests': { 'skew': skew_test, 'concave': concave_test, + 'bowtie': bowtie_test, }, 'messages': { 'skew-error': lambda skew_angle: @@ -50,5 +67,6 @@ degree_rep(skew_angle), ), 'concave-error': 'concave quadrilateral', + 'self-intersecting': 'bowtie quadrilateral', }, }