The algorithm starts on page 25 of the book (book page, not pdf page)
I am currently trying to implement the function HandleEventPoint(p) (page 26)
and I am stuck at 2.
How would one find the adjacent segments in the AVL tree (T) (Adjacent to point p) without iterating through the whole AVL tree? I can only search a segment in the avl tree with a segment (a start and an endpoint) to then find it’s adjacent segments. I can’t search a segment with only one point (p). It would not be enough information to search in the tree.
Here is my class “Segment” which is what is stored in the avl tree (T):
public class Segment : IComparable<Segment>
{
/// <summary>
/// Startpoint of the line segment in 2D space
/// </summary>
private Vector2 startPoint;
/// <summary>
/// Endpoint of the line segment in 2D space
/// </summary>
private Vector2 endPoint;
public Vector2 GetStartPoint()
{
return this.startPoint;
}
public Vector2 GetEndPoint()
{
return this.endPoint;
}
/// <summary>
/// Initializes the Segment
/// </summary>
/// <param name="startpoint">Startpoint of the line segment in 2D space</param>
/// <param name="endpoint">Endpoint of the line segment in 2D space</param>
public Segment(Vector2 startpoint, Vector2 endpoint)
{
startPoint = startpoint;
endPoint = endpoint;
}
public static bool operator <(Segment p, Segment q)
{
// p comes before q if y coordinate of p is bigger than y coordinate of q
return (p.startPoint.x <= q.startPoint.x);
}
public static bool operator >(Segment p, Segment q)
{
return (p.startPoint.x > q.startPoint.x);
}
public static bool operator ==(Segment p, Segment q)
{
return (p.startPoint.x == q.startPoint.x);
}
public static bool operator !=(Segment p, Segment q)
{
return (p.startPoint.x != q.startPoint.x);
}
public override string ToString()
{
return "(Startpoint: {" + startPoint.x + "}) | Endpoint: {" + endPoint.x + "})";
}
public int CompareTo(Segment other)
{
if (this == other) //If both are fancy (Or both are not fancy, return 0 as they are equal)
{
return 0;
}
else if (this < other) //Otherwise if A is fancy (And therefore B is not), then return -1
{
return -1;
}
else if (this > other) //Otherwise it must be that B is fancy (And A is not), so return 1
{
return 1;
}
else
{
throw new System.InvalidOperationException("Two segments have been compared. For some reason, they weren't equal or of higher or lower priority.");
}
}
}
You’re better off using the exact same case and qualifying instance fields with this.startPoint = startPoint - having a single uppercase value as your point of difference makes me feel like I’m climbing without a spotter.
As for the algorithm, the whole point of tree data structures is that you shouldn’t need to iterate through every branch and leaf, they should quickly converge to the point of interest. Your first iteration should eliminate approximately half the nodes, the next step eliminates about half the remaining nodes etc etc and you converge after only about 4/5 iterations in the loop depending on how big the data set is.
As far as the constructor goes: I usually use _ to distinct paramters from the variables. Looks like a typo. But thank you for mentioning.
I know that binary search trees allow for “binary search” and thus have log(n) complexity. But the question was more regarding finding C(p). Meaning the set of lines that go through point p. The problem is that I store segments and not points in the tree: Meaning during each exploration of a segment I will have to check whether the point lies within the segment, which would be too slow. What do you think?
There has to be some kind of way to use segments as the elements but still get the log(n) complexity when searching since the books explicitly mentions that the tree stores segments and not points.
Better answered late then never for posterity I guess.
First of all, it might be slightly different depending on whether you choose to store the segments in the leaves (as in the book) or in the entire tree. In my implementation I stored them in the entire tree (because I am a rebel and I like to save space when I can ^^)
But in principle, when traversing the tree, you first check if p is the lower point of the segment. If yes, you add it to the lower segments list.
Then you check if p is strictly left or right of a segment. Remember, the order of the segments represents the order of the segments on the sweep line. That means, that if p is completely left of the segment, we only have to search the left subtree, as all other segments in the right subtree will be strictly right of p, and can therefore not intersect with it.
With completely left or right, I mean that p.x is smaller or bigger than the x-coordinates of both the start- and endpoint of the line segment.
And the ordering of the tree is still valid when searching like this for p, because it could not have changed since the last event point (it only changes after reinserting the segments again with the new Y-value of the sweep line)
If p is not left or right of the segments, we have to do two things:
First (only if p is not the lower endpoint of the segment), we check if p is on the segment (be careful with horizontal ones). If true, add it to the inner segments list (this is an O(1)-operation)
Second, we traverse the tree in both directions, left and right (if the nodes exist). This is because there still might be other lines “inside” (i.e. between the x-axis bounds) the current segment.
And that is basically it. I’m not certain if that is the best way to traverse it, but it is certainly one way.