Given n > 3 points P1 = (x1, y1), ..., Pn = (xn, yn) in the Cartesian plane, dev

Question

Given n > 3 points P1 = (x1, y1), ..., Pn = (xn, yn) in the Cartesian plane, develop an algorithm to check whether all points are in a triangle with the vertices of the triangle being three points from P1 = (x1, y1), ..., Pn = (xn, yn).

NOTE: For the algorithm's, not looking for full programs. Looking more along the lines of half pseudocode, half coding. See example below of bubblesort.

ALGORITHM BubbleSort(A[0.n 1]) //Sorts a given array by bubble sort //Input: An array A[0.. 1 of orderable elements //Output: Array A[0..n - 1] sorted in ascending order for i 0ton_2do for j 0 to n-2-do

Explanation / Answer

The algorithm for checking whether all the points are in a triangle within the vertices of the triangle is given below.Hope it helps..

Let the three corners be (a1, b1), (a2, b2) and (a3, b3) & co-ordinates of the given point X be (a, b)

1) Calculate the area of triangle,

i.e. Area A = [ a1(b2 – b3) + a2(b3 – b1) + a3(b1-b2)]/2

2) Area of the triangle XAB.Use same formula as above & let the area be A1.
3) Area of the triangle XBC. Let this area be A2.
4) Area of the triangle XAC. Let this area be A3.
5) If 'X' lies inside the triangle, then A1 + A2 + A3 must be equal to A.

Please rate the answer if it helped......Thankyou

Hope it helps.....

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.