Wie überprüfen Sie für den Schnittpunkt zwischen Liniensegment und ein line-ray, die von einem Punkt in einem Winkel von der horizontalen?

Einem gegebenen Liniensegment, das zwei Punkte (x1,y1) und (x2,y2) ein Punkt P(x,y) und ein Winkel theta. Wie wir finden, wenn das Liniensegment und die line-ray, entspringt aus P in einem Winkel theta von der horizontalen schneidet oder nicht? Wenn Sie sich schneiden, so finden Sie den Schnittpunkt?

InformationsquelleAutor der Frage Paagalpan | 2013-01-13

  1. 20

    Lassen Sie die Beschriftung der Punkte q = (x1y1) und q + s = (x2y2). Daher s = (x2 − x1y2 − y1). Dann das problem sieht wie folgt aus:

    Wie überprüfen Sie für den Schnittpunkt zwischen Liniensegment und ein line-ray, die von einem Punkt in einem Winkel von der horizontalen?

    Lassen r = (cos θ, sin θ). Dann ist jeder Punkt auf dem Strahl durch p darstellbar ist als p + t r (für einen skalaren parameter 0 ≤ t), und jeder Punkt auf dem Liniensegment ist darstellbar als q + u s (für einen skalaren parameter 0 ≤ u ≤ 1).

    Sich die beiden geraden schneiden sich, wenn wir finden t und uso dass p + t r = q + u s:

    Wie überprüfen Sie für den Schnittpunkt zwischen Liniensegment und ein line-ray, die von einem Punkt in einem Winkel von der horizontalen?

    Sehen diese Antwortwie um diesen Punkt zu finden (oder zu bestimmen, dass es keine solche Stelle).

    Dann Ihre Liniensegment schneidet der Strahl, wenn 0 ≤ t und 0 ≤ u ≤ 1.

    InformationsquelleAutor der Antwort Gareth Rees

  2. 5

    Hier ist ein C# - code für den Algorithmus gegeben, in anderen Antworten:

        ///<summary>
    ///Returns intersection point on ray or null if there is no intersection.
    ///</summary>
    public double? GetRayToLineSegmentIntersection(Point rayOrigin, Vector rayDirection, Point point1, Point point2)
    {
        var v1 = rayOrigin - point1;
        var v2 = point2 - point1;
        var v3 = new Vector(-rayDirection.Y, rayDirection.X);


        var dot = v2 * v3;
        if (Math.Abs(dot) < 0.000001)
            return null;

        var t1 = Vector.CrossProduct(v2, v1) /dot;
        var t2 = (v1 * v3) /dot;

        if (t1 >= 0.0 && (t2 >= 0.0 && t2 <= 1.0))
            return t1;

        return null;
    }

    InformationsquelleAutor der Antwort ezolotko

  3. 3

    Dank Gareth für eine große Antwort. Hier ist die Lösung in Python implementiert. Fühlen Sie sich frei, um entfernen Sie die tests und kopieren Sie einfach fügen Sie die eigentliche Funktion. Ich habe den write-up Methoden, die hier erschienen, https://rootllama.wordpress.com/2014/06/20/ray-line-segment-intersection-test-in-2d/.

    import numpy as np

def magnitude(vector):
   return np.sqrt(np.dot(np.array(vector),np.array(vector)))

def norm(vector):
   return np.array(vector)/magnitude(np.array(vector))

def lineRayIntersectionPoint(rayOrigin, rayDirection, point1, point2):
    """
    >>> # Line segment
    >>> z1 = (0,0)
    >>> z2 = (10, 10)
    >>>
    >>> # Test ray 1 -- intersecting ray
    >>> r = (0, 5)
    >>> d = norm((1,0))
    >>> len(lineRayIntersectionPoint(r,d,z1,z2)) == 1
    True
    >>> # Test ray 2 -- intersecting ray
    >>> r = (5, 0)
    >>> d = norm((0,1))
    >>> len(lineRayIntersectionPoint(r,d,z1,z2)) == 1
    True
    >>> # Test ray 3 -- intersecting perpendicular ray
    >>> r0 = (0,10)
    >>> r1 = (10,0)
    >>> d = norm(np.array(r1)-np.array(r0))
    >>> len(lineRayIntersectionPoint(r0,d,z1,z2)) == 1
    True
    >>> # Test ray 4 -- intersecting perpendicular ray
    >>> r0 = (0, 10)
    >>> r1 = (10, 0)
    >>> d = norm(np.array(r0)-np.array(r1))
    >>> len(lineRayIntersectionPoint(r1,d,z1,z2)) == 1
    True
    >>> # Test ray 5 -- non intersecting anti-parallel ray
    >>> r = (-2, 0)
    >>> d = norm(np.array(z1)-np.array(z2))
    >>> len(lineRayIntersectionPoint(r,d,z1,z2)) == 0
    True
    >>> # Test ray 6 --intersecting perpendicular ray
    >>> r = (-2, 0)
    >>> d = norm(np.array(z1)-np.array(z2))
    >>> len(lineRayIntersectionPoint(r,d,z1,z2)) == 0
    True
    """
    # Convert to numpy arrays
    rayOrigin = np.array(rayOrigin, dtype=np.float)
    rayDirection = np.array(norm(rayDirection), dtype=np.float)
    point1 = np.array(point1, dtype=np.float)
    point2 = np.array(point2, dtype=np.float)

    # Ray-Line Segment Intersection Test in 2D
    # http://bit.ly/1CoxdrG
    v1 = rayOrigin - point1
    v2 = point2 - point1
    v3 = np.array([-rayDirection[1], rayDirection[0]])
    t1 = np.cross(v2, v1) /np.dot(v2, v3)
    t2 = np.dot(v1, v3) /np.dot(v2, v3)
    if t1 >= 0.0 and t2 >= 0.0 and t2 <= 1.0:
        return [rayOrigin + t1 * rayDirection]
    return []

if __name__ == "__main__":
    import doctest
    doctest.testmod()

    InformationsquelleAutor der Antwort Daniel Farrell

Schreibe einen Kommentar