Triangle formed by straight lines

In summary, the OP tried to solve this problem using the notation y=-mx+c, but it gave the incorrect answer because the origin (0,0) lies on the graph and hence the inequality symbol y\geq0 is not satisfied.
  • #36
I deleted my precious attempt. I think this algorithm will work. It ain’t pretty. It generalizes Perok’s approach.
1) Find the longest side of the triangle (one way is define normalized direction vectors for each line and then take inner products to find the largest angle)
2) Redefine the coordinate system so that the longest side of the triangle is on the new x-axis. Notice that the triangle is now above or below the new x-axis. Also since the longest side is on the axis, both of the angles opposite to the other two sides are acute.
4) Determine if the point is above or below the new x-axis.
5) If it above the new x-axis, it needs to be below the other two lines (in the new coordinate system). If it below the new x-axis, it needs to be above the other two lines (in the new coordinate system).
 
  • Skeptical
Likes Einstein44
Physics news on Phys.org
  • #37
Frabjous said:
I deleted my precious attempt. I think this algorithm will work. It ain’t pretty. It generalizes Perok’s approach.
1) Find the longest side of the triangle (one way is define normalized direction vectors for each line and then take inner products to find the largest angle)
2) Redefine the coordinate system so that the longest side of the triangle is on the new x-axis. Notice that the triangle is now above or below the new x-axis. Also since the longest side is on the axis, both of the angles opposite to the other two sides are acute.
4) Determine if the point is above or below the new x-axis.
5) If it above the new x-axis, it needs to be below the other two lines (in the new coordinate system). If it below the new x-axis, it needs to be above the other two lines (in the new coordinate system).

But we agree this is significantly worse than the solution from the book right?
 
  • Like
Likes PeroK and Einstein44
  • #38
Office_Shredder said:
But we agree this is significantly worse than the solution from the book right?
Mine is a painful solution. With yours, I am unsure of how to setup the direction of the inequalities without drawing a figure which we were forbidden to do.
 
  • #39
Frabjous said:
Mine is a painful solution. With yours, I am unsure of how to setup the direction of the inequalities without drawing a figure which we were forbidden to do.
The idea with the vertices and seven regions can be made ultimately purely algebraic. My issue is how you arrive at that without drawing a sketch. Moreover, how exactly is the interior of a triangle defined if not from a sketch? Even if the sketch is a mental picture of the plane geometry involved.

Once you have things nailed down in 2-3 dimensions, you may have to trust to algebra when generalizing.
 
  • Like
Likes Lnewqban
  • #40
PeroK said:
The idea with the vertices and seven regions can be made ultimately purely algebraic. My issue is how you arrive at that without drawing a sketch. Moreover, how exactly is the interior of a triangle defined if not from a sketch? Even if the sketch is a mental picture of the plane geometry involved.

Once you have things nailed down in 2-3 dimensions, you may have to trust to algebra when generalizing.

The interior of the triangle is the only bounded intersection of three half spaces defined by splitting the plane by the given equations.

Yes i agree if you are given this question without having worked with polygons before like this drawing a picture is a good way to gain some intuition. This is like complaining if someone asks a question about continuous functions that doesn't permit a picture as a proof - the whole point is to take your picture, and turn it into an actual math proof.
 
  • #41
Frabjous said:
Mine is a painful solution. With yours, I am unsure of how to setup the direction of the inequalities without drawing a figure which we were forbidden to do.
I missed the book solution in post 15. It uses the vertices to determine the directions. I feel like an idiot obtuse.
 
Last edited:
  • Like
Likes Office_Shredder
  • #42
Frabjous said:
I missed the book solution in post 15. It uses the vertices to determine the directions. I feel like an idiot.

There's a lot going on in this thread. I was genuinely checking that you agreed with the book solution, since it seems easy to miss it in the conversation.
 
  • Like
Likes Frabjous
  • #43
1672720255059.png

This diagram helps understand how the logic works but importantly you do not need it to do the calculation.

We define functions ##f_1,f_2,f_3## that assign a real number to each point on the plane, where for point ##\mathbf v##, the value of ##f_i(\mathbf v)=f_i((x,y))## is that of the LHS of the ##i##-th equation in the OP, where ##x,y## are the Cartesian coordinates of ##\mathbf v##.

For each ##i\in\{1,2,3\}## and each ##u\in\mathbb R##, the level set$$S_{i}(u):= \left\{ \mathbf v\in\mathbb R^2\ :\ f_i(\mathbf v) = u\right\}$$is a straight line. For a given ##i##, all level sets are parallel. The value of ##f_i((x,y))## increases in a direction perpendicular to those lines, but we don't yet know which of the two perpendicular directions it is (eg NorthEast or SouthWest).

Define ##b_i## to be the constant on the RHS of the ##i##-th equation in the OP. So we can write the ##i##-th equation as:$$f_i((x,y)) = b_i$$The ##i##-th equation is satisfied by the level set ##S_{i}(b_i)##, ie the level set of ##f_i## on which ##f_i## gives value ##b_i##. Let's call that level set for equation ##i## the ##i##-th boundary line, because it will be a boundary of the triangle. On one side of that boundary line, ##f_i## will always give a value larger then ##b_i## and on the other side, always smaller.

For each ##i## we define ##P_{i}## to be the point of intersection for the two boundary lines that are not boundary line ##i##. Now the entire triangle lies on one side of that boundary line, or on the line, and ##P_i## is in the triangle but not on that boundary line. So the weak inequality (##\geq## or ##\leq##) version of equation ##i## that applies to ##P_i## must also be satisfied by all points in the triangle.
That is, if ##f_i(P_i)\leq b_i## then ##f_i(\mathbf v)\leq b_i## for all points ##\mathbf v## in the triangle. And the same applies if we replace ##\leq## by ##\geq##.

We test and find that:\begin{align*}
&f_1(P_1) = f_1((1.8, 0.8)) = 2\times 1.8+ 0.8 = 4.4\geq 2 = b_1\\
&f_2(P_2) = f_2((1,0)) = 2\times 1 + 3\times 0 = 2\leq 6 = b_2\\
&f_3(P_3) = f_3((0,2)) = 0 - 2 = -2 \leq 1 = b_3\\
\end{align*}For each ##i## the diagram shows as a dashed line the level set for ##f_i## that passes through point ##P_i##.

So our triangle is defined as:$$\Delta\,P_1P_2P_3 = \left\{ \mathbf v\in\mathbb R^2\ :\
f_1(\mathbf v)\geq b_1\wedge f_2(\mathbf v)\geq b_2\wedge f_3(\mathbf v)\geq b_3\right\} $$where ##\wedge## means AND.

We can then test and see that ##P## satisfies this but ##Q## and ##O## (the origin) do not.

PS the book's solution in post 15 is just a very terse - and somewhat hard to follow - version of this approach.

PPS below is some python code to automate the solution, showing it's quite straightforward and requires no diagrams to determine directions:
Python code:
import numpy as np

# matrix of coefficients from equations (LHS)
M = np.array([[2, 1],\
              [2, 3],\
              [1, -1]])
# vector of constants from equations (RHS)
b = np.array([2, 6, 1])

# function to choose the 'other two' indices, given an index i in [0, 1, 2]
def not_i(i):
    return np.where(i == 0, [1, 2], np.where(i == 1, [0, 2], [0, 1]))

# function to test whether the i-th linear function gives > or < b[i] at point (x,y)
def test_val(x, y, i):
    return np.sign(sum(M[i] * np.array([x, y])) - b[i])

# set up v to be matrix of coordinates of the three triangle vertices
v = np.array([[0.0 ,0.0],\
              [0.0, 0.0],\
              [0.0, 0.0]] )
# set up vector 'signs' to give directions of the inequalities
signs = [1, 1, 1]
# loop to find the vertices (points of intersection) and directions of inequalities
for i in [0, 1, 2]:
    v[i, :] = np.linalg.solve(M[not_i(i)], b[not_i(i)])
    signs[i] = test_val(v[i, 0], v[i, 1], i)

# using the above, define a function to test whether point (x, y) is in the triangle
def is_in_triangle(x, y):
    is_in = True
    for i in [0, 1, 2]:
        is_in = is_in and (test_val(x, y, i) == signs[i])
    return is_in
 
# apply the function to test each of the three points
print("Is (1, 1) in the triangle? ", is_in_triangle(1, 1)) # test point P
print("Is (1, 2) in the triangle? ", is_in_triangle(1, 2)) # test point Q
print("Is (0, 0) in the triangle? ", is_in_triangle(0, 0)) # test point O (origin)
And here is the output:
Code:
Is (1, 1) in the triangle?  True
Is (1, 2) in the triangle?  False
Is (0, 0) in the triangle?  False
 
Last edited:
  • Like
  • Love
Likes chwala, Lnewqban, PeroK and 1 other person
  • #44
Thanks very much for everyones contribution! I think I got it now.
 
  • Like
Likes berkeman and PeroK

Suggested for: Triangle formed by straight lines

Back
Top