Geometric algorithms are more commonly known by the name Computational Geometry. These algorithms are designed to solve geometric problems and are stated in terms of geometry. Geometric algorithms require in-depth knowledge of different mathematical subjects like topology, algebra and differential geometry. For example, topological maps, and computer-aided design and manufacturing are examples of the need for geometric algorithms. In fact, the use of geometric algorithms dates to the building of the pyramids. Most recently, geometric algorithms have become essential in the world or virtual and augmented reality design.
There are two main branches of computational geometry,
1. Combinatorial
2. Numerical
Combinatorial Computational Geometry
Combinatorial computational geometry is also called algorithmic geometry. The primary goal in combinatorial computational geometry is to develop efficient algorithms and data structures for solving problems in terms of basic geometrical objects such as circles, triangles polygons, etc.. Combinatorial computational geometry is used extensively in such construction areas as pyramid construction, marine construction to determine convex hull shapes, and in space craft constructions.
Numerical computational geometry
Numerical computational geometry (NCG) is also known as geometric modeling and computer-aided geometric design. Because numerical geometry is used primarily in in Computer-aided design and manufacturing (CAD/CAM) it makes use of parametric curves and surfaces and Bezier curves and splines.
Implementing a Geometric Algorithm:
Scenario
You are working on a project which requires you to work with geometric algorithms. You have been asked to explore an algorithm that checks if two lines intersect.
Objectives:
After completing this lab, you will be able to:
- Check if two line segments intersect.
Exercise 1:
In this exercise, you will check if two line segments intersect.
Task 1: Checking if two lines intersect
- On the Jupyter Index page, click File > New Notebook > Python 3.
- Copy the following code into the notebook
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def subtract(self, p):
return Point(self.x — p.x, self.y — p.y)
def cross_product(p1, p2):
return p1.x * p2.y — p2.x * p1.y
def direction(p1, p2, p3):
return cross_product(p3.subtract(p1), p2.subtract(p1))
def on_segment(p1, p2, p):
return min(p1.x, p2.x) <= p.x <= max(p1.x, p2.x) and min(p1.y, p2.y) <= p.y <= max(p1.y, p2.y)
def intersect(p1, p2, p3, p4):
d1 = direction(p3, p4, p1)
d2 = direction(p3, p4, p2)
d3 = direction(p1, p2, p3)
d4 = direction(p1, p2, p4)
if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
return True
elif d1 == 0 and on_segment(p3, p4, p1):
return True
elif d2 == 0 and on_segment(p3, p4, p2):
return True
elif d3 == 0 and on_segment(p1, p2, p3):
return True
elif d4 == 0 and on_segment(p1, p2, p4):
return True
else:
return False
#False
point1 = Point(1,1)
point2 = Point(10,1)
point3 = Point(1,2)
point4 = Point(10,2)
result = intersect(point1, point2, point3, point4)
print(result)
#True
point1 = Point(10,1)
point2 = Point(0,10)
point3 = Point(0,0)
point4 = Point(10,10)
result = intersect(point1, point2, point3, point4)
print(result)
#False
point1 = Point(-5,-5)
point2 = Point(0,0)
point3 = Point(1,1)
point4 = Point(10,10)
result = intersect(point1, point2, point3, point4)
print(result)
- To run the code, click Run.
- View the results.
Quiz solutions
1. The sort algorithm that is based on the idea of finding the minimum or maximum element in an unsorted array is called?
Merge sort
Bubble sort
Selection sort correct
Quick sort
Insertion sort
Answer
Correct, the Selection sort algorithm is one of the simplest sorting algorithm
2. Which sort algorithm makes use of the insertion sort and merge sort?
Timsort correct
Bubble sort
Quick sort
Selection sort
Insertion sort
Answer
Correct, the Timsort algorithm can make use of both the Insertion and Merge sort. Timsort first analyses a list that it is trying to sort and then chooses the best sorting approach based on the analysis of the list.
3. Insertion sorts provide several advantages. Which of the following are the main advantages?
Makes use of other sorts
Useful for large data sets and Timsorts
Simple implementation, efficient for small data sets and memory efficient correct
Efficient use of Quick sorts, merge sorts and memory efficient
Momory efficient, makes use of Bubble sorts and simple to implement
Answer
4. There are basically two main types of search algorithms. These are called:
Note: Make sure you select all of the correct options — there may be more than one!
Merge Search
Sequential Search
Linear Search
Interval Search
Bubble Search
5. Which type of search algorithm is considered to be the most efficient?
Interval Search correct
Sequential Search
Geometric Search
Graphing Search
Answer
Correct, Interval search algorithms are more efficient than sequential search algorithms because the Interval search breaks an array into smaller parts to be searched.
6. Linear or Sequential search algorithms…
sort data first before searching.
need data to be sorted before searching.
examine each element in the array in sequence, working from the beginning of the array to the end in a linear fashion. correct
compares the target value to the value of the item at the mid-point of the array.
Answer
Correct, Linear or Sequential search algorithms examine each element in the array in sequence, working from the beginning of the array to the end in a linear fashion.
7. Interval search algorithms …
uses data from multiple datasets to find the correct answer.
must use a simple binary approach for the search.
does not compares the target value to the value of the item at the mid-point of the array.
break the array into smaller parts to be searched. correct
Answer
Correct, Interval algorithms are more efficient than sequential search algorithms, but they need data to be sorted before searching.
8. Another name for Combinatorial Computational Geometry is,
Map geometry
Algorithmic Geometry correct
CAD/CAM geometry.
Modeling geometry.
Answer
Correct, the primary goal in combinatorial computational geometry is to develop efficient algorithms and data structures for solving problems in terms of basic geometrical objects such as circles, triangles and polygons.
Note: Make sure you select all of the correct options — there may be more than one!
9. Geometric algorithms can be used for which of these tasks?
Building topographical maps
Computer-aided design and manufacturing
Construction
Pyramid building
Aerospace design
10. AI application for Geometric algorithms include:
Planning and collision avoidance for robots in motion; planning the best path around a complicated obstacle.
Defining airspace with geographic information systems to resolve airspace issues, and direct search and rescue efforts.
Studying biochemistry and virology to advance medical research and treatments.
All of the above correct
Answer
all of these applications make use of geometric and graphing algorithms.
