Surveying and mapping with photogrammetry in Drone Programming - Time & Space Complexity

Time Complexity: Surveying and mapping with photogrammetry

O(n x m)

Understanding Time Complexity

When using drones for surveying and mapping with photogrammetry, we want to know how the time to process images grows as we collect more data.

We ask: How does the work increase when we add more photos to map?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function processPhotos(photoList) {
  let mappedPoints = []
  for (let photo of photoList) {
    let points = extractPoints(photo)
    for (let point of points) {
      mappedPoints.push(transformPoint(point))
    }
  }
  return mappedPoints
}

This code takes a list of photos, extracts points from each photo, transforms them, and collects all mapped points.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over photos and points inside each photo.
• How many times: Outer loop runs once per photo; inner loop runs once per point in each photo.

How Execution Grows With Input

As the number of photos increases, and the number of points per photo stays about the same, the total work grows roughly in proportion to the number of photos times points per photo.

Input Size (photos)	Approx. Operations
10	10 x points per photo
100	100 x points per photo
1000	1000 x points per photo

Pattern observation: The total operations grow linearly with the number of photos, assuming points per photo stay similar.

Final Time Complexity

Time Complexity: O(n x m)

This means the time grows in proportion to the number of photos (n) times the average number of points per photo (m).

Common Mistake

[X] Wrong: "The time only depends on the number of photos, not the points inside them."

[OK] Correct: Each photo has many points to process, so ignoring points misses the real work inside the inner loop.

Interview Connect

Understanding how nested loops affect time helps you explain how data size impacts drone mapping tasks, a useful skill in real projects.

Self-Check

"What if the number of points per photo grows as we use higher resolution images? How would the time complexity change?"

Practice

1. What is the main purpose of using photogrammetry in drone surveying?

easy

A. To create maps and 3D models from overlapping photos

B. To control the drone's battery life

C. To improve the drone's flight speed

D. To reduce the number of photos taken

Solution

1. Step 1: Understand photogrammetry basics

   Photogrammetry uses many overlapping photos to build maps and 3D models.

2. Step 2: Identify the main goal in drone surveying

   The goal is to create accurate maps and 3D models from the photos taken by the drone.

3. Final Answer:

   To create maps and 3D models from overlapping photos -> Option A

4. Quick Check:

   Photogrammetry = maps and 3D models [OK]

Hint: Photogrammetry means building maps from photos [OK]

Common Mistakes:

• Confusing photogrammetry with drone battery management
• Thinking photogrammetry speeds up flight
• Assuming photogrammetry reduces photo count

2. Which of the following is the correct syntax to define a flight path list in Python for drone photogrammetry?

easy

A. flight_path = {"point1", "point2", "point3"}

B. flight_path = ("point1", "point2", "point3")

C. flight_path = ["point1", "point2", "point3"]

D. flight_path = "point1", "point2", "point3"

Solution

1. Step 1: Identify list syntax in Python

   Lists use square brackets [] with items separated by commas.

2. Step 2: Check each option

   flight_path = ["point1", "point2", "point3"] uses square brackets and quotes correctly for strings.

3. Final Answer:

   flight_path = ["point1", "point2", "point3"] -> Option C

4. Quick Check:

   List syntax = square brackets [OK]

Hint: Lists use square brackets [] in Python [OK]

Common Mistakes:

• Using parentheses instead of square brackets for lists
• Using curly braces which create sets, not lists
• Leaving out brackets and just separating by commas

3. What will be the output of this Python code snippet used in photogrammetry data processing?

photos = ["img1.jpg", "img2.jpg", "img3.jpg"]
processed = [photo.replace('.jpg', '.tif') for photo in photos]
print(processed)

medium

A. ["img1.tif", "img2.tif", "img3.tif"]

B. ["img1.jpg", "img2.jpg", "img3.jpg"]

C. ["img1.tif.jpg", "img2.tif.jpg", "img3.tif.jpg"]

D. SyntaxError

Solution

1. Step 1: Understand list comprehension with string replace

   Each photo filename has '.jpg' replaced by '.tif'.

2. Step 2: Apply replace to each item

   "img1.jpg" becomes "img1.tif", similarly for others.

3. Final Answer:

   ["img1.tif", "img2.tif", "img3.tif"] -> Option A

4. Quick Check:

   Replace '.jpg' with '.tif' = changed list [OK]

Hint: String replace in list comprehension changes extensions [OK]

Common Mistakes:

• Expecting original list without changes
• Thinking replace adds text instead of replacing
• Confusing syntax causing errors

4. Identify the error in this Python code snippet for planning drone photo overlap:

overlap = 0.7
if overlap > 1:
    print("Overlap too high")
else
    print("Overlap acceptable")

medium

A. Incorrect comparison operator in if statement

B. Missing colon after else statement

C. Variable overlap should be an integer

D. Print statements must be outside if-else

Solution

1. Step 1: Check syntax of if-else statements

   Python requires a colon ':' after else keyword.

2. Step 2: Identify missing colon

   Code has 'else' without a colon, causing syntax error.

3. Final Answer:

   Missing colon after else statement -> Option B

4. Quick Check:

   else: needs colon [OK]

Hint: Always put colon after else in Python [OK]

Common Mistakes:

• Forgetting colon after else
• Thinking overlap must be integer
• Misreading comparison operator

5. You want to generate a dictionary mapping photo filenames to their GPS coordinates after a drone flight. Which Python code correctly creates this dictionary from two lists: photos = ["img1.jpg", "img2.jpg", "img3.jpg"] and coords = [(34.5, -117.2), (34.6, -117.3), (34.7, -117.4)]?

hard

A. photo_coords = [photos, coords]

B. photo_coords = dict(zip(coords, photos))

C. photo_coords = {coords[i]: photos[i] for i in range(len(coords))}

D. photo_coords = {photos[i]: coords[i] for i in range(len(photos))}

Solution

1. Step 1: Understand dictionary creation from two lists

   We want keys as photo names and values as coordinates.

2. Step 2: Check each option

   photo_coords = {photos[i]: coords[i] for i in range(len(photos))} uses dictionary comprehension with matching indexes correctly.

3. Final Answer:

   photo_coords = {photos[i]: coords[i] for i in range(len(photos))} -> Option D

4. Quick Check:

   Dict keys=photos, values=coords [OK]

Hint: Use dict comprehension with index to pair lists [OK]

Common Mistakes:

• Swapping keys and values in dict
• Using zip with wrong order
• Creating list instead of dict