问题描述:

I have stored a set of Points in a Quadtree. Once the quadtree has been created with the points, I then add all the edges to the quadtree such that each edge gets stored in ALL the leaf nodes that it crosses, begins or ends at.

Now, I have a point, say A, and I need to find the closest edge to it. In my current Algorithm, I recurse to the leaf node that contains this Point A and find the distances between A and all line segments *contained by this leaf node.*

Now this may look like the right solution but it isn't as I have to compare edges that are there in adjacent nodes as well to be able to give an accurate answer.

Now my questions are

**a)How do I go about extracting the closest edges?**

**b)Should I just compare all edges contained in the parent(to the point of interest) node?**

*(But I know for a fact that putting a hard limit on the number of levels one must go up to find the nearest edge is incorrect based on intuition)*

Every node on the quad-tree represents a cube in space (where some sides may be at infinitum) and you can calculate the minimum distance between that cube and the target point A. Note that the distance is 0 for cubes containing A.

Starting from the root node you have to calculate the distance for every of its child cubes (nodes) to A and insert it into a min-heap.

Iteratively, you get the nearest cube at the top of heap and repeat the process. When you reach some leaf node, you just search for the nearest edge to A inside it using brute force.

Once the distance of the cube at top of the heap is greater than the distance of the nearest edge found so far, you can stop the search.

**Update**: BTW, this is actually the general approach for searching for anything using a quad-tree or a kd-tree or probably most spatial structures.

You can try a voronoi diagram and look for edges inside the voronoi cell only.

您可能感兴趣的文章：

- How to create 2 (or more) dimentional array in python
- ios - How to add an extra POST parameter?
- android - java.lang.UnsatisfiedLinkError: Native method not found: org.webrtc.PeerConnectionFactory.initializeFieldTrials:(Ljava/lang/String;)V
- python - Sum of elements stored inside a tuple
- python - duplicity-backup setup for AWS S3 Frankfurt buckets
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial