HIGH SCHOOL OF ENGINEERING

MECHANICS AND ELECTRICAL

CULHUACAN UNIT

CAREER: COMPUTER ENGINEERING

ASIGNATURA: ANÁLISIS DE ALGORITMOS

WRITTEN WORK
GEOMETRIC ALGORITHMS

TEACHER: DR. GUARDIAN SOTO BEATRIZ DOLORES

GROUP: 5CM23

STUDENTS:
ANTONIO NORIEGA ALFREDO
LECHUGA ORTEGA JESÚS ALEJANDRO
OSNAYA ARRIETA JOSÉ DANIEL
SILVA ROBLES ARI RAÚL

ENTREGA: 7 DE NOVIEMBRE DEL 2018

1
Content
Objective....................................................................................................3
Introductionn .............................................................................................3
Theorya ........................................................................................................4
Examples...................................................................................................7
Geometric algorithms .........................................................................7
Geometric Search...............................................................8
Inclusion of polygons............................................................................9
Polygon intersections .10
Applications............................................................................................13
Geometric algorithms .......................................................................13
Geometric Search...........................................................................13
Inclusion of polygons..........................................................................13
Polygon intersections .....................................................................13
Works cited.....................................................................................14

2
Objective
The purpose of this report is to broadly outline the geometric algorithms.
presented, how they are applicable and their definition.

Introduction
Geometric algorithms, or computational geometry as it is better known, is
a branch of computer science that studies algorithms for solving
geometric problems. Within geometric algorithms, techniques are used
like the geometric search which, as its name suggests, will analyze from a
geometric space some characteristic or key point needed, while
también será utilizada la inclusión de polígonos que será dada un figura geométrica
a plane that is bounded by three or more lines and has three or more angles and vertices is
will conduct some search or polygons will relate to each other leading to the
intersection of polygons where it will be the union of taking more than one polygon being
broadly speaking, the topics that make up geometric algorithms and see what they are
very applicable and from here derive some algorithms such as Voronoi, March
of Javis and the Scan of Graham.

Figure 1. Geometric Representation

Source: M. Macho.: Posts Tagged 'computational geometry'

3
Theory
Although Computational Geometry emerged in the late 1970s specialized in the area
of design and analysis of algorithms.
With approaches that sought:

Systematic study of algorithms and data structures of geometric objects,

with a focus on exact (deterministic) algorithms.

Gather math and computer science problems.

Applications to numerous areas such as: computer graphics, systems of

geographic information, robotics, computer vision, etc.

A good solution to the problem of Computational Geometry requires a

good understanding of the geometric structure of the problem and knowledge
deep in algorithms and data structures.

Geometric algorithms operate on geometric objects such as points,

segments or polygons.
We will analyze two-dimensional algorithms in which each geometric object is
represented as a set of points{ } =( , ) , ∈

Figure 2. Geometric Construction from Points

Source: Miguel Sancho.: Computational Geometry

Some say that the first algorithm of Computational Geometry was born when a
a series of correct, unambiguous steps with an ending that solves a problem
geometric, the predecessor: Euclid, but it is only in the early 1970s that Michael
Shamos begins a systematic study of problems, obsessed with the idea of
create a new discipline of computer science, which I call Geometry
Computational

4
 Imagen 1. Michael Shamos padre de la Geometría Computacional

Research in this area has found many real-life applications:

Robotics, voice and pattern recognition, graphic design, information systems
geographical, etc.

Computational geometry seeks different parameters for applicable examples.

Well, this search arises from a series of geometric data that will be observed.
and will analyze if a certain geometric condition is fulfilled in the data, that
the condition is proposed according to the proposed problem besides seeking it can be
locate points or figures, given a partition of the geometric space, is calculated
efficiently in which cell the point is located.

Figure 3. Search in geometric space

Source: Pablo Brasero Moreno.: Set of points

Considering the partition of the plane determined by a simple polygon (interior region
and exterior). It is the definition of the inclusion of polygons but first we must detail the
What is a polygon? Well, a polygon is a flat geometric figure that is
limited by three or more lines and has three or more angles and vertices

5
 Figure 4. Characteristics of a polygon

Source: s/author.: Elements of a polygon

These polygons can face being related or joined to another polygon to this
we know as an intersection where 2 or more polygons interact
Where they cannot occupy the same place at the same time

There are no intersection points

There are intersection points between different geometric objects.

Natural extension of location problems and geometric search

Removal of hidden lines in graphic design

Figure 5. Intersection of 2 polygons

Source: M. Sepúlveda: Convex Polygons:

6
Examples
Geometric algorithms
First Example
Start
Read a, b, c
Calculate perimeter = a+b+c
Write perimeter
End.
2nd Example

3rd Example

7
Calculate the distance between two points

Formula=

Geometric Search
1st Example
Given a region of space, pre-process a set of figures to locate.
Where are points a, b, and c located according to the representation?

Point a is located outside of any region.

of some figure
Point b is located in the region of
decagon
Point c is located in the region of
heptagon

2nd Example
Given a region of space, pre-process a set of points to count from
efficient way how many there are in the region.

Points within the triangular region = 5

Points outside the triangular region = 11

8
3rd Example
If we think of the players on the field as points on a
Plan, we can find out what their Voronoi region will be for each of them.
that will be formed by the points of the playing field that are closest to
each player that the rest.

Inclusion of polygons
1st Example
A convex polygon P given by the Cartesian coordinates of its vertices
as it appears when traversing P counterclockwise.

P={(x0,y0),(x1,y1),…,(xn,yn)= (x0,y0)}
Step 1:
Find the point O, the centroid of the triangle with vertices (x0,y0), (x1,y1), (x2,y2).
Step 2:
Find the list of the polar coordinates of the vertices of P, with respect to the
point O and the positive direction of the OX axis.
P = {(m0,a0),(m1,a1),…,(mn,an) = (m0,a0)}
Step 3 :
Find the minimum, a2, of the values
{a0,a1,….,an-1}

Step 4:
Reorder the vertices of P as follows

P = {(mk, ak), (mk+1, ak+1), ..., (mn, an)}

(m0, a0), (m1, a1), ..., (mk, a)
2nd Example
If any simple polygon, we will provide an algorithm to locate a
point x concerning P that does not require any process. For clarity of
The algorithm will assume that the y-coordinate of point X is different from all the others.
coordinates of the vertices of the polygon
P = {(x0,y0),(x1,y1),…,(xn,yn) = (x0,y0)}
X = (x,y)
Step 1:
i <= 0, c <= 0
Step 2:
If i = n go to step 6
9
 Step 3:
If yi < y < yi+1 or yi > y > yi+1
And also the point X is to the left of the segment endpoints, then c =
c+1
Step 4:
I=i+1
Step 5:
Return to step 2
Step 6:
If c is odd, the answer is, the point is interior, otherwise the point is
Exterior.

Intersection of polygons
1st Example
Given a set P of points in the plane, we define the convex hull of P and the
we call EC(P), as the smallest convex set that contains it
We know that the set Pi = (Xi,Yi), with i = 1,…,N teaches the computer to calculate the
convex hull, as in the figure

1st Example Algorithm March of Javis

Calculate a point that we are sure is on the convex hull.
point with the lowest Y coordinate) Operating time O(N)
Calculate the angle formed by the remaining N-1 points with the and with the
horizontal, and choose the smallest Operation time O(N)
Calculation from P0 to P1

•
10
 We follow the same procedure from P0 to P1.

•
For P3

•
2nd Example Graham's Scan Algorithm
Calculate a point EC(P), for example, the lowest P0
Angularly arrange the remaining N–1 with respect to P0
Operational cost O(N*log(N))
Starting at P0 and following the ordered list, we check every 3 points.
whether the rotation by them is clockwise or counterclockwise and based on that sign we decide if
delete the central or not
Operating cost O(N) checks
•Elegido P0, etiquetamos los demás puntos siguiendo el orden angular, tal y
as seen in the previous figure. Next, we check the direction of the
turn of the first trio (P0, P1, and P2):

•
Since the turn is positive, counterclockwise, we move forward and consider the following
tern (P0, P1, P2)

11
 •
Once again the turn is positive, we continue with (P2, P3, P4):

•
When the turn is negative, as in the previous figure, we eliminate the point.
central of the ternary that will therefore not be part of the convex hull,
we step back a point and start over

•
3rd Example
In an art gallery, they want to place security cameras in such a way that
enclose the largest possible area, while occupying the least amount of space.
how many cameras will be necessary for any type of
room? In which part of the room should these cameras be placed?

12
 •

Applications
Geometric algorithms
Graphic computing, Robotics, integrated circuit design. Algorithms
geometric operations on geometric objects such as points, segments or
polygons.
Geometric Search
This process has a greater interest in geographical areas, statistics, and design.
automatic which is where they are mostly applied to solve problems
Inclusion of polygons
Shape recognition
Circuit design
Linear programming
Statistics
Intersection of polygons
Recognition of shapes that intervene in the intersection
Circuit design
Linear programming
Statistics

13
Works Cited
[Link]. (August 11, 2012). Posts Tagged 'Computational Geometry'. Retrieved from
[Link]
Mendoza, F. R. (2018). Geometría [Link] de Los Andes, -.
Sancho, M. (July 13, 2013). Computational Geometry. Obtained from
[Link]
subdivisions
Sepúlveda, m. (June 25, 2012). Convex Polygons: Obtained from the Caliber Method
Rotating:
[Link]
theory/[Link]

14