Concave Quadrilaterals

This was a nice problem. First of all,as a rule of thumb in Computational geometry it is not good to deal with angles.It is exceedingly difficult and things get messy soon. A nice way to handle this problem is to use the $CCW$ algorithm. $CCW$ takes three points $A$ , $B$ , and $C$ as arguments and asks: do these three points make a counterclockwise turn,in other words is $\angle ABC$ a counterclockwise angle. Checking concavity is straightforward from there,sort the points in a clockwise order and check if each three pair of angles is $CCW$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import numpy as np
File=#file.read() goes here
Points=[]
for i in File.split('\n'):
    a=i.split()
    B=[]
    for j in range(0,8,2):
        B.append((int(a[j]),int(a[j+1])))
    Points.append(B)

def clockwise(points):
    x , y = points[0,:] , points[1,:]
    cx , cy = np.mean(x) , np.mean(y)
    a = np.arctan2(y - cy, x - cx)
    order = a.ravel().argsort()
    x , y = x[order] ,  y[order]
    return np.vstack([x,y])

def ccw(A,B,C):
    return (C[1]-A[1])*(B[0]-A[0]) > (B[1]-A[1])*(C[0]-A[0])

def isConvex(points):
    n = len(points)
    Pts = clockwise(np.array([[i[0] for i in points],[i[1] for i in points]]))
    points = [(Pts[0][i],Pts[1][i]) for i in range(len(Pts[0]))]
    for i in range( n):
        # Check every triplet of points
        A , B , C= points[i % n] ,points[(i + 1) % n],points[(i + 2) % n]
        if not ccw(A, B, C):
            return False
    return True

print filter( isConvex(x),Points).count(False) + 6

I am learning python and computer science is quite new for me. First, I struggled with handling the raw data. I copied the text to a text file on the desktop and wrote:

list=open('C:/Users/Admin/Desktop/text.txt').read().split()
case=[]
for i in range(100):
    vertex=()
    for x in range(8):
        vertex+=(list[8*i+x],)
    case.append(vertex)

to create a list of 100 tuples, each tuple contains the coordinates of vertex of a quadrilateral.

The next step I thought of is to write a procedure to test whether a quadrilateral is convex or not, given its vertex's coordinates. My approach was: given X,Y,Z,T is 4 vertex, consider whether X,Y in the same side with regard to ZT and wheter Z,T in the same side with regard to XY. If both cases result in True or False, then the quadrilateral is convex. If one case is True, one case is False, then the quadrilateral is concave. So I wrote:

def same(x,y,z,t):
    a=(y[0]-x[0],y[1]-x[1])
    b=(z[0]-x[0],z[1]-x[1])
    c=(t[0]-x[0],t[1]-x[1])
    d=(a[1],-a[0])
    e=(b[0]*d[0]+b[1]*d[1])*(c[0]*d[0]+c[1]*d[1])
    return e
def test(x,y,z,t):
    if same(x,y,z,t)*same(z,t,x,y)<0:
        return False
    return True

The "test" procedure will return True if the quadrilateral is convex. Then I wrote:

n=0
for i in range(100):
    x=(int(group[i][0]),int(group[i][1]))
    y=(int(group[i][2]),int(group[i][3]))
    z=(int(group[i][4]),int(group[i][5]))
    t=(int(group[i][6]),int(group[i][7]))
    if not (test(x,y,z,t)):
        n+=1
print n

to test 100 given quadrilaterals. This printed 29, so the answer is $\boxed{35}$

First, note that the convexity / concavity of a quadrilateral doesn't change if it is translated. Given a quadrilateral $A_1 (x_1, y_1), A_2 (x_2, y_2), A_3 (x_3, y_3), A_4 (x_4, y_4),$ we can translate it in four ways so that one of the vertices goes to the origin. If we want $A_4$ to go to the origin, the coordinates of $A_1, A_2, A_3$ should be $(x_1 - x_4, y_1-y_4), (x_2-y_4, y_2 - y_4), (x_3-y_4, y_3-y_4)$ respectively. Similarly we can determine the coordinates of the other vertices given that one of the vertices goes to the origin.

In the following code, we build four functions translate1 , translate2 , translate3 , translate4 which return the coordinates of the quadrilateral when it is translated in such a way that $A_1, A_2, A_3, A_4$ go to the origin respectively.

def transate1(x1, y1, x2, y2, x3, y3, x4, y4):
  return [x1-x1, y1-y1, x2-x1, y2-y1, x3-x1, y3-y1]

def translate2(x1, y1, x2, y2, x3, y3, x4, y4):
  return [x1-x2, y1-y2, x2-x2, y2-y2, x3-x2, y3-y2]

def translate3(x1, y1, x2, y2, x3, y3, x4, y4):
  return [x1-x3, y1-y3, x2-x3, y2-y3, x3-x3, y3-y3]

def translate4(x1, y1, x2, y2, x3, y3, x4, y4):
  return [x1-x4, y1-y4, x2-x4, y2-y4, x3-x4, y3-y4]

A quadrilateral is concave if and only if one of its vertices lies inside the triangle determined by the other three vertices.

In general, consider a triangle $A (x_1, y_1), B (x_2, y_2), C (x_3, y_3).$ We have to find out whether the origin $O (0, 0)$ lies within this triangle or not. Let $(B_A, B_B, B_C)$ be the normalized barycentric coordinates of $O$ with respect to $\triangle ABC,$ where $B_A+B_B+B_C= 1.$ Assign the vectors $\vec{O}, \vec{A}, \vec{B},\vec{C}$ to points $O, A, B, C$ respectively. Let $\vec{\bf{i}}$ and $\vec{\bf{j}}$ be the unit vectors along the $x$ and $y$ axes respectively. We then have $\begin{array}{lcl}\vec{O} &=& B_A \vec{A} + B_B \vec{B} + B_C \vec{C}\\ & = & B_A \left( x_1 \cdot \vec{\bf{i}} + y_1 \cdot \vec{\bf{j}} \right ) + B_B \left( x_2 \cdot \vec{\bf{i}} + y_2 \cdot \vec{\bf{j}} \right) + B_C \left( x_3 \cdot \vec{\bf{i}} + y_3 \cdot \vec{\bf{j}} \right) \\ & = & \left( B_A x_1 + B_B x_2 + B_C x_3 \right) \cdot \vec{\bf{i}} + \left( B_A y_1 + B_B y_2 + B_C y_3 \right) \cdot \vec{\bf{j}}. \end{array}$ Since $O$ is the origin, $\vec{O} = 0 \cdot \vec{\bf{i}} + 0 \cdot \vec{\bf{j}}.$ We thus have three equations in $B_A, B_B, B_C.$ $\begin{array}{lcl} B_A x_1 + B_B x_2 + B_C x_3 & = & 0 \\ B_A y_1 + B_B y_2 + B_C y_3 & = & 0 \\ B_A + B_B + B_C & = & 1 \end{array}$

After some tedious calculations (I fed it in WolframAlpha, although the determinant method should work just fine. :P ), we find out that the solutions are:
$\begin{array}{lcl} B_A & = & \dfrac{x_3 (y_3 - y_2) + y_3 (x_2 - x_3)}{(y_2-y_3)(x_1-x_2) + (x_3-x_3)(y_1-y_3)} \\ B_B & = & \dfrac{x_3(y_1-y_3) + y_3 (x_1-x_3)}{(y_2-y_3)(x_1-x_2) + (x_3-x_3)(y_1-y_3)} \\ B_C & = & \dfrac{x_3 (y_2-y_1) + y_3 (x_2-x_1)}{(y_2-y_3)(x_1-x_2) + (x_3-x_3)(y_1-y_3)} . \end{array}$

$O$ will lie within $\triangle ABC$ if and only if $B_A, B_B, B_C > 0.$ I don't know why, but Python can't compare between two float numbers. Instead of finding the signs of $B_A, B_B, B_C$ directly, we can compare the signs of the numerators and denominators of $B_A, B_B, \text{ and }B_C.$ We define $\text{sgn}(x):\mathbb{R} \rightarrow \{0, 1, -1\}$ as follows. $\begin{cases} \text{sgn}(x) = 1 & \text{ if } x>0 \\ \text{sgn}(x) = 0 & \text{ if } x= 0 \\ \text{sgn} (x)= -1 & \text{ if } x<0 \end{cases}$
Here's the implementation of $\text{sgn}(x)$ in Python.

def sgn(x):
    if x==0:
        return 0
    if x>0:
        return 1
    if x<0:
        return -1

Now, note that a number $\dfrac{a}{b} \ (b \neq 0)$ is positive if and only if $\text{sgn}(a) = \text{sgn} (b).$ Therefore, our required condition is: $\begin{array}{lcl} \text{sgn} (x_3 (y_3 - y_2) + y_3 (x_2 - x_3)) & = & \text{sgn} ((y_2-y_3)(x_1-x_3) + (x_3-x_2)(y_1-y_3)) \\ \text{sgn} (x_3(y_1-y_3) + y_3 (x_1-x_3)) & = & \text{sgn} ((y_2-y_3)(x_1-x_3) + (x_3-x_2)(y_1-y_3)) \\ \text{sgn} (x_3 (y_2-y_1) + y_3 (x_2-x_1)) & = & \text{sgn} ((y_2-y_3)(x_1-x_3) + (x_3-x_2)(y_1-y_3)). \end{array}$ In the following Python code, we define $\begin{array}{lcl} \text{num1} & = & x_3 (y_3 - y_2) + y_3 (x_2 - x_3) \\ \text{num2} & = & x_3(y_1-y_3) + y_3 (x_1-x_3) \\ \text{num3} & = & x_3 (y_2-y_1) + y_3 (x_2-x_1) \\ \text{den} & = & (y_2-y_3)(x_1-x_3) + (x_3-x_3)(y_1-y_3), \end{array}$ so our required condition is $\text{sgn(num1)} = \text{sgn(num2)} = \text{sgn(num3)}= \text{sgn(den).}$

def within_triangle(x1, y1, x2, y2, x3, y3):
    num1= (y3-y2)*x3 + (x2-x3)*y3
    num2= (y1-y3)*x3 + (x3-x1)*x3
    num3= (y2-y1)*x3 + (x2-x1)*y3
    den= (y2-y3)*(x1-x3) + (x3-x2)*(y1-y3)
    return sgn(den)==sgn(num1) & sgn(den)==sgn(num2) & sgn(den)==sgn(num3)

We just have to check whether the origin lies in atleast one of the triangles returned by the translate functions. The following code take cares of that.

def concavity(x1, y1, x2, y2, x3, y3, x4, y4):
    a= transform1(x1, y1, x2, y2,  x3, y3, x4, y4)
    p= within_triangle(a[0], a[1], a[2], a[3], a[4], a[5])
    b= transform2(x1, y1, x2, y2,  x3, y3, x4, y4)
    q= within_triangle(b[0], b[1], b[2], b[3], b[4], b[5])
    c= transform3(x1, y1, x2, y2,  x3, y3, x4, y4)
    r= within_triangle(c[0], c[1], c[2], c[3], c[4], c[5])
    d= transform4(x1, y1, x2, y2,  x3, y3, x4, y4)
    s= within_triangle(d[0], d[1], d[2], d[3], d[4], d[5])
    return p==True or q==True or r==True or s==True

All that remains is to handle the input data. The following code goes through each line of the file and checks whether the quadrilateral formed is concave or not. The variable count stores the number of concave quadrilaterals the program has encountered.

f= open('convex_quadrilaterals.txt','r')
a= []
count=0
for line in f:
    a= [int(x) for x in line.split()]
    if concavity(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7])==True:
        count+=1
print count

This prints $36,$ so $N-1= \boxed{35}.$

To test if $ABCD$ is a concave quadrilateral, we test if $A$ in $BCD$ or $B$ in $ACD$ or $C$ in $ABD$ or $D$ in $ABC$ , that means we test if a point is inside the triangle formed by other three points. To test if $A$ is in $BCD$ , we test if $A,B$ , $A,C$ , $A,D$ , are the same side to $CD$ , $BD$ , $BC$ respectively. To test if $A,B$ is the same side to $CD$ , we first choose vector $\vec{n}(-y_{\vec{CD}}, x_{\vec{CD}})$ , then $\vec{n}\perp\vec{CD}$ . If $(\vec{n}\cdot\vec{CA})(\vec{n}\cdot\vec{CB})\ge 0$ then $A,B$ must be same side to $CD$

Here is the code to count the quadrilaterals

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

function vector(a, b)
{
    var v={}

    v.x=b.x-a.x;
    v.y=b.y-a.y;

    return v;
}

function pendi(v)
{
    var nv={}

    nv.x=-v.y;
    nv.y=v.x;

    return nv;
}

function dot(u,v)
{
    return u.x*v.x+u.y*v.y;
}

function sameside(a, b, c, d)
{
    var ab=vector(a, b);
    var ac=vector(a, c);
    var ad=vector(a, d);

    var n=pendi(ab);
    return dot(ac, n)*dot(ad, n)>=0;

}

function inside(a, b, c, d)
{
    return  sameside(b, c, a, d)&&
    sameside(c, d, a, b)&&
    sameside(d, b, a, c);
}

function isConcave(q)
{
    return  inside(q.points[0], q.points[1], q.points[2], q.points[3])||
    inside(q.points[1], q.points[0], q.points[2], q.points[3])||
    inside(q.points[2], q.points[0], q.points[1], q.points[3])||
    inside(q.points[3], q.points[0], q.points[1], q.points[2]);
}

var s="paste data string here";

var ps=s.split(/\s+/); //split data
var qs=[];

while(ps.length)
{
    var q={points:[]}

    for(var i=0;i<4;i++)
    {
        var p={x:0,y:0}

        p.x=parseInt(ps.shift());
        p.y=parseInt(ps.shift());

        q.points.push(p);

        //extract 4 points
    }

    qs.push(q);
}

var c=0; //count

for(var i=0;i<qs.length;i++)
    if(isConcave(qs[i]))
        c++;

//result is in variable c