Im currently implementing the sweep line algorithm for line intersection in C#. Using this book: [DELETED]
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>
{
private Vector2 startPoint;
private Vector2 endPoint;
public Vector2 GetStartPoint()
{
return this.startPoint;
}
public Vector2 GetEndPoint()
{
return this.endPoint;
}
public Segment(Vector2 startpoint, Vector2 endpoint)
{
startPoint = startpoint;
endPoint = endpoint;
}
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 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)
{
return 0;
}
else if (this < other)
{
return -1;
}
else if (this > other)
{
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.");
}
}
}
What I have tried:
Using an avl tree with segments as elements