<jupyter_start><jupyter_text>Voronoi Diagrams from Delaunay Triangulations CS 480 Computational Geometry Dr. <NAME>For this lab you are going to build on the code you developed in the previous lab to compute the Voronoi diagram. Recall that the Voronoi diagram is the dual graph of the Delaunay triangulation. For this lab we will write code that takes in a DCEL representing a triangulation and computes the dual.  Code: Predicates<jupyter_code>from koebe.geometries.euclidean2 import PointE2, SegmentE2, CircleE2

### Predicates

def areaOfParallelogram(A: PointE2, B: PointE2, C: PointE2) -> float:
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y)

def areaOfTriangle(A: PointE2, B: PointE2, C: PointE2) -> float:
    return 0.5 * areaOfParallelogram(A, B, C)

def leftHandTurn(A: PointE2, B: PointE2, C: PointE2) -> bool:
    return areaOfTriangle(A, B, C) > 0

def inCircle(A: PointE2, B: PointE2, C: PointE2, D: PointE2) -> bool:
    """
    Returns true if D is in the circle through points A, B, and C. 
    """
    adx = A.x - D.x
    ady = A.y - D.y
    bdx = B.x - D.x
    bdy = B.y - D.y
    cdx = C.x - D.x
    cdy = C.y - D.y

    abdet = adx * bdy - bdx * ady
    bcdet = bdx * cdy - cdx * bdy
    cadet = cdx * ady - adx * cdy
    alift = adx * adx + ady * ady
    blift = bdx * bdx + bdy * bdy
    clift = cdx * cdx + cdy * cdy
    
    return (alift * bcdet + blift * cadet + clift * abdet) > 0<jupyter_output><empty_output><jupyter_text>Elementary Operations<jupyter_code>def orient(p1, p2, p3):
    return (p1, p2, p3) if leftHandTurn(p1, p2, p3) else (p1, p3, p2)

def circleCenter(p1: PointE2, p2: PointE2, p3: PointE2) -> PointE2:
    """Computes the center of the circle through points p1, p2, p3."""
    # HINT: Don't reinvent the wheel. See the CircleE2 class. 
    return p1 # TODO Fix this<jupyter_output><empty_output><jupyter_text>Datastructures<jupyter_code>class DCEL:
    """
    The basic DCEL container. 
    
    Attributes:
        verts: List[Vertex] - The list of vertices. 
        halfEdges: List[HalfEdge] - The list of half-edges. 
        faces: List[Face] - The list of faces. 
        outerFace: Face - The outerFace (None if there isn't one.)
    """
    def __init__(self):
        self.verts = []
        self.halfEdges = []
        self.faces = []
        self.outerFace = None
    
    def dual(self, face_to_dual_pos):
        """
        Constructs the dual graph for this DCEL. 
        
        Attributes:
            face_to_dual_pos: (DCEL, Face) -> PointE2? - A function that takes in a face and returns a PointE2 for the dual vertex's .pos attribute.
                The function face_to_dual_pos should return None if Face is the dual face. 
        Returns: 
            A new DCEL object representing the dual. Should call the face_to_pos function on each of the primal faces
            in order to compute the position of the dual vertex. 
        """
        # HINT: To start you off, let's create a DCEL to store the dual. 
        dual = DCEL()
        
        # HINT: Creating some lookup dictionaries to convert between primal and dual is helpful: 
        dualOf = {}
        primalOf = {}
        
        # HINT: Let's create a dual Face for every primal Vertex: 
        for v in self.verts:
            df = Face(dual)
            dualOf[v] = df
            primalOf[df] = v
        
        # Step 2: Create duals for the half-edges and faces. 
        # TODO
        # Step 3: Stitch up all the attributes (Vertex.outgoingHalfEdge, Vertex.pos, Face.incidentHalfEdge, etc.)
        # TODO
        
        return dual
    
class Vertex:
    """
    The basic Vertex object. 
    
    Attributes:
        dcel: DCEL - The parent DCEL. 
        outgoingHalfEdge: HalfEdge - Any one half-edge with this vertex as its origin.
        
    """
    def __init__(self, dcel, outgoingHalfEdge=None, pos=None):
        self.dcel = dcel
        self.dcel.verts.append(self)
        self.outgoingHalfEdge = outgoingHalfEdge
        self.pos = pos

class Face:
    def __init__(self, dcel, incidentHalfEdge=None):
        self.dcel = dcel
        self.dcel.faces.append(self)
        self.incidentHalfEdge = incidentHalfEdge
    
    def incidentHalfEdges(self):
        result = []
        curr = self.incidentHalfEdge
        while True:
            result.append(curr)
            curr = curr.next
            if curr == self.incidentHalfEdge:
                break
        return result
    
    def incidentVertices(self):
        return [he.origin for he in self.incidentHalfEdges()]

class HalfEdge:
    def __init__(self, 
                 dcel, 
                 origin=None, 
                 face=None, 
                 prev=None, 
                 next=None, 
                 twin=None):
        
        self.dcel   = dcel
        self.dcel.halfEdges.append(self)
        
        self.origin = origin
        self.face   = face
        self.prev   = prev
        self.next   = next
        self.twin   = twin
    
    def makeNext(self, he):
        self.next = he
        he.prev = self
    
    def makeTwin(self, he):
        self.twin = he
        he.twin = self
    
    @property # The @property annotation let's you "run" this as
              # he.destination instead of he.destination()
    def destination(self):
        return self.twin.origin
    
    def isLegal(self) -> bool:
        return False # TODO COPY YOUR SOLUTION FROM PREVIOUS LAB
    
    def flip(self):
        # First check if this is a valid flippable edge (i.e. an illegal edge)
        # Then do the flip by fixing self and self.twin's pointers (and the surrounding
        # half-edges of the flip quadrilateral). HINT: Remember that .face and .origin
        # pointers need to be updated for self and self.twin and .face pointers need
        # to be updated for all the half-edges incident the outer quadrilateral. 
        pass # TODO COPY YOUR SOLUTION FROM THE PREVIOUS LAB

def splitFace(e1: HalfEdge, e2: HalfEdge) -> None:
    if e1.face != e2.face:
        return
    
    newFace = Face(e1.dcel)

    s1 = HalfEdge(dcel=e1.dcel, origin=e2.origin, face=e1.face)
    s2 = HalfEdge(dcel=e1.dcel, origin=e1.origin, face=newFace)
    s1.makeTwin(s2)

    e2.prev.makeNext(s1)
    e1.prev.makeNext(s2)
    s1.makeNext(e1)
    s2.makeNext(e2)

    newFace.incidentHalfEdge = e2
    e1.face.incidentHalfEdge = e1

    for e in e1.face.incidentHalfEdges(): e.face = e1.face
    for e in newFace.incidentHalfEdges(): e.face = newFace<jupyter_output><empty_output><jupyter_text>Algorithms<jupyter_code>from typing import List

def triangleDCEL(p1: PointE2, p2: PointE2, p3: PointE2) -> DCEL:
    """
    Convenience method for creating a DCEL representing a triangle given its three corners. 
    """
    result = DCEL()
    result.outerFace = Face(result)
    
    tri = Face(result)
    
    A, B, C = [Vertex(dcel=result, pos=p) for p in orient(p1, p2, p3)]
    
    AB = HalfEdge(dcel=result, origin=A, face=tri)
    BC = HalfEdge(dcel=result, origin=B, face=tri)
    CA = HalfEdge(dcel=result, origin=C, face=tri)
    
    AC = HalfEdge(dcel=result, origin=A, face=result.outerFace)
    CB = HalfEdge(dcel=result, origin=C, face=result.outerFace)
    BA = HalfEdge(dcel=result, origin=B, face=result.outerFace)
    
    AB.makeTwin(BA)
    BC.makeTwin(CB)
    CA.makeTwin(AC)
    
    AB.makeNext(BC)
    BC.makeNext(CA)
    CA.makeNext(AB)
    
    AC.makeNext(CB)
    CB.makeNext(BA)
    BA.makeNext(AC)
    
    A.outgoingHalfEdge = AB
    B.outgoingHalfEdge = BC
    C.outgoingHalfEdge = CA
    
    tri.incidentHalfEdge = AB
    result.outerFace.incidentHalfEdge = BA
    
    return result

def findLowerTangent(dcel, p):
    for he in dcel.outerFace.incidentHalfEdges():
        if (leftHandTurn(he.prev.origin.pos, he.origin.pos, p) 
            and leftHandTurn(he.next.origin.pos, he.origin.pos, p)):
            return he
    return None

def findUpperTangent(dcel, p):
    for he in dcel.outerFace.incidentHalfEdges():
        if (leftHandTurn(p, he.origin.pos, he.next.origin.pos) 
            and leftHandTurn(p, he.origin.pos, he.prev.origin.pos)):
            return he
    return None

def incrTriangulation(S: List[PointE2]) -> DCEL:
    thePoints = sorted(S, key=lambda p:(p.x, p.y))
    result = triangleDCEL(*thePoints[0:3])
    for p in thePoints[3:]:
        lowerTangent = findLowerTangent(result, p)
        upperTangent = findUpperTangent(result, p)
        
        upper_orig_prev = upperTangent.prev
        
        v = Vertex(dcel=result, pos=p)
        f = Face(dcel=result, incidentHalfEdge=upperTangent)

        upper_inner = HalfEdge(dcel=result, origin=v, face=f)
        lower_inner = HalfEdge(dcel=result, origin=lowerTangent.origin, face=f)
        
        upper_outer = HalfEdge(dcel=result, origin=upperTangent.origin, face=result.outerFace)
        lower_outer = HalfEdge(dcel=result, origin=v, face=result.outerFace)
        
        upper_inner.makeTwin(upper_outer)
        lower_inner.makeTwin(lower_outer)
        
        upper_inner.makeNext(upperTangent)
        lowerTangent.prev.makeNext(lower_inner)
        lower_inner.makeNext(upper_inner)
        
        upper_orig_prev.makeNext(upper_outer)
        upper_outer.makeNext(lower_outer)
        lower_outer.makeNext(lowerTangent)
        
        result.outerFace.incidentHalfEdge = upper_outer
        f.incidentHalfEdge = upperTangent
        v.outgoingHalfEdge = upper_inner
        
        for e in f.incidentHalfEdges(): e.face = f
        
        curr = upper_inner.next.next
        vHe = upper_inner
        while curr != lower_inner:
            curr = curr.next
            splitFace(curr.prev, vHe)
            vHe = curr.prev.prev
            
    return result
        
        
def delaunify(triangulation: DCEL):
    # Use your flip() code to convert the given triangulation into a DCEL
    # using the flip algorithm from class. 
    pass # TODO COPY YOUR SOLUTION TO THE PREVIOUS LAB

def face_avg(dcel, face):
    if dcel.outerFace == face:
        return None
    verts = face.incidentVertices()
    xAvg = sum([v.pos.x for v in verts]) / len(verts)
    yAvg = sum([v.pos.y for v in verts]) / len(verts)
    return PointE2(xAvg, yAvg)

def face_to_voronoi_vertex_pos(dcel, face):
    # TODO
    pass
    
def voronoi_dual(delaunayTriangulation: DCEL):
    """
    Given a delaunay triangulation returns the dual. 
    """
    pass<jupyter_output><empty_output><jupyter_text>Graphics LibraryTwo new canvases based on the editable point set canvas we used in the prior labs.<jupyter_code>from ipycanvas import Canvas, hold_canvas

def VoronoiCanvas(size, pts, draw_func = None):
    
    points = list(pts)
    canvas = Canvas(size=size)
    selectedPointIdx = -1
    
    incr = incrTriangulation(points)
    delaunify(incr)
    vor = voronoi_dual(incr)
    
    def _canvas_draw():
        nonlocal canvas, points, selectedPointIdx, draw_func, incr, vor
        
        with hold_canvas(canvas):
            canvas.clear()

            if draw_func != None:
                draw_func(canvas, points)
                
            for he in incr.halfEdges:
                he.marked = False
                
            if vor != None:
                for he in vor.halfEdges:
                    he.marked = False
                
            canvas.stroke_style = '#333'
            for he in incr.halfEdges:
                if not he.marked:
                    u = he.origin
                    v = he.destination
                    canvas.begin_path()
                    canvas.move_to(int(u.pos.x), int(u.pos.y))
                    canvas.line_to(int(v.pos.x), int(v.pos.y))
                    canvas.stroke()
                    he.marked = True
                    he.twin.marked = True
            
            if vor != None:
                canvas.stroke_style = 'crimson'
                for he in vor.halfEdges:
                    if not he.marked:
                        u = he.origin
                        v = he.destination
                        if u.pos != None and v.pos != None:
                            canvas.begin_path()
                            canvas.move_to(int(u.pos.x), int(u.pos.y))
                            canvas.line_to(int(v.pos.x), int(v.pos.y))
                            canvas.stroke()
                            he.marked = True
                            he.twin.marked = True

            canvas.fill_style = 'navy'
            canvas.fill_rects([round(p.x) - 4 for p in points], 
                              [round(p.y) - 4 for p in points], 
                              8)
            
            if selectedPointIdx != -1:
                canvas.fill_style = 'red'
                canvas.fill_rect(round(points[selectedPointIdx].x) - 4, 
                                 round(points[selectedPointIdx].y) - 4, 
                                 8)
            if vor != None:
                canvas.fill_style = 'crimson'
                canvas.fill_rects([round(v.pos.x) - 4 for v in vor.verts if v.pos != None], 
                                  [round(v.pos.y) - 4 for v in vor.verts if v.pos != None], 
                                  8)
            
            
    def handle_mouse_down(x, y):
        nonlocal selectedPointIdx, incr
        # See if any point is close to x, y
        cursorPoint = PointE2(x, y)
        sqDists = [p.distSqTo(cursorPoint) for p in points]
        minIdx = sqDists.index(min(sqDists))
        
        if sqDists[minIdx] < 24:
            selectedPointIdx = minIdx
        
        _canvas_draw()

    def handle_mouse_up(x, y):
        nonlocal selectedPointIdx
        selectedPointIdx = -1 # No point is selected anymore.
        _canvas_draw()

    def handle_mouse_move(x, y):
        nonlocal selectedPointIdx, incr, vor
        if selectedPointIdx >= 0:
            points[selectedPointIdx] = PointE2(x, y)
            incr = incrTriangulation(points)
            delaunify(incr)
            vor = voronoi_dual(incr)
        _canvas_draw()
    
    canvas.on_mouse_down(handle_mouse_down)
    canvas.on_mouse_up(handle_mouse_up)
    canvas.on_mouse_move(handle_mouse_move)
    
    _canvas_draw()
    
    return canvas<jupyter_output><empty_output><jupyter_text>Your TasksYour first task is to implement the following functions:* `circleCenter`: Computes the center of a circle through three points.* `DCEL.dual`: Computes the dual of a given DCEL object. * `face_to_voronoi_vertex_pos`: Converts a Face of a Delaunay triangulation to a Voronoi VertexYour second task is to add drawing of the infinite rays to the `VoronoiCanvas` application. __Turning it in:__ Turn everything in to Canvas by the deadline. Applications<jupyter_code>VoronoiCanvas(
    size=(800, 800),
    pts=[
        PointE2(p.x * 400 + 200, p.y * 400 + 200)
        for p in [PointE2(0.1, 0.29),
         PointE2(0.3, 0.23), 
         PointE2(0.55, 0.43), 
         PointE2(0.31, 0.61), 
         PointE2(0.31, 0.45), 
         PointE2(0.68, 0.52), 
         PointE2(0.69, 0.17)]
    ]
)
def face_to_point(face):
    return vor_point

for f in dcel.faces:
    if f != dcel.outerFace:
        p = face_to_point(f)
        draw(p)
for he in dcel.halfEdges:
    if he.face != dcel.outerFace and he.twin.face != dcel.outerFace:
        p = face_to_point(he.face)
        q = face_to_point(he.twin.face)
        draw_segment(p, q)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09379649395174332, 'fraction_numerical': 0.011579015460249692, 'mean_word_length': 1.9616858237547892, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '292622', 'license': 'MIT', 'n_tokens_mistral': 5241, 'n_tokens_neox': 4994, 'n_words': 1321, 'path': 'CS 480 Computational Geometry/Labs/06 - Voronoi Diagram from Delaunay Triangulation.ipynb', 'repo_name': 'johncbowers/koebepy', 'size': '15467'}