4

I have huge number of line segments in 2D. I want to represent them all in kd-tree structure and then find near by line segments for a particular line segment. Any ideas on how to do this with kd-tree?

StevenWhite
  • 5,907
  • 3
  • 21
  • 46
niro
  • 947
  • 3
  • 13
  • 30
  • What exactly do you mean? (The query operation you want to implement) `find near by line segments for a particular line segment`... – leemes Jan 17 '13 at 10:14
  • 2
    @leemes: i will add a picture soon – niro Jan 17 '13 at 10:15
  • Are you sure that the "equidistant mark" (the thing around the bold line which should indicate the same distance) you have drawn is of that shape? Shouldn't it be a semi circle on both ends of the line? – leemes Jan 17 '13 at 10:23
  • @leemes: yes yes it is semi circle. – niro Jan 17 '13 at 10:26
  • It might be better to use a different spatial index for this task, specifically, an R-tree is designed for non-point data... – Darren Engwirda Jan 17 '13 at 10:31

2 Answers2

4

The segment should be in every kd-tree leaf that it intersects. That is, let's say a line segment is represented by a pair of points (p1, p2), you should store a reference to this line segment in the kd tree nodes. This line segment should be in every kd-tree node which it passes through, this part is different from when dealing with points, where each point is only stored within 1 kd tree node.

When splitting the kd tree node, you split on a horizontal or vertical line. The line segment is in the "left" subtree if at least one of the endpoints is in the left subtree. And similarly for the right subtree.

You should find nearby by doing something similar to a point query with the endpoints of the line segment. That is, look at all the kd-tree leaves near the query endpoints.

Then for the potential segments in those bins, you can do an exact length comparison by looking at the length of the perpendicular line from the query endpoint to the candidate segment, and vice versa (compare the candidate line endpoints to the query line).

The details of how to do this is answered here: Shortest distance between a point and a line segment. you should do 4 tests, the endpoints of one line to the other line, and vice versa, and take the minimum. Take care to ignore the distances of the cases where the point is projected to outside the line segment.

This works because lines don't curve, so the closest point between 2 lines must lie at one of the endpoints.

Community
  • 1
  • 1
yiding
  • 3,482
  • 18
  • 17
  • sorry, I couldnt get exactly what you mean. i am poor in kd-tree. how to represent line segment in kd-tree. should i convert them into points to represent in kdtree or? i mean what would be the inputs. (to be honest, if i follow standard library functions which designed for point data, then how can i use that lib-function for this case? can i use it or not? sorry for poor terminology – niro Jan 17 '13 at 10:25
  • sorry again. i am doubted how to represent line segment in kd-tree and i do not have any idea to do it. should i take only mid points? to find nearby lines or how can i represent line segments i.e. two ending points with one number... may be i am wrong.. any idea please – niro Jan 17 '13 at 11:08
  • I elaborated on some details. The metric for "nearby" may not be what you want, though. – yiding Jan 17 '13 at 19:01
  • thank you for the suggestions. if you could, please add some example to make this clear. – niro Jan 18 '13 at 13:58
0

You cannot implement kd-tree with segments. kd-tree is specially designed for k-vector space, and segments are not part of vector space. Idea is kd-tree use hyperplane to partition the kd-space, if you are not in a kd-vector space, that's not ideal.

However, what you need might be the Bounding Volume Hierarchy, https://en.wikipedia.org/wiki/Bounding_volume_hierarchy, a technique used for collision detection.

ctNGUYEN
  • 241
  • 2
  • 6