We might have heard about Octrees a few times. It is a tree data structure that is used for the partition of three-dimensional space. What most of us don’t know is that octrees also have a two-dimensional analog called Quadtrees. Where octrees had eight children for each node, quadtrees limits to four. A two-dimensional space is repeatedly divided into four quadrants where each of which acts as a node with spatial information. The longitude and latitude are represented as cartesian coordinates (x, y), and search the points efficiently.
When we already have latitudes and longitudes, why do we need quadtrees?
This is a question many people have on their minds. Let’s see what’s the difference when we use quadtrees over longitude and latitude.
While using coordinates of latitude and longitude, we need to use Euclidean distance to calculate close location points. However, when there are large data sets, it shows CPU-intensive nature. This makes the use of coordinates in the real-time system not scalable.
Geohashing also helps us save extra computational operations because it only divides a node after a certain threshold. In addition, with the use of some mapping algorithms like the Hilbert Curve, the range query performance is also improved.
Types of Quadtrees
The types of quadtrees depend on the data that needs to be represented like areas, points, lines, curves, etc. Some of the most common quadtrees types are listed below: -
- Edge Quadtrees
- Point Quadtrees
- Point-region (PR) Quadtrees
- Compressed Quadtrees
- Polygonal Map (PM) Quadtrees
Use Cases of Quadtrees
Let’s view some of the use cases of quadtrees.
- Spatial Indexing
- Range Queries
- InDriver, Pathao, etc. (location-based services)
- Mesh Generation
- Computer Graphics
- Sparse Data Storage
- Image representation, processing, and compression
pragyaasapkota
/
System-Design-Concepts
Though the concepts of system design might be tricky, let's see them individually to their core concepts and have a better understanding.
System Design
Systems design is the process of defining elements of a system like modules, architecture, components and their interfaces and data for a system based on the specified requirements.
This is a index for the concepts of system.
If you wish to open these in a new tab, Press CTRL+click
| S.N. | Table of Content |
|---|---|
| 1. | Caching |
| 2. | Network Protocols |
| 3. | Storage: The Underrated Topic |
| 4. | Latency and Throughput |
| 5. | System Availability |
| 6. | Leader Election |
| 7. | Proxies |
| 8. | Load Balancing |
| 9. | Endpoint Protection |
| 10. | HTTPS: Is it better than HTTP? |
| 11. | Polling and Streaming |
| 12. | Long Polling |
| 13. | Hashing |
| 14. | CAP Theorem |
| 15. | PACELC Theorem |
| 16. | Messaging and Pub-Sub |
| 17. | Database |
| 18. | Logging, Monitoring, and Alerting |
| 19. | Distributed System |
| 20. | Scaling |
| 21. | Event Driven Architecture (EDA) |
| 22. | CQRS |
| 23. | Message Queue |
| 24. | Architectural Patterns |
| 25. | Enterprise Service Bus (ESB) |
| 26. | SLA, SLO, and SLI |
| 27. | Heartbeat |
I hope this article was helpful to you.
Please don’t forget to follow me!!!
Any kind of feedback or comment is welcome!!!
Thank you for your time and support!!!!
Keep Reading!! Keep Learning!!!
Top comments (0)