Xavier Holt edited Assume_we_are_comparing_two__.tex  about 8 years ago

Commit id: 68bd4b8bd00f39a00d9fd7805fcf9f9b086f545a

deletions | additions      

       

Assume we are comparing two intervals $A$ and $B$. Let $A$ be the interval stored in-heap, in-heap  and $B$ the interval we've just encountered the first end-point of. We represent our intervals with a line-segment parametisation. That is, an interval is defined by $\{\mathbf{u} + t\mathbf{v}\mid t\in [0,1]\}$ where in our case $\mathbf{u}$ and $\mathbf{v} \in\mathbb{R}^2$.   As such the encountered. Our  points of comparison interest  are $B\vert_0$ (the the  first end-point of B) $B$,  and the point on $A$ we get which intersects the radial scan line at this point. We can do so in $O(1)$ by simply comparing the line defined  byextending  the $QB$ segment until intersection. angle $\angle mqB\vert 0$