There are four concepts to consider:
- Point
- Vector
- Reta
- Triangle
All of these concepts are in two dimensions. The point and the vector have a x coordinate and a y coordinate. A triangle is represented by 3 points.
The line can be represented as a point and a vector or as a colon. To find the% vector of% of a line given by the points v and a , you can do this:
v.x = a.x - b.x;
v.y = a.y - b.y;
The opposite case, to find the point b from a line with a point b and a vector a is this:
b.x = a.x - v.x;
b.y = a.y - v.y;
Notice that in both cases it is the same equation. In fact, in this second pair of equations, you could use v instead of + if you prefer or multiply - and v.x by any number other than zero before adding or subtracting with the coordinates of v.y , since the only thing that matters here to define the a point is that it is any point on the line since it is not itself b .
To simplify some calculations, you may prefer to work with normalized vectors. To create a normalized% color from a a vector, you do this:
double mag = sqrt(v.x * v.x + v.y * v.y);
u.x = v.x / mag;
u.y = v.y / mag;
And note that this works only if at least one of u and v is non-zero. In this your problem, null vectors are not usable.
That said, what you have to do is see if the D point is inside the triangle ABC or if the point C is inside the triangle ABD. For this, you will already have a function something like this:
bool dentro(Triangulo t, Ponto p);
Or, if you are using classes:
bool Triangulo::dentro(Ponto p);
Now we have to see how to know if a point is inside the triangle. To do this, we can see that a line always divides the plane into two parts. Therefore, point D is within the triangle ABC if all these conditions are true:
- Using A and B to divide the plane, points C and D are on the same side.
- Using A and C to divide the plane, points B and D are on the same side.
- Using B and C to divide the plane, points A and D are on the same side.
If all of the above conditions are true, then D is inside the triangle. If at least one of them is false, it's out. A point on top of the line can be considered as being on both sides simultaneously (ie, above the line it is inside the triangle).
With this, you will have a function something like this:
bool mesmo_lado(Reta r, Ponto p1, Ponto p2);
Or so:
bool Reta::mesmo_lado(Ponto p1, Ponto p2);
To know which side of the line a point is on, you can do something like the figure below:
In this figure, points A and B form a line and there is a point C. Then there is a line CK perpendicular to line AB (ie, they form an angle of 90 °), where point K is the point where the two straight lines meet.
The idea is to use a vector to measure this CK segment. You then do the same with D producing a straight DJ (where J is another point on the line AB, but not necessarily equal to K). As a result, CK and DJ will be vectors of the same direction, but not necessarily with the same directions. If CK and DJ have the same meaning, then C and D are on the same side. If CK and DJ have opposite directions, then C and D are on different sides of the AB line.
Thus, to find the vector perpendicular to another vector:
Vetor *Vetor::perpendicular() {
return new Vetor(this.y, -this.x);
}
Or else it could be this too (the vector would point to the opposite side, but in the same direction):
Vetor Vetor::perpendicular() {
return new Vetor(-this.y, this.x);
}
When you do this, you already have the AB line and when you use the C point and the perpendicular vector of the AB line, you get the CK line.
However, you still do not know where the K point is. To find it, we use a system of equations where the points are v.x , v.y and a , line vector AB is% the length of segment AK and% of which is the length of segment CK:
k.x = a.x + r * vab.x;
k.x = c.x + s * vck.x;
k.y = a.y + r * vab.y;
k.y = c.y + s * vck.y;
Let's isolate b and c :
r = (k.x - a.x) / vab.x;
r = (k.y - a.y) / vab.y;
s = (k.x - c.x) / vck.x;
s = (k.y - c.y) / vck.y;
Note that there are two formulas for vab and two formulas for vab . Use the one that suits you best. The one that best suit is the one that best avoids division by zero. That way, you can compare vck and r and opt for the formula that divides by the greater. The same occurs with s and r .
Finding the K point, you can create the CK line. You do the same for D and get a DJ point where J is some other point. Note that in this case, the CK and DJ vector will have the same direction. Then you can check the meaning by comparing the signals of the s and r components of the vector. Equal signs are same side and different signs are opposite sides.
With this, you can finally set up your function / method s and with it the function / method vab.x and finally solve your problem.
