CODEWITHSUNDEEP
algorithmc#-3.03d
AMH
AMH

Reputation: 6451

line segment using four point intersection

I have four point p0 , p1 ,p1' , p2' , each defined by x,y,z component and all lay on one line as in the figure

enter image description here

I want to get the line segment (the dashed part) result from the intersection between the four points

any suggestion , or sample code using C#

Upvotes: 0

Views: 594

Answers (2)

Random Dev
Random Dev

Reputation: 52290

This is more or less the same answer as Howard gave but pressed into C# ... I hope this helps with your code-base.

This code snippet should do the trick (finding the mid-points from your 4, but only if all are colinear) - also note I don't check for real intersection, you can do this easily youself by inspecting the answer and your points. I did not take the time and implement the Vector3D struct in a sensible manner (operators, ...) - you can do this easily too. Also note that this will work for not only 4 points but keep your diagram in mind.

private struct Vector3D
{
    public double X { get; set; }
    public double Y { get; set; }
    public double Z { get; set; }
}
static class Vectors
{
    static public double ScalProd(Vector3D v1, Vector3D v2)
    {
        return v1.X*v2.X + v1.Y*v2.Y + v1.Z*v2.Z;
    }

    static public Vector3D Minus(Vector3D v1, Vector3D v2)
    {
        return new Vector3D {X = v1.X - v2.X, Y = v1.Y - v2.Y, Z = v1.Z - v2.Z};
    }

    static public Vector3D Normalize(Vector3D v)
    {
        var len = Math.Sqrt(ScalProd(v, v));
        return new Vector3D {X = v.X/len, Y = v.Y/len, Z = v.Z/len};
    }
}

private Vector3D[]  FindIntersectionOnCoLinearVectors(params Vector3D[] input)
{
    if (input.Length < 2) throw new Exception("you need a minimum of two vectors");
    var v0 = input[0];
    var direction = Vectors.Normalize(Vectors.Minus(input[1], v0));
    Func<Vector3D, double> projectOntoLineStartingAtv0 =
        v => Vectors.ScalProd(direction, Vectors.Minus(v, v0));
    var mapped = input.OrderBy(projectOntoLineStartingAtv0).ToArray();
    return new Vector3D[] {mapped[1], mapped[2] };
}

Upvotes: 1

Howard
Howard

Reputation: 39217

You may proceed as follows:

Step 1: Transformation into a 1D-problem

  • define t(P) = (P-P0).(P1-P0) / (P1-P0).(P1-P0) where the dot denotes the scalar product
  • t is a linear measure on the line through P1 and P0
  • thus we have t(P0)=0, t(P1)=1

Step 2: Solve the problem in 1D

  • We assume t(P0') <= t(P1') (otherwise swap P0' and P1' in the following lines)
  • Now the following cases are possible
    • t(P1') < 0 => no intersection
    • 1 < t(P0') => no intersection
    • t(P0') <= 0 <= t(P1') <= 1 => intersection is segment (P0,P1')
    • t(P0') <= 0 < 1 < t(P1') => intersection is segment (P0,P1)
    • 0 <= t(P0') <= t(P1') <= 1 => intersection is segment (P0',P1')
    • 0 <= t(P0') <= 1 < t(P1') => intersection is segment (P0',P1)
  • alternatively if you are only interested in the t-values, the intersection is given by the line segment between t0 = max(0, t(P0')) and t1 = min(1, t(P1')) iff t0 <= t1

Upvotes: 0

Related Questions