Permalink

Fetching contributors…

Cannot retrieve contributors at this time

\documentclass{article} | |

\usepackage{graphicx,amsmath,amsthm,amssymb} | |

\usepackage{fullpage} | |

\usepackage{eucal} | |

\usepackage{graphicx} | |

\usepackage{color} | |

\usepackage{tikz} | |

\usepackage{algorithm,algorithmic} | |

\newcommand{\question}[1]{\vspace{10pt}\noindent $\mathbf{#1}$} | |

\newcommand{\R}{\mathbb{R}} | |

\newcommand{\vect}[2]{\bigl[\begin{smallmatrix}#1\\#2\end{smallmatrix}\bigr]} | |

\newcommand{\vectt}[3]{\bigl[\begin{smallmatrix}#1\\#2\\#3\end{smallmatrix}\bigr]} | |

\newcommand{\gap}{{~~~~~~~~~~~~~~~~~~~~~}} | |

\newcommand{\vor}{\mathrm{Vor}} | |

\newcommand{\CC}{\mathrm{conv}} | |

\newcommand{\sign}{\mathrm{sign}} | |

\newcommand{\orient}{\textsc{Orient}} | |

\title{Computational Geometry: Fall 2016: Homework 2} | |

\author{} | |

\begin{document} | |

\maketitle | |

\section*{Administration} | |

Your answers should be typeset in \LaTeX\ or some equivalent and submitted as a \textbf{pdf}. | |

The \LaTeX\ source of these questions may be found on the course website under ``homework''. | |

Name your files as ``2\_\emph{your\_last\_name}.pdf'', all lowercase letters. | |

For example, I would call mine \textbf{2\_sheehy.pdf}. | |

% Submission: Use the same repository that you used for your last submission. If you did not submit the last homework: | |

Create a \textbf{private} repository on github.uconn.edu and add me (userid: she13001) as a collaborator. Name your repository ``your\_last\_name\_compgeom'' (all lowercase). | |

\textbf{push your solutions to the repository before midnight on Monday, Nov 7. Remember that you have to both commit and push.} | |

\section*{PSLGs and the HalfEdge Data Structure} | |

Assume (unless otherwise noted) for all of the following problems that you are given a connected HalfEdge data structure that stores the faces implcitly. | |

That is, there are objects for vertices and edges, but a face can be represented by an arbitrary halfedge bounding that face. | |

Assume the definitions of the three classes Vertex, Edge, and HalfEdge as described in class. | |

\noindent | |

\textbf{HalfEdge} supports the following operations. | |

\begin{enumerate} | |

\item origin() - Return the Vertex at the origin (tail) of the halfedge. | |

\item prev() - Return the previous (in ccw order) halfedge on the same face. | |

\item next() - Return the next (in ccw order) halfedge on the same face. | |

\item twin() - Return the halfedge on the same edge but the other face. | |

\end{enumerate} | |

\noindent | |

\textbf{Vertex} supports the following operations. | |

\begin{enumerate} | |

\item halfedge() - Return an arbitrary halfedge that has this vertex as its origin. | |

\item edges() - Return a list of the edges incident to this vertex in ccw order. | |

\item wedge(vector) - Return the halfedge $h$ that has this vertex as its origin and such that $h$ and $h.next()$ are on opposite sides of vector in ccw order. | |

\end{enumerate} | |

\noindent | |

\textbf{Edge} supports the following operations. | |

\begin{enumerate} | |

\item halfedge - Return an arbitrary halfedge on this edge. | |

\item vertices() - Return a list of the two vertices incident to this edge. | |

\end{enumerate} | |

\question{1} \textbf{Adding Edges} | |

Give pseudocode to implement a method to add an edge. | |

The method \texttt{addedge(u, v)}, takes two vertices as input. | |

It should update all the appropriate halfedges. | |

\begin{algorithm}[H] | |

\caption*{$ADDEDGE(U, V)$} | |

\begin{algorithmic} | |

\STATE $U_{new}$ = new $HalfEdge()$ | |

\STATE $V_{new}$ = new $HalfEdge()$ | |

\STATE $U_{new}$.origin = $U$; $U_{new}$.twin = $V_{new}$ | |

\STATE $V_{new}$.origin = $V$; $V_{new}$.twin = $U_{new}$ | |

\STATE $U_{new}$.prev = $U$.halfEdge.prev() | |

\STATE $U$.halfEdge.prev().next = $U_{new}$ | |

\STATE $U_{new}$.next = $V$.halfEdge.next() | |

\STATE $V$.halfEdge().next().prev = $U_{new}$ | |

\STATE $V_{new}$.prev = $V$.halfEdge.prev() | |

\STATE $V$.halfEdge.prev().next = $V_{new}$ | |

\STATE $V_{new}$.next = $V$.halfEdge.next() | |

\STATE $V$.halfEdge.next().prev = $V_{new}$ | |

\end{algorithmic} | |

\end{algorithm} | |

\question{2} \textbf{Removing Edges} | |

Give pseudocode to implement a method to remove an edge. | |

The method \texttt{removeedge(e)}, takes an edge as input. | |

It should update all the appropriate halfedges. | |

You may assume the graph will remain connected. | |

\begin{algorithm}[H] | |

\caption*{$REMOVEEDGE(U, V)$} | |

\begin{algorithmic} | |

\STATE ITERATE EDGES with $i$ | |

\IF{$U[i]$.halfEdge().next().origin() === $V$} | |

\STATE $U[i]$.halfEdge().prev().next = $U[i]$.halfEdge.twin().next() | |

\STATE $U[i]$.halfEdge().next().prev = $U[i]$.halfEdge.twin().prev() | |

\ENDIF | |

\IF{$V[i]$.halfEdge().next().origin() === $U$} | |

\STATE $V[i]$.halfEdge().prev().next = $U[i]$.halfEdge.twin().next() | |

\STATE $V[i]$.halfEdge().next().prev = $U[i]$.halfEdge.twin().prev() | |

\ENDIF | |

\end{algorithmic} | |

\end{algorithm} | |

\question{3} \textbf{Flipping Edges} | |

Use the previous methods and the \texttt{InCircle} predicate to give pseudocode for a method \texttt{DelaunayFlip(e)} that takes an edge e and flips it if it's not locally Delaunay. | |

\begin{algorithm}[H] | |

\caption*{$DELAUNEY(E)$} | |

\begin{algorithmic} | |

\STATE let $(u, v)$ = $E$.vertices() | |

\STATE$U_{nextVer}$ = $U$.halfEdge.next().twin().origin() | |

\STATE$V_{nextVer}$ = $V$.halfEdge.next().twin().origin() | |

\IF{(incircle($U, V, V_{nextVer}, U_{nextVer}$) OR incircle($U, U_{nextVer}, V, V_{nextVer}$))} | |

\STATE $removeEdge$(U,V) | |

\STATE $addEdge(U_{nextVer}, V_{nextVer})$ | |

\ELSE | |

\STATE return; | |

\ENDIF | |

\end{algorithmic} | |

\end{algorithm} | |

\section*{Walking through a triangulation} % (fold) | |

Point location in a triangulation is the problem of finding what triangle contains a given query point. | |

A popular algorithm for locating a point in a triangulation uses an idea very similar to the one we used for polygon membership testing. | |

Recall that for polygons, we intersected every edge of the polygon with a ray and counted intersections. | |

Now, we are not interested in the number of intersections, but we would like to return a halfedge on the face (triangle) containing the query point $q$. | |

If we start from a vertex $v$ of the triangulation, we can draw a straight line segment from $v$ to $q$. | |

We can then walk from triangle to triangle (using halfedge operations) so that the triangles visited in this process are exactly those intersecting the line segment $\overline{vq}$. | |

Implemented with a halfedge data structure, we really go from halfedge to halfedge. | |

\question{4} \textbf{Point Location by Walking} | |

Give pseudocode for implementing a walking based point location algorithm for triangulations. | |

You may make any convenient general position assumptions on the inputs and the query. | |

\begin{algorithm}[H] | |

\caption*{$WALKINGTRIANGULATION(q)$} | |

\begin{algorithmic} | |

\STATE $v$ = arbitrary vertex in triangulation | |

\STATE $l$ = line $vq$ | |

\STATE $start$ = $v$.halfEdge() | |

\STATE $current$ = $v$.halfEdge().next() | |

\WHILE {$true$} | |

\IF{$start === current$} | |

\STATE $return$ current | |

\ENDIF | |

\IF {$intersection$(current, l)} | |

\STATE $start$ = $current$.twin() | |

\STATE $current$ = $start$.next() | |

\ELSE | |

\STATE $current$ = $current$.next() | |

\ENDIF | |

\ENDWHILE | |

\end{algorithmic} | |

\end{algorithm} | |

\question{5} \textbf{Visibility Walk} | |

There is another version of the walking-based point location algorithm called the ``visibility walk''. | |

In this version, we still go from triangle to triangle (really halfedge to halfedge), but we are less strict about which will be the next triangle. | |

We are instead allowed to visit the next triangle through any edge that is ``visible'' to the query point. | |

By ``visible'', we mean that a straight line segment from the query point to a point on the edge (not the endpoints) can drawn that does not intersect either of the other two edges of the current triangle. | |

There are many cases, there are two possible next triangles and any of several heuristics can be used to choose between the two. | |

Find an example of a triangulation and a query (in general position) for which the visibility walk may not terminate. | |

That is, it will cycle without every reaching the triangle containing the query. | |

Is your example Delaunay? | |

Bonus: Can there be such a bad example that is also Delaunay? | |

\begin{figure} | |

\caption {An Example of an infinite loop in a Visibility Walk} | |

\centering | |

\includegraphics[scale=1]{cycle} | |

\end{figure} | |

\textbf{This infinite cycle can be fixed by using a heuristic that makes random choices when there are two possible paths to take} | |

\textbf{BONUS: | |

A visibility walk in a triangulation that is strictly Delaunay will always terminate} | |

% section polygons (end) | |

\end{document} |