# HG changeset patch
# User Santeri Piippo
# Date 1516709384 -7200
# Node ID 5933250813a36e6d160521aae58824d6290ea788
# Parent  3089611c99d1fc4ac337036ced9e2933bf8de4ac
Added bowtie check

diff -r 3089611c99d1 -r 5933250813a3 geometry.py
--- 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
diff -r 3089611c99d1 -r 5933250813a3 tests/quadrilaterals.py
--- 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',
     },
 }