Summary of Algorithms, Data Structures, and Numerical Methods

Algorithms, Data Structures, and Numerical Methods Explained

SummaryKnowledge testFlashcardsPodcastMindmap

Introduction

Photography is not just about pointing a camera and pressing a button; it is about planning, location scouting, time management, and making design choices that maximize impact. In this case study we examine Elisa, a student who aims to maximize monthly "likes" by photographing at various park locations under constraints of travel, time, and rules about where she can shoot. This material breaks the problem into data representation, location evaluation, pathfinding, rule verification, and overall optimization — all useful skills for practical photography planning and location-based creative work.

Definition: A candidate shooting location is a point in the park that is at least 100 m from any road and is distinct from other candidate locations by more than 50 m.

Part 1 — Data structures and candidate locations

Describe clear structures to represent the map and derived shooting points.

Map primitives

  • Polygon features for: roads, water, overgrown parts, and regions (each region stores a "likes" value per shooting there). Represent these as standard vector polygons (ordered vertex lists) with attributes.
  • Park gates: a set of points marking possible entry/exit gates.

Suggested data structures (in pseudocode):

  • RoadPolygons: List<Polygon>
  • WaterPolygons: List<Polygon>
  • OvergrownPolygons: List<Polygon>
  • RegionPolygons: List<Tuple<Polygon, likesValue>>
  • Gates: List<Point>

Spatial index: Build an R-tree (or quadtree) over all polygon bounding boxes to speed up geometric queries.

Candidate location generation

  • Rasterize or sample the park interior at a resolution appropriate to the 50 m uniqueness threshold (for example sample grid with spacing $25,\mathrm{m}$) and keep sample points that lie inside the park but outside roads and inside allowed areas.
  • Alternatively, compute the medial axis / polygon offset: take the complement of road buffers of radius $100,\mathrm{m}$ and intersect with park area. Then extract representative points (centroids of connected components or regular samples) spaced more than $50,\mathrm{m}$ apart.

Representation for each candidate location M:

  • Point: $M=(x,y)$
  • Region: pointer to RegionPolygon that contains M (if any)
  • LikesPotential: numeric value from region
  • Flags: isOvergrownNearby (boolean), isInWater (boolean), distanceToNearestRoad (float)

Why these choices

  • R-tree gives $O(\log n)$ search for intersecting polygons.
  • Sampling with spacing less than half the minimum uniqueness radius ensures possible distinct locations are represented.

Part 2 — Expected likes for a location M

We need a function that returns expected likes from shooting at M.

Algorithm outline:

  1. Determine the region that contains M using point-in-polygon tests via spatial index.
  2. BaseLikes $= L_{region}$ (provided attribute for that region).
  3. Apply modifiers:
    • If M is in/near overgrown parts, increase by a factor $f_{overgrown}>1$ (e.g. $1.2$) because exotic areas give more likes.
    • If M is adjacent to water or unique features, apply other modifiers $f_{water}, f_{unique}$.
  4. Final expected likes:

$$Likes(M) = L_{region} \cdot f_{overgrown} \cdot f_{water} \cdot f_{other}$$

Practical notes:

  • Use a small deterministic set of modifiers and cap values to avoid runaway estimates.
  • If no region contains M, treat $L_{region}=0$.

Part 3 — Shortest path from gate A to M and back to gate B

We must compute shortest travel time path considering different speeds on roads, off-road, overgrown, and swimming across water with changing time costs.

Modeling:

  • Build a weighted graph over the continuous map by creating a navigation mesh (navmesh) or visibility graph: nodes are polygon vertices, gate points, candidate points, plus intersection points between polygon boundaries. Edges connect walkable straight-line segments that do not cross impassable areas; each edge stores length and terrain type.
  • Edge travel time is computed from length and terrain speed. If an ed
Zaregistruj se pro celé shrnutí
FlashcardsKnowledge testSummaryPodcastMindmap
Start for free

Already have an account? Sign in

Park Photo Planning

Klíčové pojmy: Represent park features as polygons and use an R-tree spatial index, Generate candidate points by offsetting roads by 100 m or grid sampling with spacing <50 m, Compute expected likes as region base times modifiers for overgrown/water features, Model movement as a weighted graph with edge times based on terrain speeds, Use Dijkstra or A* to compute shortest-time paths and round-trips, Check rule 3 via distance-to-road >= 100 m (buffer or distance query), Ensure rule 4 by enforcing minimum 50 m separation using spatial queries or clustering, Precompute round-trip times for candidates and gates, then select top locations per available days, Use greedy ratio R(M)/C(M) or choose top rewards for one-location-per-day schedule, Complexities: preprocessing dominated by sampling and graph shortest-path runs; memory by graph and candidate storage

## Introduction Photography is not just about pointing a camera and pressing a button; it is about planning, location scouting, time management, and making design choices that maximize impact. In this case study we examine Elisa, a student who aims to maximize monthly "likes" by photographing at various park locations under constraints of travel, time, and rules about where she can shoot. This material breaks the problem into data representation, location evaluation, pathfinding, rule verification, and overall optimization — all useful skills for practical photography planning and location-based creative work. > Definition: A candidate shooting location is a point in the park that is at least 100 m from any road and is distinct from other candidate locations by more than 50 m. ## Part 1 — Data structures and candidate locations Describe clear structures to represent the map and derived shooting points. ### Map primitives - Polygon features for: roads, water, overgrown parts, and regions (each region stores a "likes" value per shooting there). Represent these as standard vector polygons (ordered vertex lists) with attributes. - Park gates: a set of points marking possible entry/exit gates. Suggested data structures (in pseudocode): - RoadPolygons: List<Polygon> - WaterPolygons: List<Polygon> - OvergrownPolygons: List<Polygon> - RegionPolygons: List<Tuple<Polygon, likesValue>> - Gates: List<Point> Spatial index: Build an R-tree (or quadtree) over all polygon bounding boxes to speed up geometric queries. ### Candidate location generation - Rasterize or sample the park interior at a resolution appropriate to the 50 m uniqueness threshold (for example sample grid with spacing $25\,\mathrm{m}$) and keep sample points that lie inside the park but outside roads and inside allowed areas. - Alternatively, compute the medial axis / polygon offset: take the complement of road buffers of radius $100\,\mathrm{m}$ and intersect with park area. Then extract representative points (centroids of connected components or regular samples) spaced more than $50\,\mathrm{m}$ apart. Representation for each candidate location M: - Point: $M=(x,y)$ - Region: pointer to RegionPolygon that contains M (if any) - LikesPotential: numeric value from region - Flags: isOvergrownNearby (boolean), isInWater (boolean), distanceToNearestRoad (float) ### Why these choices - R-tree gives $O(\log n)$ search for intersecting polygons. - Sampling with spacing less than half the minimum uniqueness radius ensures possible distinct locations are represented. ## Part 2 — Expected likes for a location M We need a function that returns expected likes from shooting at M. Algorithm outline: 1. Determine the region that contains M using point-in-polygon tests via spatial index. 2. BaseLikes $= L_{region}$ (provided attribute for that region). 3. Apply modifiers: - If M is in/near overgrown parts, increase by a factor $f_{overgrown}>1$ (e.g. $1.2$) because exotic areas give more likes. - If M is adjacent to water or unique features, apply other modifiers $f_{water}, f_{unique}$. 4. Final expected likes: $$Likes(M) = L_{region} \cdot f_{overgrown} \cdot f_{water} \cdot f_{other}$$ Practical notes: - Use a small deterministic set of modifiers and cap values to avoid runaway estimates. - If no region contains M, treat $L_{region}=0$. ## Part 3 — Shortest path from gate A to M and back to gate B We must compute shortest travel time path considering different speeds on roads, off-road, overgrown, and swimming across water with changing time costs. Modeling: - Build a weighted graph over the continuous map by creating a navigation mesh (navmesh) or visibility graph: nodes are polygon vertices, gate points, candidate points, plus intersection points between polygon boundaries. Edges connect walkable straight-line segments that do not cross impassable areas; each edge stores length and terrain type. - Edge travel time is computed from length and terrain speed. If an ed