Karachi-Navigator

Karachi-Navigator is a standalone, high-performance navigation engine designed specifically for Karachi’s road network. Unlike traditional mapping applications, this engine operates entirely offline without reliance on external APIs like Google Maps or Mapbox. It utilizes a custom-built geographic dataset and graph-based pathfinding to provide accurate routing and turn-by-turn instructions.

The system creates a graph based on a custom GeoJSON dataset and utilizes Dijkstra's Algorithm to traverse the network and calculate paths.

---

🚀 Getting Started

Follow these steps to set up the project on your local machine:

1. Fork, Clone and Install Dependencies

• It is recommended to use a virtual environment:

pip install -r requirements.txt

2. Run the Application

• Launch the Server:

python main.py

• The engine will initialize, build the road network from your data files, and start a local server at http://127.0.0.1:5000.

---

🛠️ Architecture

The repository consists of two core components:

1. The Navigation Engine (PathFinder.py)

This is the "brain" of the project. It handles:

• Data Parsing: Reads road geometries from GeoJSON and statistical data (speed, distance) from CSV.
• Graph Construction: Uses NetworkX to create a MultiGraph where intersections are nodes and roads are edges.
• Spatial Analysis: Uses Shapely for point-in-polygon checks to identify Karachi neighborhoods.
• Geometry Math: Implements Haversine formulas for distance and bearing calculations to generate navigation instructions.

2. The Web Server (main.py)

A FastAPI wrapper that exposes the engine to the web:

• POST /calculate_route: Accepts start and end coordinates and returns a JSON response containing the path, time, and instructions.
• Static Hosting: Serves the frontend interface directly from the /static directory.

---

⚙️ Data Structure

The engine requires two primary data files located in the data/ directory:

1. map.geojson: Contains the LineString geometries for Karachi's roads and Polygon shapes for various areas.
2. heuristic.csv: Contains statistical data for each road.

---

🗺️ Pathfinding Logic

The engine utilizes Dijkstra's Algorithm to find the most efficient path. When a request is made:

1. Snapping: The engine finds the closest graph nodes to the provided latitude/longitude.
2. Weighting: It calculates the shortest path based on the chosen weight, such as travel_time or distance.
3. Instruction Generation: It iterates through the path segments, detecting road name changes to generate "Turn left onto..." or "Travel along..." instructions.