HW 2D CGA - PPT 5 - Clipping 2

-

Question 1

Solution:

We need to declare: 
$$A=\begin{bmatrix}2\\7\end{bmatrix}, B=\begin{bmatrix}10\\2\end{bmatrix}, C=\begin{bmatrix}7\\4\end{bmatrix}$$
And then find \(\overrightarrow {AB}\) and \(\vec N\):
$$\overrightarrow {AB}=\begin{bmatrix}10-2\\2-7\end{bmatrix}=\begin{bmatrix}8\\-5\end{bmatrix}$$
Here are some basic rule you need to know to easily define \(\vec N\):
$$if \ \vec N \ is \ to \ the \ left \ of \ any \ vector \rightarrow \vec N=\begin{bmatrix}-dy\\dx\end{bmatrix}$$ 
$$if \ \vec N \ is \ to \ the \ right \ of \ any \ vector \rightarrow \vec N=\begin{bmatrix}dy\\-dx\end{bmatrix}$$
From the rule above, we can see that because \(\vec N\) is facing to the left (up as stated in the question) of \(\overrightarrow {AB}\), we can conclude as stated below:
$$\vec N=\begin{bmatrix}-dy\\dx\end{bmatrix}=\begin{bmatrix}5\\8\end{bmatrix}$$
Variable \(dx\) and \(dy\) is taken from \(\overrightarrow {AB}\). After that the question requires us to find \(\overrightarrow {AC} \cdot \vec N\), which can be solved as stated below:
$$\overrightarrow {AC}=\begin{bmatrix}7-2\\4-7\end{bmatrix}=\begin{bmatrix}5\\-3\end{bmatrix}$$
$$\overrightarrow {AC} \cdot \vec N=\begin{bmatrix}5\\-3\end{bmatrix}\cdot\begin{bmatrix}5\\8\end{bmatrix}=5 \cdot 5+(-3)\cdot8=25-24=1$$
Now we've found \(\overrightarrow {AC} \cdot \vec N\), from that we can determine whether C is above or below \(\overrightarrow {AB}\), using the rule below:
$$if \overrightarrow {AC} \cdot \vec N > 0 \rightarrow C \ is \ above \ \overrightarrow {AB}$$
$$if \overrightarrow {AC} \cdot \vec N < 0 \rightarrow C \ is \ below \ \overrightarrow {AB}$$
From that rule we can conclude C is above \(\overrightarrow {AB}\) .


Question 2

Solution:

Below is the graph of question 2:
Graph from question 2
First of all, we need to declare all Edges as vectors (\(\vec E\)), and find Normal vectors (\(\vec N\)) of each Edge. We assume all edge vectors to have clockwise direction. Edge 1 vector is running from point A(2, 2) to B(2, 7) of the rectangle / clipping window:
$$\vec E_1=\begin{bmatrix}2-2\\7-2\end{bmatrix}=\begin{bmatrix}0\\5\end{bmatrix}$$
$$\vec N_1=\begin{bmatrix}dy\\-dx\end{bmatrix}=\begin{bmatrix}5\\0\end{bmatrix}$$ 
Edge 2 vector is running from point B(2, 7) to C(7, 7) of the rectangle / clipping window:
$$\vec E_2=\begin{bmatrix}7-2\\7-7\end{bmatrix}=\begin{bmatrix}5\\0\end{bmatrix}$$
$$\vec N_2=\begin{bmatrix}dy\\-dx\end{bmatrix}=\begin{bmatrix}0\\-5\end{bmatrix}$$ 
Edge 3 vector is running from point C(7, 7) to D(7, 2) of the rectangle / clipping window:
$$\vec E_3=\begin{bmatrix}7-7\\2-7\end{bmatrix}=\begin{bmatrix}0\\-5\end{bmatrix}$$
$$\vec N_3=\begin{bmatrix}dy\\-dx\end{bmatrix}=\begin{bmatrix}-5\\0\end{bmatrix}$$
Edge 4 vector is running from point D(7, 2) to A(2, 2) of the rectangle / clipping window:
$$\vec E_4=\begin{bmatrix}2-7\\2-2\end{bmatrix}=\begin{bmatrix}-5\\0\end{bmatrix}$$
$$\vec N_4=\begin{bmatrix}dy\\-dx\end{bmatrix}=\begin{bmatrix}0\\5\end{bmatrix}$$
Now we will process each line to determine whether they are trivially accepted or trivially rejected, if a line failed to classify into the trivial cases, then we need to find the intersection and update existing points of the line until that line classify into either trivial cases. Now let's begin with Line 1 (3, 4) to (6, 3) by drawing the table:
\begin{array} {|r|r|}\hline Edge & Point \ 1 & Point \ 2 \\ \hline \vec E_1 & in & in \\ \hline \vec E_2 & in & in \\ \hline \vec E_3 & in & in \\ \hline \vec E_4 & in & in \\ \hline  \end{array}From the table we can determine that Line 1 is trivially accepted because Point 1 and Point 2 are inside all of the edges meaning Line 1 is actually inside the clipping window. Now for Line 2 from (5, 3) to (1, 5) let's draw the table:
 \begin{array} {|r|r|}\hline
Edge & Point \ 1 & Point \ 2 \\ \hline
\vec E_1 & in & out \\ \hline
\vec E_2 & in & in \\ \hline
\vec E_3 & in & in \\ \hline
\vec E_4 & in & in \\ \hline
\end{array}


From the table we can see there's one out occured in Edge 1 Point 2, this means Line 2 is not trivially accepted nor rejected, then we should proceed to finding the interection in Edge 1 from A(2, 2) to B(2, 7). To find the intersection we will use equations below:
$$
t= \frac{\overrightarrow {P_1A} \cdot \vec N_1}{\overrightarrow {P_1P_2} \cdot \vec N_1 }
$$
$$
t= \frac{\begin{bmatrix}2-5\\2-3\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix}}{\begin{bmatrix}1-5\\5-3\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix} }= \frac{\begin{bmatrix}-3\\-1\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix}}{\begin{bmatrix}-4\\2\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix} }=\frac{-15+0}{-20+0}=\frac{3}{4}
$$
After we've found \(t\) we can insert it into the equation below to find intersection coordinate:
$$
\begin{align}
Ox & = P_1x + t (P_2x - P_1x) \\
& = 5 + \frac{3}{4} (1 - 5) \\
& = 5 + \frac{3}{4} (-4) \\
& = 5 - 3 \\
& = 2
\end{align}
$$
$$
\begin{align}
Oy & = P_1y + t (P_2y - P_1y)\\
& = 3 + \frac{3}{4} (5 - 3)\\
& = 3 + \frac{3}{4} (2)\\
& = \frac{6}{2} + \frac{3}{2}\\
& = \frac{9}{2}
\end{align}
$$
From the equation above, we got new \(P_2(2, \ \frac{9}{2})\). After we've found new Point 2 we need to check with the table once more:
\begin{array} {|r|r|}\hline
Edge & Point \ 1 & Point \ 2 \\ \hline
\vec E_1 & in & in \\ \hline
\vec E_2 & in & in \\ \hline
\vec E_3 & in & in \\ \hline
\vec E_4 & in & in \\ \hline
\end{array}
From the table above we can see now Line 2 is trivially accepted with Line 2 from (5, 3) to \((2, \ \frac{9}{2})\). Now for Line 3 from (0, 0) to (12, 3) let's draw the table:
\begin{array} {|r|r|}\hline
Edge & Point \ 1 & Point \ 2 \\ \hline
\vec E_1 & out & in \\ \hline
\vec E_2 & in & in \\ \hline
\vec E_3 & in & out \\ \hline
\vec E_4 & out & in \\ \hline
\end{array}
From the table above we know that there must be an intersection at Edge 1 Point 1, let's dive right in into Edge 1 from A(2, 2) to B(2, 7):
$$
t= \frac{\overrightarrow {P_1A} \cdot \vec N_1}{\overrightarrow {P_1P_2} \cdot \vec N_1 }
$$
$$
t= \frac{\begin{bmatrix}2-0\\2-0\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix}}{\begin{bmatrix}12-0\\3-0\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix} }= \frac{\begin{bmatrix}2\\2\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix}}{\begin{bmatrix}12\\3\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix} }=\frac{10+0}{60+0}=\frac{1}{6}
$$
Now that we've found \(t\) we can insert it into equation below:
$$
\begin{align}
Ox & = P_1x + t (P_2x - P_1x) \\
& = 0 + \frac{1}{6} (12 - 0) \\
& = \frac{1}{6} (12) \\
& = 2
\end{align}
$$
$$
\begin{align}
Oy & = P_1y + t (P_2y - P_1y)\\
& = 0 + \frac{1}{6} (3 - 0)\\
& = \frac{1}{6} (3)\\
& = \frac{1}{2}
\end{align}
$$ From the equation above we got new \(P_1(2, \ \frac{1}{2})\). After that we need to check with the table again:
\begin{array} {|r|r|}\hline
Edge & Point \ 1 & Point \ 2 \\ \hline
\vec E_1 & in & in \\ \hline
\vec E_2 & in & in \\ \hline
\vec E_3 & in & out \\ \hline
\vec E_4 & out & in \\ \hline
\end{array}
From the table above we can see the next intersection occurs in Edge 3 from C(7, 7) to D(7, 2) Point 2. Let's go:
$$
t= \frac{\overrightarrow {P_1D} \cdot \vec N_3}{\overrightarrow {P_1P_2} \cdot \vec N_3 }
$$
$$
t= \frac{\begin{bmatrix}7-0\\2-0\end{bmatrix} \cdot \begin{bmatrix}-5\\0\end{bmatrix}}{\begin{bmatrix}12-0\\3-0\end{bmatrix} \cdot \begin{bmatrix}-5\\0\end{bmatrix} }= \frac{\begin{bmatrix}7\\2\end{bmatrix} \cdot \begin{bmatrix}-5\\0\end{bmatrix}}{\begin{bmatrix}12\\3\end{bmatrix} \cdot \begin{bmatrix}-5\\0\end{bmatrix} }=\frac{-35+0}{-60+0}=\frac{-35}{-60}=\frac{7}{12}
$$
Now that we've found \(t\), we can insert it to the equation below:
$$
\begin{align}
Ox & = P_1x + t (P_2x - P_1x) \\
& = 0 + \frac{7}{12} (12 - 0) \\
& = \frac{7}{12} (12) \\
& = 7
\end{align}
$$
$$
\begin{align}
Oy & = P_1y + t (P_2y - P_1y)\\
& = 0 + \frac{7}{12} (3 - 0)\\
& = \frac{7}{12} (3)\\
& = \frac{7}{4}
\end{align}
$$
From the equation above, we got new \(P_2(7, \ \frac{7}{4})\). Now let's check with the table again with the new Point 2:
\begin{array} {|r|r|}\hline
Edge & Point \ 1 & Point \ 2 \\ \hline
\vec E_1 & in & in \\ \hline
\vec E_2 & in & in \\ \hline
\vec E_3 & in & in \\ \hline
\vec E_4 & out & out \\ \hline
\end{array}
Let's take a moment to observe the table above. Based on Edge 3, Point 1 and Point 2 are inside but on Edge 4 now Point 2 is also out that's because the new Point 2  is located below Edge 4 and that causes it to be outside of Edge 4. Based on Edge 4 we can conclude that Line 3 is trivially rejected with \(P_1(2, \ \frac{1}{2})\) and \(P_2(7, \ \frac{7}{4})\). Now let's continue to the last Line 4 from (0, 1) to (9, 3):
\begin{array} {|r|r|}\hline
Edge & Point \ 1 & Point \ 2 \\ \hline
\vec E_1 & out & in \\ \hline
\vec E_2 & in & in \\ \hline
\vec E_3 & in & out \\ \hline
\vec E_4 & out & in \\ \hline
\end{array}
From the table above we can see the first intersection occurs at Edge 1 from A(2, 2) to B(2, 7):
$$
t= \frac{\overrightarrow {P_1A} \cdot \vec N_1}{\overrightarrow {P_1P_2} \cdot \vec N_1}
$$
$$
t= \frac{\begin{bmatrix}2-0\\2-1\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix}}
{\begin{bmatrix}9-0\\3-1\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix} }
= \frac{\begin{bmatrix}2\\1\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix}}
{\begin{bmatrix}9\\2\end{bmatrix} \cdot \begin{bmatrix}5\\0\end{bmatrix} }=\frac{10+0}{45+0}=\frac{10}{45}=\frac{2}{9}
$$
From the equation above we got \(t\) and then let's insert it to equation below to find the intersection coordinate:
$$
\begin{align}
Ox & = P_1x + t (P_2x - P_1x) \\
& = 0 + \frac{2}{9} (9 - 0) \\
& = \frac{2}{9} (9) \\
& =2
\end{align}
$$
$$
\begin{align}
Oy & = P_1y + t (P_2y - P_1y)\\
& = 1 + \frac{2}{9} (3 - 1)\\
& = \frac{9}{9} + \frac{2}{9} (2)\\
& = \frac{9}{9} + \frac{4}{9} \\
& = \frac{13}{9}
\end{align}
$$
From the equation above we got new \(P_1(2, \ \frac{13}{9})\). Now let's check with the table again:
\begin{array} {|r|r|}\hline
Edge & Point \ 1 & Point \ 2 \\ \hline
\vec E_1 & in & in \\ \hline
\vec E_2 & in & in \\ \hline
\vec E_3 & in & out \\ \hline
\vec E_4 & out & in \\ \hline
\end{array}
The next intersection occurs at Edge 3 from C(7, 7) to D(7, 2):
$$
t= \frac{\overrightarrow {P_1D} \cdot \vec N_3}{\overrightarrow {P_1P_2} \cdot \vec N_3}
$$
$$
t= \frac{\begin{bmatrix}7-0\\2-1\end{bmatrix} \cdot \begin{bmatrix}-5\\0\end{bmatrix}}
{\begin{bmatrix}9-0\\3-1\end{bmatrix} \cdot \begin{bmatrix}-5\\0\end{bmatrix} }
= \frac{\begin{bmatrix}7\\1\end{bmatrix} \cdot \begin{bmatrix}-5\\0\end{bmatrix}}
{\begin{bmatrix}9\\2\end{bmatrix} \cdot \begin{bmatrix}-5\\0\end{bmatrix} }=\frac{-35+0}{-45+0}=\frac{-35}{-45}=\frac{7}{9}
$$
Now that we've got \(t\), we can insert it to the equation below to find the intersection coordinate:
$$
\begin{align}
Ox & = P_1x + t (P_2x - P_1x) \\
& = 0 + \frac{7}{9} (9 - 0) \\
& = \frac{7}{9} (9) \\
& =7
\end{align}
$$
$$
\begin{align}
Oy & = P_1y + t (P_2y - P_1y)\\
& = 1 + \frac{7}{9} (3 - 1)\\
& = \frac{9}{9} + \frac{7}{9} (2)\\
& = \frac{9}{9} + \frac{14}{9} \\
& = \frac{23}{9}
\end{align}
$$
From the equation above we got new \(P_2(7, \ \frac{23}{9})\). Now let's check with the table again:
\begin{array} {|r|r|}\hline
Edge & Point \ 1 & Point \ 2 \\ \hline
\vec E_1 & in & in \\ \hline
\vec E_2 & in & in \\ \hline
\vec E_3 & in & in \\ \hline
\vec E_4 & out & in \\ \hline
\end{array}
Now we can see that there's one last intersection on Edge 4 from D(7, 2) to A(2, 2). Let's dive right in:
$$
t= \frac{\overrightarrow {P_1A} \cdot \vec N_4}{\overrightarrow {P_1P_2} \cdot \vec N_4}
$$
$$
t= \frac{\begin{bmatrix}2-0\\2-1\end{bmatrix} \cdot \begin{bmatrix}0\\5\end{bmatrix}}
{\begin{bmatrix}9-0\\3-1\end{bmatrix} \cdot \begin{bmatrix}0\\5\end{bmatrix} }
= \frac{\begin{bmatrix}2\\1\end{bmatrix} \cdot \begin{bmatrix}0\\5\end{bmatrix}}
{\begin{bmatrix}9\\2\end{bmatrix} \cdot \begin{bmatrix}0\\5\end{bmatrix} }=\frac{0+5}{0+10}=\frac{5}{10}=\frac{1}{2}
$$
Now that we've got \(t\), we can insert it directly into the equation below to find the intersection coordinate:
$$
\begin{align}
Ox & = P_1x + t (P_2x - P_1x) \\
& = 0 + \frac{1}{2} (9 - 0) \\
& = \frac{1}{2} (9) \\
& = \frac{9}{2}
\end{align}
$$
$$
\begin{align}
Oy & = P_1y + t (P_2y - P_1y)\\
& = 1 + \frac{1}{2} (3 - 1)\\
& = 1 + \frac{1}{2} (2)\\
& = 1 + 1 \\
& = 2
\end{align}
$$
From the equation above we got new \(P1(\frac{9}{2}, \ 2)\). Now let's update the table again:
\begin{array} {|r|r|}\hline
Edge & Point \ 1 & Point \ 2 \\ \hline
\vec E_1 & in & in \\ \hline
\vec E_2 & in & in \\ \hline
\vec E_3 & in & in \\ \hline
\vec E_4 & in & in \\ \hline
\end{array}
Now the table show us that Point 1 and Point 2 are inside the clipping window which means Line 4 is now trivially accepted with \(P1(\frac{9}{2}, \ 2)\) and \(P_2(7, \ \frac{23}{9})\).


Question 3

Solution:

Below is the graph from question 3:
Graph from question 3


We assume the edge vectors have clockwise direction. First of all, we need to find \(\vec E_1, \vec E_2, \vec E_3\) and \(\vec N_1, \vec N_2, \vec N_3\):
$$
P_1=
\begin{bmatrix}
0 \\ 0
\end{bmatrix},
P_2=
\begin{bmatrix}
5 \\ 10
\end{bmatrix},
P_3=
\begin{bmatrix}
10 \\ 0
\end{bmatrix}
$$
$$
\vec E_1=
\begin{bmatrix}
5-0 \\ 10-0
\end{bmatrix}=
\begin{bmatrix}
5 \\ 10
\end{bmatrix},
\vec N_1=
\begin{bmatrix}
dy \\ -dx
\end{bmatrix}=
\begin{bmatrix}
10 \\ -5
\end{bmatrix}
$$
$$
\vec E_2=
\begin{bmatrix}
10-5 \\ 0-10
\end{bmatrix}=
\begin{bmatrix}
5 \\ -10
\end{bmatrix},
\vec N_2=
\begin{bmatrix}
dy \\ -dx
\end{bmatrix}=
\begin{bmatrix}
-10 \\ -5
\end{bmatrix}
$$
$$
\vec E_3=
\begin{bmatrix}
0-10 \\ 0-0
\end{bmatrix}=
\begin{bmatrix}
-10 \\ 0
\end{bmatrix},
\vec N_3=
\begin{bmatrix}
dy \\ -dx
\end{bmatrix}=
\begin{bmatrix}
0 \\ 10
\end{bmatrix}
$$
Now we need to contruct the table:
\begin{array} {|r|r|}\hline
Edge & A & B \\ \hline
\vec E_1 & out & in \\ \hline
\vec E_2 & in & out \\ \hline
\vec E_3 & out & in \\ \hline
\end{array}
I'll post how to determine whether a point is inside or outside using vector. Now that we know where intersection occurs we can directly go to it, first intersection is on Edge 1 from P1(0, 0) to P2(5, 10):
$$
t_1= \frac{\overrightarrow {AP_2} \cdot \vec N_1}{\overrightarrow {AB} \cdot \vec N_1}
$$
$$
t_1= \frac{\begin{bmatrix}5-(-1)\\10-(-1)\end{bmatrix} \cdot \begin{bmatrix}10\\-5\end{bmatrix}}
{\begin{bmatrix}13-(-1)\\25-(-1)\end{bmatrix} \cdot \begin{bmatrix}10\\-5\end{bmatrix} }
= \frac{\begin{bmatrix}6\\11\end{bmatrix} \cdot \begin{bmatrix}10\\-5\end{bmatrix}}
{\begin{bmatrix}14\\26\end{bmatrix} \cdot \begin{bmatrix}10\\-5\end{bmatrix} }=\frac{60+(-55)}{140+(-130)}=\frac{5}{10}=\frac{1}{2}
$$
There is another way to determine whether a line is accepted or rejected, we only need to find \(t_1, t_2, t_3\) and then find the maximum entering \(t_E\) and minimum leaving \(t_L\). After we found \(t_1\) we can proceed to the next intersection \(t_2\) on Edge 2 from P2(5, 10) to P3(10, 0):
$$
t_2= \frac{\overrightarrow {AP_2} \cdot \vec N_2}{\overrightarrow {AB} \cdot \vec N_2}
$$
$$
t_2= \frac{\begin{bmatrix}5-(-1)\\10-(-1)\end{bmatrix} \cdot \begin{bmatrix}-10\\-5\end{bmatrix}}
{\begin{bmatrix}13-(-1)\\25-(-1)\end{bmatrix} \cdot \begin{bmatrix}-10\\-5\end{bmatrix} }
= \frac{\begin{bmatrix}6\\11\end{bmatrix} \cdot \begin{bmatrix}-10\\-5\end{bmatrix}}
{\begin{bmatrix}14\\26\end{bmatrix} \cdot \begin{bmatrix}-10\\-5\end{bmatrix} }=\frac{-60+(-55)}{-140+(-130)}=\frac{-115}{-270}=\frac{23}{54}
$$
After we've found \(t_2\), we can proceed to the next intersection \(t_3\) on Edge 3 from P3(10, 0) to P1(0, 0):
$$
t_3= \frac{\overrightarrow {AP_1} \cdot \vec N_3}{\overrightarrow {AB} \cdot \vec N_3}
$$
$$
t_3= \frac{\begin{bmatrix}0-(-1)\\0-(-1)\end{bmatrix} \cdot \begin{bmatrix}0\\10\end{bmatrix}}
{\begin{bmatrix}13-(-1)\\25-(-1)\end{bmatrix} \cdot \begin{bmatrix}0\\10\end{bmatrix} }
= \frac{\begin{bmatrix}1\\1\end{bmatrix} \cdot \begin{bmatrix}0\\10\end{bmatrix}}
{\begin{bmatrix}14\\26\end{bmatrix} \cdot \begin{bmatrix}0\\10\end{bmatrix} }=\frac{0+10}{0+260}=\frac{10}{260}=\frac{1}{26}
$$
Now that we've found all \(t_1, t_2, t_3\), we can determine which is \(t_E\) and which is \(t_L\):
$$
t_1=
\begin{bmatrix}
1 \\ 2
\end{bmatrix},
t_2=
\begin{bmatrix}
23 \\ 54
\end{bmatrix},
t_3=
\begin{bmatrix}
1 \\ 26
\end{bmatrix}$$
\begin{array} {|r|r|}\hline
Edge & A & B & Line & t \\ \hline
E_1 & out & in & E & \frac{1}{2}=0.5 \\ \hline
E_2 & in & out & L & \frac{23}{54}=0.42 \\ \hline
E_3 & out & in & E & \frac{1}{26}=0.03 \\ \hline
 \end{array}
From the table above we can determine \(t_E=t_1\) and \(t_L=t_2\). Now use the rule below to determine whether line \(\overline {AB}\) is accepted or rejected:
$$
\begin{align}
&if \ t_E < t_L \rightarrow accepted\\
&if \ t_E > t_L \rightarrow rejected\\
&t_E = maximum \ entering \\
&t_L = minimum \ leaving
\end{align}
$$
The result is line \(\overline {AB}\) is rejected because \(t_E > t_L\).


Question 4

Solution:

To determine whether a polygon is convex/not and clockwise/not we can use cross product of every edge in a polygon. First of all, we need to find \( \vec E_1, \vec E_2, \vec E_3, \vec E_4, \vec E_5 \). Where \( \vec E_1 = \overrightarrow {AB} , \vec E_2 = \overrightarrow {BC} , \vec E_3 = \overrightarrow {CD} , \vec E_4 = \overrightarrow {DE} , \vec E_5 = \overrightarrow {DA} \) So:
$$

A=

\begin{bmatrix}

4 \\ 2

\end{bmatrix},

B=

\begin{bmatrix}

6 \\ 7

\end{bmatrix},

C=

\begin{bmatrix}

3 \\ 8

\end{bmatrix},

D=

\begin{bmatrix}

0 \\ 5

\end{bmatrix},

E=

\begin{bmatrix}

1 \\ 0

\end{bmatrix}

$$

$$

\vec E_1=

\begin{bmatrix}

6-4\\7-2

\end{bmatrix}=

\begin{bmatrix}

2\\5

\end{bmatrix}

$$

$$

\vec E_2=

\begin{bmatrix}

3-6\\8-7

\end{bmatrix}=

\begin{bmatrix}

-3\\1

\end{bmatrix}

$$

$$

\vec E_3=

\begin{bmatrix}

0-3\\5-8

\end{bmatrix}=

\begin{bmatrix}

-3\\-3

\end{bmatrix}

$$

$$

\vec E_4=

\begin{bmatrix}

1-0\\0-5

\end{bmatrix}=

\begin{bmatrix}

1\\-5

\end{bmatrix}

$$

$$

\vec E_5=

\begin{bmatrix}

4-1\\2-0

\end{bmatrix}=

\begin{bmatrix}

3\\2

\end{bmatrix}

$$


Now we find cross product of each pair of edges. Note that in this method, an edge vector should contain 3 variable, so just add the third variable as 0 on each edge vector:

$$

\vec E_1 \times \vec E_2=

\begin{bmatrix}

a\\b\\c

\end{bmatrix}\times

\begin{bmatrix}

x\\y\\z

\end{bmatrix}=

\begin{bmatrix}

bz-cy\\az-cx\\ay-bx

\end{bmatrix}

$$

$$

\vec E_1 \times \vec E_2=

\begin{bmatrix}

2\\5\\0

\end{bmatrix}\times

\begin{bmatrix}

-3\\1\\0

\end{bmatrix}=

\begin{bmatrix}

0-0\\0-0\\2-(-15)

\end{bmatrix}=

\begin{bmatrix}

0\\0\\17

\end{bmatrix}

$$


$$

\vec E_2 \times \vec E_3=

\begin{bmatrix}
-3\\1\\0

\end{bmatrix}\times

\begin{bmatrix}

-3\\-3\\0

\end{bmatrix}=

\begin{bmatrix}

0-0\\0-0\\9-(-3)

\end{bmatrix}=

\begin{bmatrix}

0\\0\\12

\end{bmatrix}

$$


$$

\vec E_3 \times \vec E_4=

\begin{bmatrix}
-3\\-3\\0

\end{bmatrix}\times

\begin{bmatrix}
1\\-5\\0

\end{bmatrix}=

\begin{bmatrix}

0-0\\0-0\\15-(-3)

\end{bmatrix}=

\begin{bmatrix}

0\\0\\18

\end{bmatrix}

$$


$$

\vec E_4 \times \vec E_5=

\begin{bmatrix}
1\\-5\\0

\end{bmatrix}\times

\begin{bmatrix}
3\\2\\0

\end{bmatrix}=

\begin{bmatrix}

0-0\\0-0\\2-(-15)

\end{bmatrix}=

\begin{bmatrix}

0\\0\\17

\end{bmatrix}

$$


$$

\vec E_5 \times \vec E_1=

\begin{bmatrix}
3\\2\\0

\end{bmatrix}\times

\begin{bmatrix}
2\\5\\0

\end{bmatrix}=

\begin{bmatrix}

0-0\\0-0\\15-4

\end{bmatrix}=

\begin{bmatrix}

0\\0\\11

\end{bmatrix}

$$
We can see the result of all edges pairs cross product results in positive number. Here are some rule to determine whether the polygon is convex or concave, clockwise or counter-clockwise:
$$
\begin{align}
&if \ result \ of \ all \ cross \ product > 0 \rightarrow convex \ clockwise \\
&if \ result \ of \ all \ cross \ product < 0 \rightarrow convex \ counter-clockwise \\
&if \ result \ of \ all \ cross \ product \ not \ same \rightarrow concave
\end{align}
$$
Thus, the polygon from question 4 is convex clockwise.

Comments

Post a Comment

Popular posts from this blog

2D CGA - Midtest 2014

-
Image
COMPUTER GRAPHICS AND ANIMATION MID TEST 150 minutes. Open book. No electronic devices allowed. Answer the questions below. You can score more than 100, but the maximum score is capped to 100. There are a lot of questions and you might not have enough time to answer all of them. Start by answering the questions that you think are easy to answer. The questions are not too hard to answer; if you paid attention during class, tried doing the review questions and exercises at the end of each PPT file, and did the homeworks without mindlessly copying them from someone else, you should not have too much trouble answering the questions. But should you become frustrated during the test, feel free to create your own handmade graphics on your answer sheet. The basics Explain the difference between Computer Graphics, Image Processing, and Image Interpretation. Give an example for each. (10 points) Answer Computer graphics is a field that focused on
Read more

HW 2D CGA - PPT 8 - Polygon Fill

-
Image
Question Solution: First of all, we need to know the element to be inserted into SET and AEL. The element must contain \(y_{max}\), \(x \ of \ y_{min}\), \(dx\), and \(dy\). Also carry but only in AEL, carry doesn't need to be inserted into SET. With that said, let's begin with the first polygon. Polygon 1 A(1, 6), B(5,4), C(3,1) From these 3 vertices we need to find the edges element containing \(y_{max}\), \(x \ of \ y_{min}\), \(dx\), and \(dy\). Let's take a look at edge AB , the \(y_{max}\) is 6, the \(x \ of \ y_{min}\) is 5, the \(dx\) is 4, and the \(dy\) is -2. Now if we found \(dy < 0\) we need to make it positive, by multiplying \(dx\) and \(dy\) with -1, so we got \(dx\) = -4 and \(dy\) = 2. The same rule applies with edges BC and CA. After we've found all of the elements then, we put it into the SET just like below. SET y Edges \(y_{max}\) 6 5 4 \( \rightarrow AB \) 6 5 -4 2 3 2 \(y_{min}\) 1 \( \rightarrow
Read more