Basic Shapes, Polygons, Trigonometry
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, requires 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. 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.
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 segment 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, i.e. \( m = \frac{\Delta y}{\Delta x} \), and \(b\) is the \(y\)intercept .
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 representation 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 nonintersecting 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).
Euclidean Shortest Path
The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.
We are given a start position \(L_{i}\) and a goal position \(L_{f}\), which we assume are in the free space. Our goal is to compute a shortest collisionfree path from \(L_{i}\) to \(L_{f}\), that is, a shortest path that does not intersect the interior of any of the obstacles. Notice that we cannot say the shortest path, because it need not be unique. For a shortest path to exist, it is important that obstacles are open sets; if they were closed, then a shortest path would not exist, as it would always be possible to shorten a path by moving closer to an obstacle.
This is not necessarily a short path, because some arcs are between nodes that are far apart, whereas others are between nodes that are close to each other. An obvious improvement would be to give each arc a weight corresponding to the Euclidean length of the segment connecting its incident nodes, and to use a graph search algorithm that ﬁnds a shortest path in a weighted graph, such as Dijkstra’s algorithm or propagating a wavefront from one of the points until it meets the other. Although this may improve the path length, we still do not get the shortest path. For now we will discuss Dijkstra's algorithm on a visibility graph.
In three (and higher) dimensions the problem is NPhard in the general case, but there exist efficient approximation algorithms that run in polynomial time based on the idea of finding a suitable sample of points on the obstacle edges and performing a visibility graph calculation using these sample points.
The visibility graph of \(L_{i}\), \(L_{f}\), and the obstacle set is a graph whose vertices are \(L_{i}\), \(L_{f}\), and the obstacle vertices, and vertices \(v\) and \(w\) are joined by an edge if \(v\) and \(w\) are either mutually visible or if \((v, w)\) is an edge of some obstacle. It follows from the above claim that the shortest path can be computed by first computing the visibility graph and labeling each edge with its Euclidean length, and then computing the shortest path by, say, Dijkstra's algorithm . Note that the visibility graph is not planar, and hence may consist of \(O\big( n^{2}\big)\) edges.
Dijkstra(G,start) finds all shortest paths from \(L_{i}\) to each other vertex in the graph, and shortestPath(G,Li,Lf) uses Dijkstra to find the shortest path from \(L{i}\) to \(L_{f}\).
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 
