lat <- seq(37, 41, length.out = 100) # This is a vector of 100 latitude values from 37 to 41
long <- seq(102, 109, length.out = 100) # 100 longitude values from 102 to 109
grid <- expand.grid(lat, long) # Generating all coordinate pairs
coord_matrix <- as.matrix(grid) # Converting into matrix
colnames(coord_matrix) <- c("lat", "long") # Naming the valuesAssignment 6 - Case Study
Due: Friday, July 25, 11:59pm
Instructions
- You need to submit the assignment as an HTML file, which should be created by rendering this qmd file, as demonstrated in the lectures. (2 points)
- Do not include your name anywhere in the assignment. Assignments are graded anonymously. (1 point)
- Write your code as organized as possible:
- There should not be any excessively long outputs (e.g. printing unnecessary results without good reason, printing something unnecessary inside a loop, etc.). There should not be any piece of unnecessary code (running or commented out) or unnecessary text. (1 point)
- The code should be commented and clearly written with intuitive variable names. (1 point) Also keep in mind that graders cannot give any partial credit to code they cannot follow.
Before you start, note that loops are NOT allowed for this entire assignment, except the last question (Question 6). Any solution with a loop will not receive any credit.
Air Quality Sensors in Colorado
For this assignment, you need to implement an algorithm that finds the locations to install 50 air quality sensors across Colorado. Air quality sensors are used to measure the amount of contaminants in the air and they are quite costly to install. Therefore, the best practice is to install a new sensor as far as possible from all the other sensors to efficiently cover the maximum air volume possible.
You will need to locate the first sensor in Denver. The second sensor should be at the location that is furthest away from the first sensor and still within Colorado borders. The third sensor should be at the location that is furthest away from both the first and second sensors and still within Colorado borders. All the remaining sensors should be located using the same logic.
To generalize the algorithm, each new sensor should be located at the spot (in Colorado) that is furthest away from all the previously located sensors. Starting with the first sensor in Denver, 50 sensors in total should be installed.
1) Creating a coordinate grid (10 points)
Information: Colorado’s coordinates are 37 °N to 41 °N and 102 °W to 109 °W.
The first step before implementing the algorithm is to create a coordinate grid that will contain the latitude and longitude values for many locations in Colorado. The fact that Colorado’s borders are rectangular makes this step easier.
You should create a vector that holds different latitude values (called lat) and another vector that holds different longitude values (called long). Both vectors should start and end at their corresponding border values given above, containing coordinate values in between, with a certain stepsize. The smaller your stepsize is, the larger the vectors will get, and the more accurate your geographical calculations will become. For this question, using 100 elements will be sufficient for both the latitude and the longitude vectors. Do not forget to name the vectors lat and long, respectively.
After creating the latitude and longitude vectors, expand them as a grid, which means that each value in the latitude vector should pair up with each value in the longitude vector. Do not forget to save your grid as a matrix.
After implementing the steps above, you should have a matrix that contains the coordinates for 10,000 locations across Colorado. Check the dimensions of your matrix and its values to see if you have created the correct data before moving to the next part. (You should have a 10,000x2 matrix.)
2) Installing the first sensor in Denver (15 points)
As described above, the first sensor will be installed in Denver, the largest city and the state capital of Colorado. The coordinates for the city center are (39.7392 °N, 104.9903 °W). Unfortunately, the resolution of your coordinate grid is not as small as the resolution of these given coordinates, so you need to find the coordinate pair that is the closest.
Find the location of the first sensor by calculating the coordinate pair in your grid that has the shortest Euclidean distance from the given city center coordinates of Denver. Save this location to first_sensor_coords.
Hints:
1) Note that Euclidean distance between two points in the x-y plane with coordinates \((x_1, y_1)\) and \((x_2, y_2)\) is \(\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\).
2) Both in this part and throughout this assignment, broadcasting and element-by-element operations will help you tremendously.
denver_lat <- 39.7392
denver_long <- 104.9903
distances <- sqrt((coord_matrix[,1] - denver_lat)^2 +
(coord_matrix[,2] - denver_long)^2) # the Euclidean distance from each grid point to Denver
closest_index <- which.min(distances) # Point that is the closest
first_sensor_coords <- coord_matrix[closest_index, ] # To extract the closest coordinate
print(first_sensor_coords) lat long
39.74747 104.96970 3) Installing the second sensor as far as possible from Denver (15 points)
For the second sensor, you should pick the location that is as far away as possible from the first sensor, whose location data should be stored in first_sensor_coords.
Find the location of the second sensor by calculating the coordinate pair in your grid that has the largest Euclidean distance from the coordinates of the first sensor. Save this location to second_sensor_coords.
Hint: The strategy is similar to the previous part.
first_lat <- first_sensor_coords[1]
first_long <- first_sensor_coords[2]
distances_to_first <- sqrt((coord_matrix[,1] - first_lat)^2 +
(coord_matrix[,2] - first_long)^2) # To find Euclidean distances from each point to the FIRST sensor
farthest_index <- which.max(distances_to_first)
second_sensor_coords <- coord_matrix[farthest_index, ]
print(second_sensor_coords) lat long
37 109 4) Visualizing your results so far (5 points)
Bind the vectors you found for the first and second sensors together to create a matrix that holds one coordinate pair in each row. Name this matrix air_sensor_coords.
Run the code below to check if your results make sense on a map. The coordinates of the two sensors will be marked as black dots on the map of Colorado. You do not need to change anything in the code; just run it.
(Make sure the colorado.png file is in the same folder as this qmd file and that you used the correct variable names in your code above: lat, long, and air_sensor_coords. Also, set the folder you are working in as your “working directory” from the gear icon at the top of the lower right window in RStudio.)
air_sensor_coords <- rbind(first_sensor_coords, second_sensor_coords) # Combining two coordinates into the matrix
library(png)
if(!require(png)){
install.packages("png",repos = "http://cran.us.r-project.org")
library(png)
}
library(png)
my_image <- readPNG("colorado.png")
plot(-long,lat, type='n', main="", xlab="longitude", ylab="latitude")
rasterImage(my_image, xleft=-109, xright=-102, ybottom=37, ytop=41)
points(-air_sensor_coords[,2],air_sensor_coords[,1],pch=16)
print(air_sensor_coords) lat long
first_sensor_coords 39.74747 104.9697
second_sensor_coords 37.00000 109.00005) Installing the third sensor as far as possible from the first two sensors (25 points)
For the third sensor, you should pick the location that is as far away as possible from the two previous sensors, whose location data should be stored in air_sensor_coords. Note that the implementation in this part can be generalized and applied for the remaining 47 sensors.
To locate the third sensor, you first need to find the minimum distance of all coordinate pairs in your grid (in coord_data) to the already-located sensors. For each coordinate pair, this can be implemented by finding its distance to all sensors (only first and second at this point) and then finding the minimum among these distances. This minimum distance tells you how far away that coordinate pair is from the sensor that is closest to it.
The coordinate pair that has the largest minimum distance is furthest away from the sensors and it should be the location of the third sensor. Find the location and put it in the third row of air_sensor_coords.
Hint: It would help to define a function that takes a coordinate pair as the input and returns its minimum distance from the sensors (using their coordinates in air_sensor_coords, which can be used in the function as a global variable).
Use the visualization code again to check if the results visually make sense.
min_dist_to_sensors <- function(coord_row) {
lat <- coord_row[1]
long <- coord_row[2]
distances <- sqrt((lat - air_sensor_coords[,1])^2 + (long - air_sensor_coords[,2])^2)
return(min(distances))
} # Calculating what would be the minimal distance to two sensors that are already there
coord_data <- cbind(lat, long)
min_distances <- apply(coord_data, 1, min_dist_to_sensors) # Applying the function to the whole grid
farthest_index <- which.max(min_distances)
third_sensor_coords <- coord_data[farthest_index, ]
air_sensor_coords <- air_sensor_coords[1:2, ] # So we don't get multiple third sectors when running multiple times
air_sensor_coords <- rbind(air_sensor_coords, third_sensor_coords)
print(third_sensor_coords) lat long
37 102 print(air_sensor_coords) lat long
first_sensor_coords 39.74747 104.9697
second_sensor_coords 37.00000 109.0000
third_sensor_coords 37.00000 102.0000library(png)
my_image <- readPNG("colorado.png")
plot(-long,lat, type='n', main="", xlab="longitude", ylab="latitude")
rasterImage(my_image, xleft=-109, xright=-102, ybottom=37, ytop=41)
points(-air_sensor_coords[,2],air_sensor_coords[,1],pch=16)
6) Installing the remaining 47 sensors (25 points)
Note: This is the only question in this assignment where you can use loops.
Lastly, you need to generalize the idea in the previous question to find the locations for the remaining 47 sensors.
To find the location for the next sensor, find the distance of each coordinate pair in the grid to each sensor that is already located. Then, find the minimum among these distances. Each coordinate pair should have a minimum distance value after this. The coordinate pair with the largest value among these minimum distance values is the location of the next sensor. Add that coordinate pair as a new row to air_sensor_coords.
To summarize the steps:
1) Suppose you have already found the locations of i sensors.
2) Find the minimum distance of each coordinate pair in coord_data to the i sensors, whose locations are in air_sensor_coords. For example, if a coordinate pair is at a distance of \(d_1\) from the first sensor, \(d_2\) from the second sensor,…, and \(d_i\) from the \(i^{th}\) sensor, then its minimum distance to the sensors will be \(min(d_1, d_2, ..., d_i\)).
3) Among the minimum distance values, the coordinate pair with the largest minimum distance value is the location of the \((i+1)^{th}\) sensor.
4) Add the coordinate pair for the \((i+1)^{th}\) sensor to air_sensor_coords.
After you locate all 50 sensors, your air_sensor_coords matrix should have 50 rows and 2 columns. Run the visualization code again to check your results. All the sensors are supposed to be spread out across the map of Colorado.
min_dist_to_sensors <- function(coord_row) {
lat <- coord_row[1]
long <- coord_row[2] # This finds out the minimum distance from a coordinate to existing sensors
distances <- sqrt((lat - air_sensor_coords[,1])^2 + (long - air_sensor_coords[,2])^2)
return(min(distances)) # To return the shortest distance to any one of the sensors
}
#Loop
for (i in 1:47) {
min_distances <- apply(coord_data, 1, min_dist_to_sensors)
farthest_index <- which.max(min_distances) #This finds the coordinate with the biggest minimum distance to existing sensors
next_sensor_coords <- coord_data[farthest_index, ]
air_sensor_coords <- rbind(air_sensor_coords, next_sensor_coords)
}
print(dim(air_sensor_coords))[1] 50 2head(air_sensor_coords, 3) lat long
first_sensor_coords 39.74747 104.9697
second_sensor_coords 37.00000 109.0000
third_sensor_coords 37.00000 102.0000tail(air_sensor_coords, 3) lat long
next_sensor_coords 37.20202 102.3535
next_sensor_coords 37.28283 102.4949
next_sensor_coords 37.32323 102.5657my_image <- readPNG("colorado.png")
plot(-long,lat, type='n', main="", xlab="longitude", ylab="latitude")
rasterImage(my_image, xleft=-109, xright=-102, ybottom=37, ytop=41)
points(-air_sensor_coords[,2],air_sensor_coords[,1],pch=16)