How to represent line segments in kd-tree

Question 1

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.

Question 2

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.