this is for holding javascript data
Mazdak Farrokhzad added pseudocode.tex
about 10 years ago
Commit id: 36e30e491d934443568d73175179f6b475cf7cea
deletions | additions
diff --git a/pseudocode.tex b/pseudocode.tex
new file mode 100644
index 0000000..5b2d47e
--- /dev/null
+++ b/pseudocode.tex
...
\section{Pseudocode}
We'll first assume that we have access to the following constant time subroutines:
\begin{verbatim}
/*
* Finds the minimum angle needed for a ray originating in O to intersect
* a circle C. To be consistent with max_intersection_angle(), the angle of
* a ray originating in O and passing through the center of C is defined to
* lie in the interval [0, 2pi]. This means that the value returned by this
* function may be negative, but never greater than 2pi.
*/
function min_intersection_angle(O, C)
/*
* Finds the maximum angle needed for a ray originating in O to intersect
* a circle C. To be consistent with min_intersection_angle(), the angle of
* a ray originating in O and passing through the center of C is defined to
* lie in the interval [0, 2pi]. This means that the value returned by this
* function may be greater then 2pi, but never negative.
*/
function max_intersection_angle(O, C)
\end{verbatim}
\subsection{Abstract pseudocode}
\begin{verbatim}
function min_rays_intersecting(origin, circles) begin
find a ray R which doesn't intersect any of the circles
let Q be a priority queue of angles intervals ordered by the angle at which they end
convert circles into a set of intervals beginning at angle(R) and add them to Q
while Q not empty loop
let I = delete_min(Q)
if I is not intersected then
add ray at end of I
end if
end loop
return number of rays
end
\end{verbatim}
\subsection{More detailed version}
\begin{verbatim}
function min_rays_intersecting(origin, circles) begin
find a ray R which doesn't intersect any of the circles
let Q be a priority queue of angles intervals ordered by the angle at which they end
for each C in circles loop
let A_min = (min_intersection_angle(origin, C) - angle(R)) mod 2pi
let A_max = (max_intersection_angle(origin, C) - angle(R)) mod 2pi
add [A_min, A_max] to Q
end loop
let P = R
let N_R = 0
while Q not empty loop
let I = delete_min(Q)
if starting_angle(I) > P then
increment N_R
P = ending_angle(I)
end if
end loop
return N_R
end
\end{verbatim}