Basic Shapes, Polygons and Trigonometery
Computers are being used more and more to solve geometric problems. Geometric objects like points, lines and polygons are the basis of a broad variety of important applications and give rise to an interesting set of problems and algorithms. Geometric algorithms are important in design and analysis systems modeling physical objects, graphics design,medicine and game development. A designer working with a physical object has a geometric intuition. This is however part of the difficulty of geometric programming as certain "obvious" operations you do with a pencil, such as finding the intersection of two lines, require nontrivial programming to do correctly with a computer. The field of geometric algorithms is interesting to study because of its strong historical context; geometry was the most valued of the classic mathematical topics, and even above the gateway to Plato's academy appears the inscription "Let no one who is ignorant of geometry enter here."
Computational Geometry in Surgery
Geometric problems appear in modeling of medical objects, humanbody tissue structures, medical imaging and even computer aided surgery. Below is an image of a surface model of the human cortex.
Contents
Lines and Points
Most of the larger scale geometric programs depend on simple geometric objects defined in a twodimensional space. The fundamental object is a point, which we consider to be a pair of integersthe "coordinates" are the usual Cartesian (even though other systems are plausible). A line is merely the shortest distance between any two points. Lines are however of infinite length in both directions, as opposed to line segments. Here we discuss only lines limited to the plane.
Representation
Lines can be represented either as points or equations. Every line can be completely described by a pair of points \((x_1,y_1)\) and \((x_2,y_2)\). It can also be described by equations of the form \(y = mx + b\), where \(m\) is the slope of the line and \(b\) is the \(y\)intercept: \( m = \frac{\Delta y}{\Delta x} \).
Vertical lines are however a problem because they cannot be described by such an equation because of the division by zero. The equation \(x = k\) represents a vertical line that crosses the \(x\)axis at the point \((k,0)\). This problem can be avoided by using the more general formula
\[ax + by + c = 0.\]
We can thus conceive two possible representations of lines: either the point representation or the \(a,b,c\) equation representation above. Let us start by representing a point in code:
1 2 3 4 5 6 7 8 9 

We can proceed to formulating a twopoint representation of a line:
1 2 3 4 5 6 7 8 9 

We can also easily implement the a,b,c form. Let us call this class line2
:
1 2 3 4 5 6 7 8 9 

These equation and point forms can be interconverted using a function like the one below:
1 2 3 4 5 6 7 8 9 

Polygons
Polygons are a set of points that form a closed chain of non intersecting line segments. By closed, we mean that the first vertex of the chain is also the last. "Nonintersecting" means that pairs of segments only touch at their endpoints.
Polygons are essential for describing most shapes in planes. We could represent polygons as a set of lines using our line class. This is however not necessary because they can easily be represented as a set of coordinate points. We can then assume a segment exists between the \(i^\text{th}\) and \((i+1)^\text{th}\) points in the chain. We thus implement it as simply an array of point
objects.
1 2 3 4 5 6 7 8 9 10 11 

We can for example represent the below triangle as
1 2 3>>> Triangle = polygon([point(1,3),point(5,5),point(4,2)]) >>> print(Triangle) (1,3) , (5,5) , (4,2)
The file attached with this problem contains a list having \(100\) lines. Eight numbers \(x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4\) are written in each line, which correspond to a quadrilateral whose vertices have coordinates \[A_1=(x_1, y_1),\ A_2=(x_2, y_2),\ A_3=(x_3, y_3),\ A_4=(x_4, y_4)\] (in Cartesian plane). There are \(N\) quadrilaterals in this list which are concave.
Find \(N+6.\)
Details and Assumptions:
As an explicit example, suppose the list had \(2\) lines, and the following numbers were written on those two lines: \[\begin{array}{lrrrrrrrrl} &1, &1, &2, &2, &3, &3, &4, &4 \\ &1, &1, &2, &2, &3, &3, &4, &4 &.\end{array} \] We have two quadrilaterals, the first one having its vertices at points \((1, 1), (2, 2), (3, 3), (4, 4),\) and the second one having its vertices at points \((1, 1), (2, 2), (3, 3), (4, 4).\) Your job is to find out how many of them are concave.
Link to the file: http://pastebin.ca/2679837.
If one of the vertices lies on the line joining two other vertices, consider the resulting figure as convex.
This is a computer science problem, and is inspired from ProjectEuler (I don't remember the problem number at the moment).