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.

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:

Exercise 1:

In this exercise, you will check if two line segments intersect.

Task 1: Checking if two lines intersect

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)

1. To run the code, click Run.
2. 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

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

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

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

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.

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

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

Modeling geometry.

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