Consider an edge e in a subdivision, where the two incident faces are triangles.
ID: 3679415 • Letter: C
Question
Consider an edge e in a subdivision, where the two incident faces are triangles. Give the DCEL modifications to perform the operation shown below in Figure 1 (called an edge flip). You do not need to change the face or vertex information, just the next and previous pointers for the edges of the subdivision.
Note that the next and prev information changes not only for e, but also for the other four edges that bound the two triangles. Call these edges a,b,c and d. It will be easier to make all the changes by first setting some variables to those edges. Please NO CODE.
Explanation / Answer
when we want to flip edge, then it may touch more than or equal to 2 vertices.
Then draw circle touching all vertices. Then it will create triangles. Then check vertex of polygon
whether lies on oppsite side of edge. If this particular edge fails to incircle test , then swap edge.
So these edges are actual pointers to DCEL.
Add(M):
find triangles which contains M
then add edges Ma, MB, Mc ...
checkIncircleTest(ab);
checkIncircleTest(bc);
..
.
.
checkIncircleTest(AB)
if(AB is edge on exterior face) then return
Assume e is vertex to right of edge ab;
if(incircle(M,a,b,c,d))
flip edge AB for Ma;
checkIncircleTest(AM);
checkIncircleTest(MB);