# Line Segment Intersection - Map Overlay
計算幾何 Min-Te Sun, Ph.D

Two of Classical Computational Geometry Problems
---
1. Line Segment Intersection -> 找rivers and road相交的地方
2. Computing the Overlay of Two Subdivisions

Line Segment Intersection
* Problem statement:
-> Given a set S of n closed segments in the plane, report all intersection points among the segments in S
* Time Complexity -> Ω (n^2)

## Output-Sensitive Algorithm

* 在Output較小時，可以省掉一些時間
* 避免測試所有點 for intersection
* 若x-intervals 沒有overlap，則不可能會相交
* 若y-intervals 沒有overlap，則不可能會相交
* 以上方法稱 **plane sweep algorithm**
=> 將Segments分為 **active Segments** 和 **inactive Segments**
* Observation：intersection 會發生在鄰居線段
* Event Points：End points of segments
* 𝓵為 **sweep line**
* “Active” Line Segments：測試neighboring segments有沒有相交
### Algorithm
---

### HandleEventPoint( p )
---
* 1、2、3為定義甚麼是U( p )、L( p )、C( p )
* **U( p )：upper end point 的集合**
* **L( p )：lower end point 的集合**
* **C( p )：這個集合會經過p，但p不在端點**

### FindNewEvent (S𝓵,Sr,p)

---
### Example
* p為𝓵上的點，U( p )、L( p )、C( p )分別為：
* U( p )：S2
* L( p )：S4、S5
* C( p )：S1、S3

Time Complexity
---
* Time Complexity為 O(nlogn + I*logn) -> I 是S集合中intersections的數目
* 每個operation需要O(logn)