• Intersection of two segments
• Intersection of segment and triangle
• Point in polygon test
• Convex polygon intersection
• Intersection of a set of segments
• Non-convex polygon intersection

• We have already seen how to detect whether two segments intersect
  • But where do they intersect?
  • One way to compute is to solve two line equations
    • \(L_{ab} = L_{cd}\)
    • Two equation in two unknowns
    • But this is not very practical for some reasons

• Better way is to use parametric segment representations
• \(p(s) = a + sA\)

• Assume we have two line segments ab and cd on lines \(L_{ab}\) and \(L_{cd}\)
• The corresponding parametric representations are
  • \(p(s) = a + sA\), where \(A = b-a\)
  • \(q(t) = c + tC\), where \(C = d-c\)

Solving for equation

\(a+sA=c+tC\)

\(a_x+s(b_x-a_x) = c_x+t(d_x-c_x)\)

\(a_y+s(b_y-a_y) = c_y+t(d_y-c_y)\)

After some algebra:

\(s = [a_x(d_y - c_y) + c_x(a_y - d_y) + d_x(c_y - a_y)]/D\)

\(t = [a_x(c_y - b_y) + b_x(a_y - c_y) + c_x(b_y - a_y)]/D\)

\(D = a_x(d_y - c_y) + b_x(c_y - d_y) + d_x(b_y - a_y) + c_x(a_y - b_y)\)

• The return codes:

  • e: The segments collinearly overlap, sharing a point

  • v: An endpoint of one segment is on the other segment, but e doesn’t hold

  • 1: The segments intersect properly

  • 0: The segments do not intersect

• A helper for parallel segments

• Two helpers:

  • Assigndi(p,a): assign point a to point p

  • Between(a,b,c): check whether c is between a and b

• A very important computation that is used in many fields

  • Ray tracing in computer graphics

• Question: Let \(T(a,b,c)\) be a triangle and \(qr\) a line segment,

  • Does \(qr\) intersect \(T\)? If so, where?

• If \(qr\) and \(T\) are on the same plane, then this is trivial

  • Check each edge of the triangle for seg-seg-int

• Else,

  • Complicated

• We must first figure out whether the segment intersects the plane of the triangle

  • If not, then there is no intersection

  • If yes, then we will check whether the intersection point is within the triangle

• All points on a plane must satisfy the plane equation

\(\pi : Ax + By + Cz = D\)

• We represent a plane by four parameters: \((A,B,C,D)\)
• \(N=(A,B,C)\) is the vector normal of the plane
  • The normal vector is a vector perpendicular to the plane

• Plane equation:

\(\pi : (x, y, z) \cdot N = D\)

• Parametric segment representation

\(p(t) = q + t(r-q)\)

• Match two:

\([q+t(r-q)] \cdot N = D\)

\(q \cdot N + t(r-q)\cdot N = D\)

\(t = \frac{D - q \cdot N}{(r-q)\cdot N}\)

• Usually we are not given the plane equation
  • But we know the triangle vertices
  • From there we can compute the cross product to obtain the normal vector
  • Using the normal and a point on the plane (such as a triangle vertex) we compute the value of \(D\)

• ReadVertices: read the vertices into an array

• ReadFaces: read all triangles by reading three pointers for each

• From \(N = (b - a) \times (c - a)\):

• Remember \(t = \frac{D - q \cdot N}{(r-q)\cdot N}\)
• p: Segment lies wholly within the plane.
• q: The (first) q endpoint is on the plane (but not p).
• r: The (second) r endpoint is on the plane (but not p).
• 0: Segment lies strictly to one side of the plane.
• 1: Segment intersects the plane, and none of {p, q, r} hold.

• We now know where the segment intersects the plane of the triangle, if it does intersect it
• But how is this intersection point to be classified with respect to the triangle:
  • The point is inside the triangle
  • The point is outside the triangle
  • The point is on the boundary of the triangle
  • The point is on a vertex of the triangle

• We first look at a very mathematical approach
  • But implementation of this is not preferred
• The barycenter of an object is its center of gravity
• The barycentric coordinates of a point \(p\) with respect to a triangle \((a,b,c)\) are the coefficients \((\alpha, \beta, \gamma)\) in \(\alpha a + \beta b + \gamma c = p\)

• The barycentric coordinates define all the points in the plane of the triangle
  • If they are all in \([(0,1]\), and they sum up to 1, then the point \(p\) is on or inside the triangle

• We can compute these coefficients by solving 4 equations in 3 unknowns:
  • \(\alpha a_x + \beta b_x + \gamma c_x = p_x\)
  • \(\alpha a_y + \beta b_y + \gamma c_y = p_y\)
  • \(\alpha a_z + \beta b_z + \gamma c_z = p_z\)
  • \(\alpha + \beta + \gamma = 1\)
• However, this requires a lot of precision
• We will solve the classification problem in an alternative approach

• Given a fixed polygon \(P\) and a query point \(q\), is \(q \in P\)?

• If the polygon is convex: trivial

  • Test LeftOn with each edge

• Else, we have two alterative methods

  • Ray crossings

  • Winding numbers

• Nice mathematical approach

• Very bad in practice

• Imagine a car is moving on a polygonal road and you are standing on a point, there is a rope between you and the car

  • If you are inside the polygonal road, once the car completes a round, the rope will be wound around your body for \(2\pi\) radians

  • If you are outside the polygonal road, then at the end the rope will not be wound around you at all

• Too many floating point and trigonometric computations

• Shoot a ray from \(q\) and count the crossing with the boundary of \(P\)

  • An even number of crossings mean \(q\) is outside \(P\)

  • An odd number of crossings mean \(q\) is inside \(P\)

• Many degenerate cases exist, so be careful!

• The intersection of two arbitrary polygons of \(n\) and \(m\) vertices can have quadratic complexity

  

• However, the intersection of two convex polygons has only linear complexity \(O(m+n)\)

• Assume P and Q are two convex polygons, with all edges being directed in counter clockwise orientation

• Let A be an edge on P and let B be an edge on Q

• A and B will chase each other to find all crossings of P and Q

• The critical point is when to advance A or B

  • Let a be the tip of A and b be the tip of B

  • Let H(A) be the left half-plane of A

  • A x B > 0 AND b in H(A) → Advance A

  • A x B > 0 AND b not in H(A) → Advance B

  • A x B < 0 AND a in H(B) → Advance B

  • A x B < 0 AND a not in H(B) → Advance A

• Although for convex polygons we have a nice algorithm the general case is still \(\Omega (n^2)\)

• Even if we were to simple compute the intersection points of two general polygons, that would take much time naively

• Can we at least compute the intersection points faster? (given that we have much less intersection points than \(n^2\))

• If we consider each polygon edge to be an independent line segment, this is equivalent to computing the intersections of \(n\) line segments

• We now look into this problem

• We already know how to test whether two segments intersect

• But what if we have tens of them?

• Worst case optimal: \(O(n^2)\)

  • If all segments intersect all other segments you have to report this many intersections

• Average case optimal?

  • Naive algorithm: \(O(n^2)\). Test all segments with each other

  • Better algorithm? Output sensitive algorithms?

• A plane sweep approach can help here

• Event points:

  • Where a segment starts : \(O(m)\)

  • Where a segment ends : \(O(m)\)

  • Where two segments intersect : \(O(k)\)

  • Total events : \(O(m+k)\)

• If \(k << m\), an output sensitive algorithm can perform greatly

• We are given a set of line segments

• We want to find where they intersect

• We will use a plane sweep aproach

• We will maintain the following data through event points:

  • Q: A queue of event points

    • The queue is dynamic. It will be populated through the algorithm

  • L: A list of segments being intersected by the sweep line

• The event queue will be initialized with the end points of all segments sorted from top to bottom

• Whenever a potential intersection point in the future is computed, it will be injected into the queue

• Note that a new potential intersection is detected only between adjacent edges in \(L\)

• How to do non-convex polygon intersections?

• We can still apply a sweep line

• Now maintain regions through L.

  • \(I_{AB}\): Inside both polygons

  • \(I_A\): Inside A, Outside B

  • \(I_B\): Outside A, Inside B

  • \(I_\emptyset\): Outside both polygons

• Track edges on both sides of \(I_{AB}\) to outline the intersection regions