Computational Geometry - How to check if two lines intersect only at the anchor?

Question

Good guys, I need to do a show in C++ that receives a point A(x,0) a point B(x,0) that point To and B they are on the x-axis, always with y = 0.

After receiving the point To and the point B, I have to get a point C(x,y) and another D(x,y) and check if they intercept only at the anchor... Follow image to be clearer.

As shown in the image above, the dots To and B form a straight.. Then I’ll get stitches C(x,y) and D(x,y) and I need to do a program to calculate If the points intersect only at points A and B, but I don’t know how to do it.

I’m not asking for code ready, just a light as it checks if two points intersect only at points A and B...

Answer 1

There are four concepts to consider:

• Dot
• Vector
• Straight
• Triangle

All these concepts are in 2 dimensions. The point and the vector have a coordinate x and a coordinated y. A triangle is represented by 3 points.

The line can be represented as a point and a vector or as two points. To find the vector v of a line given by the points a and b, 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 straight line with a point a and a vector v that’s it:

b.x = a.x - v.x;
b.y = a.y - v.y;

Note that in both cases it is the same equation. In fact, in this second pair of equations, you could use + instead of - if you prefer or multiply v.x and v.y by the same non-zero number before summing or subtracting with the coordinates of a, because the only thing that matters here to define the point b is that it is any point on the straight as long as it is not itself a.

To simplify some calculations, you may prefer to work with normalized vectors. To create a u normalized from a vector v, you do that:

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 only works if at least one among v.x and v.y is non-zero. In this problem of yours, null vectors are not usable.

That said, what you have to do is see if point D is inside the ABC triangle or if point C is inside the ABD triangle. For this, you will already have a function more or less like this:

bool dentro(Triangulo t, Ponto p);

Or, if you’re 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 straight line always divides the plane into two parts. Therefore, point D is within the ABC triangle if all these conditions are true:

• Using A and B to split the plane, points C and D are on the same side.
• Using A and C to split the plane, points B and D are on the same side.
• Using B and C to split 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 is outside. A point on top of the line can be considered to be on both sides simultaneously (i.e., on top of the line is within the triangle).

With this, you will have a function more or less 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 dot is on, you can do something like in 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 (i.e., they form an angle of 90°), where point K is the point where the two lines meet.

The idea is you use a vector to measure this CK segment. You will then do the same with D producing a DJ straight (where J is another point on the AB straight, 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 senses. If CK and DJ feel the same way, 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 it could be that too (the vector would point to the opposite side, but in the same direction):

Vetor Vetor::perpendicular() {
    return new Vetor(-this.y, this.x);
}

Once this is done, you already have the AB line and by using point C and the perpendicular vector of the AB line, you get the CK line.

However, you still don’t know where point K is. To locate it, we use a system of equations, where the points are a, b and c, the vector of the line AB is vab, the vector perpendicular to vab is vck, r is the length of segment AK and s 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 r and s:

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 the r and two to the s. Use the one that suits you best. The one that best avoids division by zero. So, you can compare vab.x and vab.y and opt for the formula that divides into the larger one. The same occurs with vck.x and vck.y.

Finding the point K, you can create the straight CK. You do the same for D and get a point DJ where J is some other point. Note that in this case, the CK vector and DJ vector will have the same direction. There you can check the direction when comparing the signals of the components x and y vector. Equal signs are same side and different signs are opposite sides.

With this, you can finally assemble your function/method mesmo_lado and with it the function/method dentro and finally solve your problem.