15,907,906 members

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):

**What I have tried:**

Using an avl tree with segments as elements

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."); } } }

Using an avl tree with segments as elements

Comments

OriginalGriff
13-Feb-22 11:04am

Link DELETED. Software piracy is not permitted on this site, and that book is not in the public domain, it is a full-price item and PDF copies are stolen.

[no name]
13-Feb-22 11:20am

My fault!

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900