MemoLanes · TimRen01 · May 25, 2025 · May 25, 2025 · May 25, 2025 · May 30, 2025
diff --git a/app/journey_kernel/src/journey_bitmap.rs b/app/journey_kernel/src/journey_bitmap.rs
@@ -32,7 +32,21 @@ impl JourneyBitmap {
     //       - make sure we are using the consistent and correct one of `u64`/`i64`/`i32`.
     //       - better variable naming.
     //       - reduce code duplications.
+
     pub fn add_line(&mut self, start_lng: f64, start_lat: f64, end_lng: f64, end_lat: f64) {
+        self.add_line_with_change_callback(start_lng, start_lat, end_lng, end_lat, |_| {});
+    }
+
+    pub fn add_line_with_change_callback<F>(
+        &mut self,
+        start_lng: f64,
+        start_lat: f64,
+        end_lng: f64,
+        end_lat: f64,
+        mut tile_changed: F,
+    ) where
+        F: FnMut((u16, u16)),
+    {
         let (mut x0, y0) = utils::lng_lat_to_tile_x_y(
             start_lng,
             start_lat,
@@ -72,10 +86,8 @@ impl JourneyBitmap {
             loop {
                 // tile_x is not rounded, it may exceed the antimeridian
                 let (tile_x, tile_y) = (x >> ALL_OFFSET, y >> ALL_OFFSET);
-                let tile = self
-                    .tiles
-                    .entry(((tile_x % MAP_WIDTH) as u16, tile_y as u16))
-                    .or_default();
+                let tile_pos = ((tile_x % MAP_WIDTH) as u16, tile_y as u16);
+                let tile = self.tiles.entry(tile_pos).or_default();
                 (x, y, px) = tile.add_line(
                     x - (tile_x << ALL_OFFSET),
                     y - (tile_y << ALL_OFFSET),
@@ -86,6 +98,9 @@ impl JourneyBitmap {
                     true,
                     (dx < 0 && dy < 0) || (dx > 0 && dy > 0),
                 );
+                // TODO: We might want to check if the tile is actually changed
+                tile_changed(tile_pos);
+
                 x += tile_x << ALL_OFFSET;
                 y += tile_y << ALL_OFFSET;
 
@@ -105,10 +120,8 @@ impl JourneyBitmap {
             loop {
                 // tile_x is not rounded, it may exceed the antimeridian
                 let (tile_x, tile_y) = (x >> ALL_OFFSET, y >> ALL_OFFSET);
-                let tile = self
-                    .tiles
-                    .entry(((tile_x % MAP_WIDTH) as u16, tile_y as u16))
-                    .or_default();
+                let tile_pos = ((tile_x % MAP_WIDTH) as u16, tile_y as u16);
+                let tile = self.tiles.entry(tile_pos).or_default();
                 (x, y, py) = tile.add_line(
                     x - (tile_x << ALL_OFFSET),
                     y - (tile_y << ALL_OFFSET),
@@ -119,6 +132,9 @@ impl JourneyBitmap {
                     false,
                     (dx < 0 && dy < 0) || (dx > 0 && dy > 0),
                 );
+                // TODO: We might want to check if the tile is actually changed
+                tile_changed(tile_pos);
+
                 x += tile_x << ALL_OFFSET;
                 y += tile_y << ALL_OFFSET;
 

diff --git a/app/rust/benches/bench.rs b/app/rust/benches/bench.rs
@@ -1,5 +1,4 @@
 use criterion::{criterion_group, criterion_main, Criterion};
-
 use memolanes_core::{
     import_data, journey_area_utils, journey_bitmap::JourneyBitmap, merged_journey_builder,
 };
@@ -14,6 +13,7 @@ fn journey_area_calculation(c: &mut Criterion) {
         b.iter(|| {
             std::hint::black_box(journey_area_utils::compute_journey_bitmap_area(
                 &bitmap_import,
+                None,
             ))
         })
     });
@@ -31,10 +31,10 @@ fn journey_area_calculation(c: &mut Criterion) {
                 &mut journey_bitmap,
                 &journey_vector,
             );
-
             b.iter(|| {
                 std::hint::black_box(journey_area_utils::compute_journey_bitmap_area(
                     &journey_bitmap,
+                    None,
                 ))
             })
         },

diff --git a/app/rust/examples/server.rs b/app/rust/examples/server.rs
@@ -85,7 +85,7 @@ pub fn main() -> Result<(), Box<dyn std::error::Error>> {
                 let next_lng = lng + lng_step;
                 let next_lat = lat + rng.random_range(-lat_step..=lat_step);
                 let mut map_renderer = map_renderer_arc_clone.lock().unwrap();
-                map_renderer.update(|bitmap| {
+                map_renderer.update(|bitmap, _tile_cb| {
                     bitmap.add_line(lng, lat, next_lng, next_lat);
                 });
                 map_renderer.set_provisioned_camera_option(Some(CameraOption {

diff --git a/app/rust/src/api/api.rs b/app/rust/src/api/api.rs
@@ -261,12 +261,13 @@ pub fn on_location_update(
         match line_to_add {
             None => (),
             Some((start, end)) => {
-                map_renderer.update(|journey_bitmap| {
-                    journey_bitmap.add_line(
+                map_renderer.update(|journey_bitmap, tile_changed| {
+                    journey_bitmap.add_line_with_change_callback(
                         start.longitude,
                         start.latitude,
                         end.longitude,
                         end.latitude,
+                        tile_changed,
                     );
                 });
             }

diff --git a/app/rust/src/journey_area_utils.rs b/app/rust/src/journey_area_utils.rs
@@ -1,63 +1,75 @@
 use crate::journey_bitmap::{
-    JourneyBitmap, BITMAP_WIDTH, BITMAP_WIDTH_OFFSET, MAP_WIDTH_OFFSET, TILE_WIDTH,
+    JourneyBitmap, Tile, BITMAP_WIDTH, BITMAP_WIDTH_OFFSET, MAP_WIDTH_OFFSET, TILE_WIDTH,
     TILE_WIDTH_OFFSET,
 };
 use crate::utils;
-
+use std::collections::HashMap;
 const EARTH_RADIUS: f64 = 6371000.0; // unit: meter
 
+fn compute_one_tile(tile_pos: (u16, u16), tile: &Tile) -> f64 {
+    tile.blocks.iter().filter_map(|(block_pos, block)| {
+        let bit_count = block.count();
+        if bit_count > 0 {
+            // calculate center bit in each block for bit_unit_area
+            // Calculate the top-left coordinates of this bitmap point
+            let bitzoomed_x1: i32 = TILE_WIDTH as i32 * BITMAP_WIDTH as i32 * tile_pos.0 as i32
+            + BITMAP_WIDTH as i32 * block_pos.0 as i32
+            + (BITMAP_WIDTH/2) as i32;
+            let bitzoomed_y1: i32 = TILE_WIDTH as i32 * BITMAP_WIDTH as i32 * tile_pos.1 as i32
+            + BITMAP_WIDTH as i32 * block_pos.1 as i32
+            + (BITMAP_WIDTH/2) as i32;
+
+            // Bottom-right coordinates (add one bit length to each side)
+            let bitzoomed_x2 = bitzoomed_x1 + 1;
+            let bitzoomed_y2 = bitzoomed_y1 + 1;
+
+            // Convert these to latitude/longitude
+            let (lng1, lat1) = utils::tile_x_y_to_lng_lat(
+                bitzoomed_x1,
+                bitzoomed_y1,
+                (BITMAP_WIDTH_OFFSET + TILE_WIDTH_OFFSET + MAP_WIDTH_OFFSET) as i32,
+            );
+            let (lng2, lat2) = utils::tile_x_y_to_lng_lat(
+                bitzoomed_x2,
+                bitzoomed_y2,
+                (BITMAP_WIDTH_OFFSET + TILE_WIDTH_OFFSET + MAP_WIDTH_OFFSET) as i32,
+            );
+
+            /* formula derived from spherical geometry of Earth */
+            /* width=R⋅Δλ⋅cos(ϕ), where Δλ = λ2-λ1 is the difference of longitudes in radians, ϕ is the latitude in radians*/
+            let width_top = EARTH_RADIUS * (lng2 - lng1).abs().to_radians() * lat1.to_radians().cos();
+            let width_bottom = EARTH_RADIUS * (lng2 - lng1).abs().to_radians() * lat2.to_radians().cos();
+            let avg_width = (width_top + width_bottom) / 2.0;
+            /* height=R⋅Δφ, where Δφ = φ2-φ1 is the difference of latitudes in radians. */
+            let height = EARTH_RADIUS * (lat2 - lat1).abs().to_radians();
+
+            let bit_unit_area = avg_width * height;
+            Some(bit_unit_area * bit_count as f64)
+        } else {
+            None
+        }
+    }).sum()
+}
+
 // Result unit in m^2. This area calculating method by using center bit in a
 // block has better efficiency and accuracy compared to simple interation and other methods.
 // codes for different calculating methods can be found here:
 // https://github.com/TimRen01/TimRen01_repo/tree/compare_method_calculate_area_by_journey
-pub fn compute_journey_bitmap_area(journey_bitmap: &JourneyBitmap) -> u64 {
+pub fn compute_journey_bitmap_area(
+    journey_bitmap: &JourneyBitmap,
+    mut tile_update_map: Option<&mut HashMap<(u16, u16), f64>>,
+) -> u64 {
     let total_area: f64 = journey_bitmap
         .tiles
         .iter()
-        .flat_map(|(tile_pos, tile)| {
-            tile.blocks.iter().filter_map(move |(block_pos, block)| {
-                let bit_count = block.count();
-                if bit_count > 0 {
-                    // calculate center bit in each block for bit_unit_area
-                    // Calculate the top-left coordinates of this bitmap point
-                    let bitzoomed_x1: i32 = TILE_WIDTH as i32 * BITMAP_WIDTH as i32 * tile_pos.0 as i32
-                    + BITMAP_WIDTH as i32 * block_pos.0 as i32
-                    + (BITMAP_WIDTH/2) as i32;
-                    let bitzoomed_y1: i32 = TILE_WIDTH as i32 * BITMAP_WIDTH as i32 * tile_pos.1 as i32
-                    + BITMAP_WIDTH as i32 * block_pos.1 as i32
-                    + (BITMAP_WIDTH/2) as i32;
-
-                    // Bottom-right coordinates (add one bit length to each side)
-                    let bitzoomed_x2 = bitzoomed_x1 + 1;
-                    let bitzoomed_y2 = bitzoomed_y1 + 1;
-
-                    // Convert these to latitude/longitude
-                    let (lng1, lat1) = utils::tile_x_y_to_lng_lat(
-                        bitzoomed_x1,
-                        bitzoomed_y1,
-                        (BITMAP_WIDTH_OFFSET + TILE_WIDTH_OFFSET + MAP_WIDTH_OFFSET) as i32,
-                    );
-                    let (lng2, lat2) = utils::tile_x_y_to_lng_lat(
-                        bitzoomed_x2,
-                        bitzoomed_y2,
-                        (BITMAP_WIDTH_OFFSET + TILE_WIDTH_OFFSET + MAP_WIDTH_OFFSET) as i32,
-                    );
-
-                    /* formula derived from spherical geometry of Earth */
-                    /* width=R⋅Δλ⋅cos(ϕ), where Δλ = λ2-λ1 is the difference of longitudes in radians, ϕ is the latitude in radians*/
-                    let width_top = EARTH_RADIUS * (lng2 - lng1).abs().to_radians() * lat1.to_radians().cos();
-                    let width_bottom = EARTH_RADIUS * (lng2 - lng1).abs().to_radians() * lat2.to_radians().cos();
-                    let avg_width = (width_top + width_bottom) / 2.0;
-                    /* height=R⋅Δφ, where Δφ = φ2-φ1 is the difference of latitudes in radians. */
-                    let height = EARTH_RADIUS * (lat2 - lat1).abs().to_radians();
-
-                    let bit_unit_area = avg_width * height;
-                    Some(bit_unit_area * bit_count as f64)
-                }
-                else {
-                    None
-                }
-            })
+        .map(|(tile_pos, tile)| {
+            tile_update_map.as_mut().map_or_else(
+                || compute_one_tile(*tile_pos, tile),
+                |map| {
+                    *map.entry(*tile_pos)
+                        .or_insert_with(|| compute_one_tile(*tile_pos, tile))
+                },
+            )
         })
         .sum();
     // we don't have that much precision in the journey bitmap anyway

diff --git a/app/rust/src/renderer/map_renderer.rs b/app/rust/src/renderer/map_renderer.rs
@@ -1,10 +1,12 @@
 use crate::api::api::CameraOption;
 use crate::journey_area_utils;
 use crate::journey_bitmap::JourneyBitmap;
-
+use std::collections::HashMap;
 pub struct MapRenderer {
     journey_bitmap: JourneyBitmap,
     changed: bool,
+    /* for each tile of 512*512 tiles in a JourneyBitmap, use buffered area to record any update */
+    tile_area_cache: HashMap<(u16, u16), f64>,
     current_area: Option<u64>,
     // TODO: `provisioned_camera_option` should be moved out and passed to the
     // map separately.
@@ -16,6 +18,7 @@ impl MapRenderer {
         Self {
             journey_bitmap,
             changed: false,
+            tile_area_cache: HashMap::new(),
             current_area: None,
             provisioned_camera_option: None,
         }
@@ -31,11 +34,14 @@ impl MapRenderer {
 
     pub fn update<F>(&mut self, f: F)
     where
-        F: Fn(&mut JourneyBitmap),
+        F: Fn(&mut JourneyBitmap, &mut dyn FnMut((u16, u16))),
     {
-        f(&mut self.journey_bitmap);
+        let mut tile_changed = |tile_pos: (u16, u16)| {
+            self.tile_area_cache.remove(&tile_pos);
+        };
+        f(&mut self.journey_bitmap, &mut tile_changed);
         // TODO: we should improve the cache invalidation rule
-        self.reset();
+        self.changed = true;
     }
 
     pub fn replace(&mut self, journey_bitmap: JourneyBitmap) {
@@ -45,6 +51,7 @@ impl MapRenderer {
 
     pub fn reset(&mut self) {
         self.changed = true;
+        self.tile_area_cache.clear();
         self.current_area = None;
     }
 
@@ -68,14 +75,11 @@ impl MapRenderer {
     pub fn get_current_area(&mut self) -> u64 {
         // TODO: we can do something more efficient here, instead of traversing
         // the whole bitmap evey time it changes.
-        match self.current_area {
-            Some(area) => area,
-            None => {
-                let journey_bitmap = self.peek_latest_bitmap();
-                let area = journey_area_utils::compute_journey_bitmap_area(journey_bitmap);
-                self.current_area = Some(area);
-                area
-            }
-        }
+        let area = journey_area_utils::compute_journey_bitmap_area(
+            &self.journey_bitmap,
+            Some(&mut self.tile_area_cache),
+        );
+        self.current_area = Some(area);
+        area
     }
 }
diff --git a/app/rust/tests/journey_area_utils.rs b/app/rust/tests/journey_area_utils.rs
@@ -1,11 +1,70 @@
 pub mod test_utils;
+use memolanes_core::{import_data, journey_area_utils, journey_bitmap::JourneyBitmap, renderer::*};
+//use std::cell::RefCell;
 
-use memolanes_core::{import_data, journey_area_utils};
+const START_LNG: f64 = 151.1435370795134;
+const START_LAT: f64 = -33.793291910360125;
+const END_LNG: f64 = 132.1435370795134;
+const END_LAT: f64 = -55.793291910360125;
 
 #[test]
 fn test_compute_journey_bitmap_area() {
     let (bitmap_import, _warnings) =
         import_data::load_fow_sync_data("./tests/data/fow_1.zip").unwrap();
-    let calculated_area = journey_area_utils::compute_journey_bitmap_area(&bitmap_import);
+    let calculated_area = journey_area_utils::compute_journey_bitmap_area(&bitmap_import, None);
     assert_eq!(calculated_area, 3035670); // area unit: m^2
 }
+
+#[test]
+fn partial_update_use_cached_and_recompute_touched_tiles_only() {
+    let journey_bitmap = JourneyBitmap::new();
+    let mut map_renderer = MapRenderer::new(journey_bitmap);
+    //let touched = RefCell::new(Vec::<(u16, u16)>::new());
+    map_renderer.update(|bitmap, cb| {
+        bitmap.add_line_with_change_callback(START_LNG, START_LAT, END_LNG, END_LAT, cb)
+    });
+    let _ = map_renderer.get_current_area();
+
+    map_renderer.update(|bitmap, cb| {
+        bitmap.add_line_with_change_callback(START_LNG, END_LAT, END_LNG, START_LAT, cb)
+    });
+    let update_area = map_renderer.get_current_area();
+
+    //let tiles = touched.borrow();
+    //let count = tiles.len();
+    //println!("Touched {} tiles: {:?}", count, &*tiles);
+
+    //assert!(count > 0, "expected to touch at least one tile, got {}", count);
+
+    let mut full_journey_bitmap = JourneyBitmap::new();
+    full_journey_bitmap.add_line(START_LNG, START_LAT, END_LNG, END_LAT);
+    full_journey_bitmap.add_line(START_LNG, END_LAT, END_LNG, START_LAT);
+    let full_area = journey_area_utils::compute_journey_bitmap_area(&full_journey_bitmap, None);
+
+    println!("update_area = {}", update_area);
+    println!("full_area = {}", full_area);
+    assert_eq!(
+        update_area, full_area,
+        "updated area after partial-update must match a full compute"
+    );
+}
+
+#[test]
+fn validate_area_after_map_renderer_replace() {
+    let journey_bitmap = JourneyBitmap::new();
+    let mut map_renderer = MapRenderer::new(journey_bitmap);
+
+    map_renderer.update(|bitmap, _| {
+        bitmap.add_line(START_LNG, START_LAT, END_LNG, END_LAT);
+    });
+
+    assert!(map_renderer.get_current_area() > 0);
+
+    let (bitmap_import, _warnings) =
+        import_data::load_fow_sync_data("./tests/data/fow_1.zip").unwrap();
+
+    map_renderer.replace(bitmap_import.clone());
+
+    let calculated_area = journey_area_utils::compute_journey_bitmap_area(&bitmap_import, None);
+    assert_eq!(map_renderer.get_current_area(), calculated_area); // area unit: m^2
+}
diff --git a/app/rust/tests/journey_bitmap.rs b/app/rust/tests/journey_bitmap.rs
@@ -1,5 +1,4 @@
 pub mod test_utils;
-
 use memolanes_core::{
     import_data, journey_area_utils, journey_bitmap::JourneyBitmap, journey_data::JourneyData,
     journey_header::JourneyType, merged_journey_builder, renderer::MapRenderer,
@@ -230,7 +229,7 @@ fn draw_single_point() {
     journey_bitmap.add_line(120.0, 30.0, 120.0, 30.0);
 
     assert_eq!(
-        journey_area_utils::compute_journey_bitmap_area(&journey_bitmap),
+        journey_area_utils::compute_journey_bitmap_area(&journey_bitmap, None),
         68
     );
 }