Extensions for Point and Circle

Extensions for Point and Circle#

If you finish up and want more practice, here are two extensions.

Extension 1: Closest Point#

In the first Coursera course, we worked through the first 4 steps for the “closest point” problem—given a set S and a point P, find the member of S which is closest to P. Now you are ready to turn this into code, though as we will describe below, we are going to change the problem slightly (so you will want to work back through Steps 1–4).

You already have a Point class from a previous assignment, which you will use for this assignment.

Your job is to write the function: closest_point(s, p)

where:

  • s is a set of Points and

  • p is a Point such that this function returns the subset of points from s closest to p.

Note that this is slightly different then what we did in the Course 1 video for Steps 1–4, where we returned one single point.

However, as there may be more than one point at the same distance from p, it makes sense to return a set.

For example, if


s = { Point(3, 4), Point(-3, -4), Point(5, 6), Point(12, 8) }

and


p = Point(0,0)

then both (3,4) and (-3, -4) are the same distance (5) from p. So this function would return { Point(3, 4), Point(-3, -4) }

Also note that by returning a set, we can say that when the input set (s) is empty, you can just return the empty set.

Comparing Numbers#

In order to implement this algorithm correctly, it will be necessary for you to use a special function you have not encountered before for comparing two numbers.

As we will discuss later in the semester, when computers work with integers (-1, 0, 1, 2, etc.), it stores those as exact values. 1, in a computer, is always equal to 1.

But the same cannot be said for non-integer numbers (e.g., 2.5, 1.233, etc.). Numbers that are not integers are stored in as a data type called a floating point number, or float for short. These numbers are actually represented in memory as very clever approximations of the numbers we see using a format that allows them to store both tiny numbers 0.0000000024 and gigantic numbers 1,000,000,000,000,000,000,000 using the same amount of space of memory (64 bits, or 64 1s and 0s.).

But because these numbers are only approximations, occassionally weird things happen. For example, if you ask a computer whether 0.1 + 0.1 + 0.1 == 0.3, the computer will say that those are different:

0.1 + 0.1 + 0.1 == 0.3

False

While in other similar situations, you get the expected result:

0.1 + 0.1 == 0.2

True

0.11 + 0.11 + 0.11 == 0.33

True

(Don’t worry — we’ll explore in detail why this happens in a couple weeks.)

So when comparing floats for equality — like the distance between a Point and two other Points — we often need to use a tool that understands how these approximations work. In the Python standard library, this is the isclose() function in the math library:

import math

math.isclose(0.1 + 0.1 + 0.1, 0.3)

True

So when writing your algorithm, please use the math.isclose function instead of == when trying to determine if two distances are the same.

Scaffolding#

As usual, we have provided some code to help you get started testing below.


from point import Point


def closestPoint(s, p):
    return set()

if __name__ == "__main__":

    def test(s, p):
        ans = closestPoint(s, p)
        # We'll turn the set into a sorted list before
        # we print it to avoid any issues with what order things
        # are in
        sorted_ans = sorted(ans, key=lambda p: (p.x, p.y))
        print(sorted_ans)
        pass

    p1 = Point()
    p2 = Point(3, 4)
    p3 = Point(-3, 4)
    p4 = Point(3, -4)
    p5 = Point(1, 9)
    p6 = Point(8, 2)
    p7 = Point(-2, -5)
    p8 = Point(-6, 8)
    points = [p1, p2, p3, p4, p5, p6, p7, p8]

    # Creates different subsets of these points
    # to test
    for i in range(len(points)):
        s = set(points[:i]).union(set(points[i + 1 :]))
        test(s, points[i])

    # check that empty set gives empty set
    test({}, p1)

    # if the target point is in the list, we should get that point itself
    test(set(points), p5)

Expected Output#

This should give the output:


[Point(-3, 4), Point(3, -4), Point(3, 4)]
[Point(0, 0)]
[Point(-6, 8), Point(0, 0)]
[Point(0, 0)]
[Point(3, 4)]
[Point(3, 4)]
[Point(3, -4)]
[Point(-3, 4)]
[]
[Point(1, 9)]

Extension 2: Intersects Method#

A common operation in geospatial analysis is to take a circle and a collection of points (say, a list of points) and find only the subset of points that intersect (i.e., lie within) the circle.

Write a method for your Circle class that takes a list of Point objects and returns only those Point objects that are inside the Circle.

Extension-extension a: Intersect Function#

If you want to do something even more sophisticated, write a function (so not something inside the Circle class) that takes a list of Circle objects and a list of Point objects and returns all of the points that intersect at least one of the Circles.

Extension-extension 2b: Disjoint Function#

Add an argument to your intersect function. If the user passes "intersect", it does what we described in 2a. If the user passes "dijoint", then it returns all the points that don’t lie within any of the Circles.

Contents