[PYTHON] 점이 선분의 다른 두 점 사이에 있음을 어떻게 확인할 수 있습니까?

점이 선분의 다른 두 점 사이에 있음을 어떻게 확인할 수 있습니까?

두 점 (a와 b라고 부름)이 x 정수와 각 점에 대한 y 정수로 표현 된 2 차원 평면을 가지고 있다고 가정 해 보겠습니다.

다른 점 c가 a와 b에 의해 정의 된 선분 위에 있는지를 어떻게 결정할 수 있습니까?

나는 파이썬을 가장 많이 사용하지만 어떤 언어로든 예제가 도움이 될 것입니다.

해결법

1. ==============================

   1.Darius Bacon이 말한 것처럼 (b-a)와 (c-a)의 교차 곱이 0인지 확인하여 점 a, b 및 c가 정렬되어 있는지를 알려줍니다.

   Darius Bacon이 말한 것처럼 (b-a)와 (c-a)의 교차 곱이 0인지 확인하여 점 a, b 및 c가 정렬되어 있는지를 알려줍니다.

   그러나 c가 a와 b 사이에 있는지 알아 보려면 (b-a)와 (c-a)의 내적이 양수이고 a와 b 사이의 거리의 제곱보다 작은 지 확인해야합니다.

   최적화되지 않은 의사 코드에서 :

   def isBetween(a, b, c):
       crossproduct = (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y)
   
       # compare versus epsilon for floating point values, or != 0 if using integers
       if abs(crossproduct) > epsilon:
           return False
   
       dotproduct = (c.x - a.x) * (b.x - a.x) + (c.y - a.y)*(b.y - a.y)
       if dotproduct < 0:
           return False
   
       squaredlengthba = (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)
       if dotproduct > squaredlengthba:
           return False
   
       return True
   

2. ==============================

   2.방법은 다음과 같습니다.

   방법은 다음과 같습니다.

   def distance(a,b):
       return sqrt((a.x - b.x)**2 + (a.y - b.y)**2)
   
   def is_between(a,c,b):
       return distance(a,c) + distance(c,b) == distance(a,b)
   

3. ==============================

   3.b-a와 c-a의 교차 곱이 0인지 확인하십시오. 즉, 모든 점들이 동일 선상에 있음을 의미합니다. 일치하는 경우 c의 좌표가 a와 b 사이에 있는지 확인하십시오. 축에서 a와 b가 분리되어있는 한 x 또는 y 좌표를 사용하십시오 (또는 두 축 모두 동일합니다).

   b-a와 c-a의 교차 곱이 0인지 확인하십시오. 즉, 모든 점들이 동일 선상에 있음을 의미합니다. 일치하는 경우 c의 좌표가 a와 b 사이에 있는지 확인하십시오. 축에서 a와 b가 분리되어있는 한 x 또는 y 좌표를 사용하십시오 (또는 두 축 모두 동일합니다).

   def is_on(a, b, c):
       "Return true iff point c intersects the line segment from a to b."
       # (or the degenerate case that all 3 points are coincident)
       return (collinear(a, b, c)
               and (within(a.x, c.x, b.x) if a.x != b.x else 
                    within(a.y, c.y, b.y)))
   
   def collinear(a, b, c):
       "Return true iff a, b, and c all lie on the same line."
       return (b.x - a.x) * (c.y - a.y) == (c.x - a.x) * (b.y - a.y)
   
   def within(p, q, r):
       "Return true iff q is between p and r (inclusive)."
       return p <= q <= r or r <= q <= p
   

   이 대답은 세 가지 업데이트의 혼란이었습니다. 브라이언 헤이즈 (Brian Hayes)의 아름다운 코드 장은 공선 성 테스트 기능 (collinearity-test function) - 유용한 배경을위한 디자인 공간을 다룹니다. Vincent의 대답은이 문제를 개선하는 데 도움이되었습니다. 그리고 Hayes는 x 또는 y 좌표 중 하나만 테스트 할 것을 제안했습니다. 원래 코드는 있었고 대신 a.x! = b.x else의 위치에있었습니다.

4. ==============================

   4.다른 접근법이 있습니다.

   다른 접근법이 있습니다.

   점 C (x3, y3)는 A & B 사이에 위치합니다.

5. ==============================

   5.세그먼트의 길이는 중요하지 않으므로 제곱근을 사용할 필요가 없으므로 일부 정밀도를 잃을 수 있으므로 피하는 것이 좋습니다.

   세그먼트의 길이는 중요하지 않으므로 제곱근을 사용할 필요가 없으므로 일부 정밀도를 잃을 수 있으므로 피하는 것이 좋습니다.

   class Point:
       def __init__(self, x, y):
           self.x = x
           self.y = y
   
   class Segment:
       def __init__(self, a, b):
           self.a = a
           self.b = b
   
       def is_between(self, c):
           # Check if slope of a to c is the same as a to b ;
           # that is, when moving from a.x to c.x, c.y must be proportionally
           # increased than it takes to get from a.x to b.x .
   
           # Then, c.x must be between a.x and b.x, and c.y must be between a.y and b.y.
           # => c is after a and before b, or the opposite
           # that is, the absolute value of cmp(a, b) + cmp(b, c) is either 0 ( 1 + -1 )
           #    or 1 ( c == a or c == b)
   
           a, b = self.a, self.b             
   
           return ((b.x - a.x) * (c.y - a.y) == (c.x - a.x) * (b.y - a.y) and 
                   abs(cmp(a.x, c.x) + cmp(b.x, c.x)) <= 1 and
                   abs(cmp(a.y, c.y) + cmp(b.y, c.y)) <= 1)
   

   몇 가지 임의의 사용 예 :

   a = Point(0,0)
   b = Point(50,100)
   c = Point(25,50)
   d = Point(0,8)
   
   print Segment(a,b).is_between(c)
   print Segment(a,b).is_between(d)
   

6. ==============================

   6.보다 기하학적 인 방법을 사용하여 다음 거리를 계산하십시오.

   보다 기하학적 인 방법을 사용하여 다음 거리를 계산하십시오.

   ab = sqrt((a.x-b.x)**2 + (a.y-b.y)**2)
   ac = sqrt((a.x-c.x)**2 + (a.y-c.y)**2)
   bc = sqrt((b.x-c.x)**2 + (b.y-c.y)**2)
   

   ac + bc가 ab인지 테스트하기 :

   is_on_segment = abs(ac + bc - ab) < EPSILON
   

   세 가지 가능성이 있기 때문입니다.

7. ==============================

   7.좋아, 선형 대수학 (벡터 교차 곱셈)과 실제 (즉 연속 또는 부동 소수점) 공간에서 작동하지만이 질문은 구체적으로 두 점이 정수로 표현되므로 교차 곱이 올바르지 않다고 명시되어 있습니다. 솔루션이지만 근사 솔루션을 제공 할 수 있습니다.

   좋아, 선형 대수학 (벡터 교차 곱셈)과 실제 (즉 연속 또는 부동 소수점) 공간에서 작동하지만이 질문은 구체적으로 두 점이 정수로 표현되므로 교차 곱이 올바르지 않다고 명시되어 있습니다. 솔루션이지만 근사 솔루션을 제공 할 수 있습니다.

   올바른 해결책은 두 점 사이에 Bresenham의 선 알고리즘을 사용하고 세 번째 점이 선의 점 중 하나인지 확인하는 것입니다. 포인트가 충분히 멀어서 알고리즘 계산이 비 효과적이라면 (그리고 그 경우에는 반드시 커야합니다.) 나는 당신이 파고 들어서 최적화를 찾을 수있을 것이라고 확신합니다.

8. ==============================

   8.다음은 C ++에서 제공되는 코드를 사용하여 다른 방법을 설명합니다. 주어진 두 점, l1과 l2 사이에 선분을 표현하는 것은 간단합니다.

   다음은 C ++에서 제공되는 코드를 사용하여 다른 방법을 설명합니다. 주어진 두 점, l1과 l2 사이에 선분을 표현하는 것은 간단합니다.

   l1 + A(l2 - l1)
   

   여기서 0 <= A <= 1입니다.이 문제에 대해 더 이상 관심이 없으면 선의 벡터 표현이라고합니다. 우리는 이것의 x와 y 성분을 나눌 수 있습니다 :

   x = l1.x + A(l2.x - l1.x)
   y = l1.y + A(l2.y - l1.y)
   

   한 점 (x, y)을 취해이 두 표현식으로 대체하여 x와 y 성분을 A로 풀면 두 점에서 A에 대한 해가 같고 0 <= A <= 1이면 점이 나타납니다. A에 대한 해결은 나눗셈이 필요하고, 선분이 수평 또는 수직 일 때 0으로 나눗셈을 멈추게하는 특수한 경우가 있습니다. 최종 해결책은 다음과 같습니다.

   // Vec2 is a simple x/y struct - it could very well be named Point for this use
   
   bool isBetween(double a, double b, double c) {
       // return if c is between a and b
       double larger = (a >= b) ? a : b;
       double smaller = (a != larger) ? a : b;
   
       return c <= larger && c >= smaller;
   }
   
   bool pointOnLine(Vec2<double> p, Vec2<double> l1, Vec2<double> l2) {
       if(l2.x - l1.x == 0) return isBetween(l1.y, l2.y, p.y); // vertical line
       if(l2.y - l1.y == 0) return isBetween(l1.x, l2.x, p.x); // horizontal line
   
       double Ax = (p.x - l1.x) / (l2.x - l1.x);
       double Ay = (p.y - l1.y) / (l2.y - l1.y);
   
       // We want Ax == Ay, so check if the difference is very small (floating
       // point comparison is fun!)
   
       return fabs(Ax - Ay) < 0.000001 && Ax >= 0.0 && Ax <= 1.0;
   }
   

9. ==============================

   9.(c-a)와 (b-a) 사이의 스칼라 생성물은 길이의 곱과 동일해야합니다. 즉 벡터 (c-a)와 (b-a)가 같은 방향으로 정렬되어 있음을 의미합니다. 또한 (c-a)의 길이는 (b-a)의 길이보다 작거나 같아야합니다. 의사 코드 :

   (c-a)와 (b-a) 사이의 스칼라 생성물은 길이의 곱과 동일해야합니다. 즉 벡터 (c-a)와 (b-a)가 같은 방향으로 정렬되어 있음을 의미합니다. 또한 (c-a)의 길이는 (b-a)의 길이보다 작거나 같아야합니다. 의사 코드 :

   # epsilon = small constant
   
   def isBetween(a, b, c):
       lengthca2  = (c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y)
       lengthba2  = (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)
       if lengthca2 > lengthba2: return False
       dotproduct = (c.x - a.x)*(b.x - a.x) + (c.y - a.y)*(b.y - a.y)
       if dotproduct < 0.0: return False
       if abs(dotproduct*dotproduct - lengthca2*lengthba2) > epsilon: return False 
       return True
   

10. ==============================

    10.나는 사용자 커서가 특정 줄 위나 근처에 있는지를 탐지하기 위해 html5 캔버스에서 사용하기 위해 javascript에 이것을 필요로했다. 그래서 다리우스 베이컨 (Darius Bacon)이 주어진 답변을 수정하여 커피점 기록으로 만들었습니다.

    나는 사용자 커서가 특정 줄 위나 근처에 있는지를 탐지하기 위해 html5 캔버스에서 사용하기 위해 javascript에 이것을 필요로했다. 그래서 다리우스 베이컨 (Darius Bacon)이 주어진 답변을 수정하여 커피점 기록으로 만들었습니다.

    is_on = (a,b,c) ->
        # "Return true if point c intersects the line segment from a to b."
        # (or the degenerate case that all 3 points are coincident)
        return (collinear(a,b,c) and withincheck(a,b,c))
    
    withincheck = (a,b,c) ->
        if a[0] != b[0]
            within(a[0],c[0],b[0]) 
        else 
            within(a[1],c[1],b[1])
    
    collinear = (a,b,c) ->
        # "Return true if a, b, and c all lie on the same line."
        ((b[0]-a[0])*(c[1]-a[1]) < (c[0]-a[0])*(b[1]-a[1]) + 1000) and ((b[0]-a[0])*(c[1]-a[1]) > (c[0]-a[0])*(b[1]-a[1]) - 1000)
    
    within = (p,q,r) ->
        # "Return true if q is between p and r (inclusive)."
        p <= q <= r or r <= q <= p
    

11. ==============================

    11.여기 내가 학교에서 어떻게 했어. 왜 그것이 좋은 생각이 아닌지 까먹었습니다.

    여기 내가 학교에서 어떻게 했어. 왜 그것이 좋은 생각이 아닌지 까먹었습니다.

    편집하다:

    @Darius Bacon : 아래 코드가 왜 좋은지에 대한 설명이 포함 된 "아름다운 코드"책을 인용합니다.

    #!/usr/bin/env python
    from __future__ import division
    
    epsilon = 1e-6
    
    class Point:
        def __init__(self, x, y):
            self.x, self.y = x, y
    
    class LineSegment:
        """
        >>> ls = LineSegment(Point(0,0), Point(2,4))
        >>> Point(1, 2) in ls
        True
        >>> Point(.5, 1) in ls
        True
        >>> Point(.5, 1.1) in ls
        False
        >>> Point(-1, -2) in ls
        False
        >>> Point(.1, 0.20000001) in ls
        True
        >>> Point(.1, 0.2001) in ls
        False
        >>> ls = LineSegment(Point(1, 1), Point(3, 5))
        >>> Point(2, 3) in ls
        True
        >>> Point(1.5, 2) in ls
        True
        >>> Point(0, -1) in ls
        False
        >>> ls = LineSegment(Point(1, 2), Point(1, 10))
        >>> Point(1, 6) in ls
        True
        >>> Point(1, 1) in ls
        False
        >>> Point(2, 6) in ls 
        False
        >>> ls = LineSegment(Point(-1, 10), Point(5, 10))
        >>> Point(3, 10) in ls
        True
        >>> Point(6, 10) in ls
        False
        >>> Point(5, 10) in ls
        True
        >>> Point(3, 11) in ls
        False
        """
        def __init__(self, a, b):
            if a.x > b.x:
                a, b = b, a
            (self.x0, self.y0, self.x1, self.y1) = (a.x, a.y, b.x, b.y)
            self.slope = (self.y1 - self.y0) / (self.x1 - self.x0) if self.x1 != self.x0 else None
    
        def __contains__(self, c):
            return (self.x0 <= c.x <= self.x1 and
                    min(self.y0, self.y1) <= c.y <= max(self.y0, self.y1) and
                    (not self.slope or -epsilon < (c.y - self.y(c.x)) < epsilon))
    
        def y(self, x):        
            return self.slope * (x - self.x0) + self.y0
    
    if __name__ == '__main__':
        import  doctest
        doctest.testmod()
    

12. ==============================

    12.기음# http://www.faqs.org/faqs/graphics/algorithms-faq/에서 -> Subject 1.02 : 한 점에서 한 점까지의 거리를 어떻게 구합니까?

    기음# http://www.faqs.org/faqs/graphics/algorithms-faq/에서 -> Subject 1.02 : 한 점에서 한 점까지의 거리를 어떻게 구합니까?

    Boolean Contains(PointF from, PointF to, PointF pt, double epsilon)
            {
    
                double segmentLengthSqr = (to.X - from.X) * (to.X - from.X) + (to.Y - from.Y) * (to.Y - from.Y);
                double r = ((pt.X - from.X) * (to.X - from.X) + (pt.Y - from.Y) * (to.Y - from.Y)) / segmentLengthSqr;
                if(r<0 || r>1) return false;
                double sl = ((from.Y - pt.Y) * (to.X - from.X) - (from.X - pt.X) * (to.Y - from.Y)) / System.Math.Sqrt(segmentLengthSqr);
                return -epsilon <= sl && sl <= epsilon;
            }
    

13. ==============================

    13.다음은 저에게 도움이되는 Java 코드입니다.

    다음은 저에게 도움이되는 Java 코드입니다.

    boolean liesOnSegment(Coordinate a, Coordinate b, Coordinate  c) {
    
        double dotProduct = (c.x - a.x) * (c.x - b.x) + (c.y - a.y) * (c.y - b.y);
        if (dotProduct < 0) return true;
        return false;
    }
    

14. ==============================

    14.경사면이 동일하고 다른 지점 사이의 지점이 맞는지 확인하는 것은 어떻습니까?

    경사면이 동일하고 다른 지점 사이의 지점이 맞는지 확인하는 것은 어떻습니까?

    주어진 점 (x1, y1)과 (x2, y2) (x2> x1) 후보 점 (a, b)

    (b-y1) / (a-x1) = (y2-y2) / (x2-x1) 및 x1

    그러면 (a, b)는 (x1, y1)과 (x2, y2) 사이에 있어야합니다.

15. ==============================

    15.선분 (a, b) (a와 b는 벡터)에있는 모든 점은 두 벡터 a와 b의 선형 결합으로 표현 될 수 있습니다.

    선분 (a, b) (a와 b는 벡터)에있는 모든 점은 두 벡터 a와 b의 선형 결합으로 표현 될 수 있습니다.

    즉, c가 선분 (a, b)에 있으면 :

    c = ma + (1 - m)b, where 0 <= m <= 1
    

    m에 대해 다음을 얻습니다.

    m = (c.x - b.x)/(a.x - b.x) = (c.y - b.y)/(a.y - b.y)
    

    그래서, 우리의 테스트는 (파이썬에서)된다.

    def is_on(a, b, c):
        """Is c on the line segment ab?"""
    
        def _is_zero( val ):
            return -epsilon < val < epsilon
    
        x1 = a.x - b.x
        x2 = c.x - b.x
        y1 = a.y - b.y
        y2 = c.y - b.y
    
        if _is_zero(x1) and _is_zero(y1):
            # a and b are the same point:
            # so check that c is the same as a and b
            return _is_zero(x2) and _is_zero(y2)
    
        if _is_zero(x1):
            # a and b are on same vertical line
            m2 = y2 * 1.0 / y1
            return _is_zero(x2) and 0 <= m2 <= 1
        elif _is_zero(y1):
            # a and b are on same horizontal line
            m1 = x2 * 1.0 / x1
            return _is_zero(y2) and 0 <= m1 <= 1
        else:
            m1 = x2 * 1.0 / x1
            if m1 < 0 or m1 > 1:
                return False
            m2 = y2 * 1.0 / y1
            return _is_zero(m2 - m1)
    

16. ==============================

    16.Vector2D 클래스를 사용하는 C #의 대답

    Vector2D 클래스를 사용하는 C #의 대답

    public static bool IsOnSegment(this Segment2D @this, Point2D c, double tolerance)
    {
         var distanceSquared = tolerance*tolerance;
         // Start of segment to test point vector
         var v = new Vector2D( @this.P0, c ).To3D();
         // Segment vector
         var s = new Vector2D( @this.P0, @this.P1 ).To3D();
         // Dot product of s
         var ss = s*s;
         // k is the scalar we multiply s by to get the projection of c onto s
         // where we assume s is an infinte line
         var k = v*s/ss;
         // Convert our tolerance to the units of the scalar quanity k
         var kd = tolerance / Math.Sqrt( ss );
         // Check that the projection is within the bounds
         if (k <= -kd || k >= (1+kd))
         {
            return false;
         }
         // Find the projection point
         var p = k*s;
         // Find the vector between test point and it's projection
         var vp = (v - p);
         // Check the distance is within tolerance.
         return vp * vp < distanceSquared;
    }
    

    유의 사항

    s * s
    

    C #에서 연산자 오버로딩을 통한 세그먼트 벡터의 내적입니다.

    열쇠는 점의 무한한 선으로의 투영을 이용하고 투영의 스칼라 양이 투영이 선상에 있는지 여부를 알 수 있음을 관찰합니다. 퍼지 공차를 사용하기 위해 스칼라 수량의 범위를 조정할 수 있습니다.

    투영 범위가 경계 내에 있다면 투영 지점까지의 거리가 범위 내에 있는지 테스트합니다.

    교차 제품 접근법의 이점은 관용이 의미있는 가치를 갖는다는 것입니다.

17. ==============================

    17.쐐기 및 점으로 표시된 제품을 사용할 수 있습니다.

    쐐기 및 점으로 표시된 제품을 사용할 수 있습니다.

    def dot(v,w): return v.x*w.x + v.y*w.y
    def wedge(v,w): return v.x*w.y - v.y*w.x
    
    def is_between(a,b,c):
       v = a - b
       w = b - c
       return wedge(v,w) == 0 and dot(v,w) > 0
    

18. ==============================

    18.여기 Unity에서 C #을 사용하는 나의 해결책이 있습니다.

    여기 Unity에서 C #을 사용하는 나의 해결책이 있습니다.

    private bool _isPointOnLine( Vector2 ptLineStart, Vector2 ptLineEnd, Vector2 ptPoint )
    {
        bool bRes = false;
        if((Mathf.Approximately(ptPoint.x, ptLineStart.x) || Mathf.Approximately(ptPoint.x, ptLineEnd.x)))
        {
            if(ptPoint.y > ptLineStart.y && ptPoint.y < ptLineEnd.y)
            {
                bRes = true;
            }
        }
        else if((Mathf.Approximately(ptPoint.y, ptLineStart.y) || Mathf.Approximately(ptPoint.y, ptLineEnd.y)))
        {
            if(ptPoint.x > ptLineStart.x && ptPoint.x < ptLineEnd.x)
            {
                bRes = true;
            }
        }
        return bRes;
    }
    

from https://stackoverflow.com/questions/328107/how-can-you-determine-a-point-is-between-two-other-points-on-a-line-segment by cc-by-sa and MIT license