선 세그먼트의 다른 두 점 사이에 점이 있는지 어떻게 확인할 수 있습니까?

선 세그먼트의 다른 두 점 사이에 점이 있는지 어떻게 확인할 수 있습니까?

2개의 점(a 및 b라고 함)이 있는 2차원 평면을 각 점에 대해 x 정수와 y 정수로 나타낸다고 가정합니다.

a와 b로 정의된 선분에 다른 점 c가 있는지 어떻게 확인할 수 있습니까?

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

다리우스 베이컨이 말하는 것처럼 (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

다음과 같은 방법이 있습니다.

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)

의 교차 제품인지 확인합니다.b-a그리고.c-a이라0합니다. 모, 든점동일상에있다것는입니다즉선이,있것입니.만약 그렇다면, 확인합니다.c는 의좌는다같습다니음과표다 사이에 a의 모래bs. x 또는 y 좌표 중 하나를 사용합니다.a그리고.b해당 축에서 분리되어 있습니다(또는 두 축에서 동일합니다.

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의 Beautiful Code의 챕터는 공선성 테스트 기능을 위한 디자인 공간을 다루고 있습니다. 유용한 배경이죠.빈센트의 답변은 이것을 개선하는 데 도움이 되었습니다.그리고 x 또는 그들의 좌표 중 하나만 테스트할 것을 제안한 사람은 헤이스였습니다; 원래 코드는and신에를 if a.x != b.x else.

(이 코드는 정수 또는 유리수를 사용하여 정확한 산술을 위해 코딩됩니다. 대신 부동 소수점 숫자를 전달하면 반올림 오류가 발생합니다.부동 좌표에서 2-d 점의 간격을 정의하는 좋은 방법이 무엇인지조차 잘 모르겠습니다.)

다음은 또 다른 접근 방식입니다.

• 두 점이 A(x1,y1)와 B(x2,y2)라고 가정합니다.
• 이러한 점을 통과하는 선의 방정식은 (x-x1)/(y-y1)=(x2-x1)/(y2-y1)입니다.(경사를 동일하게 만드는 것뿐)

점 C(x3,y3)는 다음과 같은 경우 A와 B 사이에 놓입니다.

• x3,y3는 위의 방정식을 만족시킵니다.
• x3은 x1과 x2 사이에 있고 y3은 y1과 y2 사이에 있습니다(반복 검사).

세그먼트의 길이는 중요하지 않으므로 제곱근을 사용할 필요가 없으며 정밀도가 떨어질 수 있으므로 피해야 합니다.

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)

웨지 및 도트 제품을 사용할 수 있습니다.

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

보다 기하학적인 접근법을 사용하여 다음 거리를 계산합니다.

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

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

• 세 점은 삼각형을 형성합니다 => ac+bc > ab
• 그것들은 공선이고 c는 ab 세그먼트 밖에 있습니다 => ac+bc > ab.
• 그것들은 공선이고 c는 ab 세그먼트 안에 있습니다 => ac+bc = ab

코드가 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;
}

(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

나는 사용자 커서가 특정 라인 위에 있는지 또는 근처에 있는지 감지하기 위해 html5 캔버스에서 사용하기 위해 Javascript에 이것이 필요했습니다.그래서 저는 다리우스 베이컨의 대답을 커피 대본으로 수정했습니다.

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

이것이 제가 학교에서 한 방법입니다.나는 왜 그것이 좋은 생각이 아닌지 잊었습니다.

편집:

@다리우스 베이컨: 아래 코드가 좋은 생각이 아닌 이유를 설명하는 "뷰티풀 코드" 책을 인용합니다.

#!/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()

좋아요, 선형 대수(벡터의 교차곱)와 이것은 실제(즉, 연속점 또는 부동소수점) 공간에서 작동한다는 많은 언급이 있지만 질문은 두 점이 정수로 표현되었기 때문에 교차곱은 대략적인 솔루션을 제공할 수 있지만 올바른 솔루션이 아니라고 명시했습니다.

올바른 해결책은 두 점 사이에 Bresenham의 선 알고리즘을 사용하여 세 번째 점이 선 위의 점 중 하나인지 확인하는 것입니다.알고리즘을 계산하는 것이 비효율적일 정도로 점들이 충분히 멀리 떨어져 있는 경우 (그러기 위해서는 정말 커야 할 것입니다.저는 당신이 주변을 파서 최적화를 찾을 수 있을 것이라고 확신합니다.

선분(a, b)의 임의의 점(여기서 a와 b는 벡터)은 두 벡터 a와 b의 선형 조합으로 표현될 수 있습니다.

즉, 선분(a, b)에 cli가 있는 경우:

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

양식을 해결하면 다음과 같은 이점을 얻을 수 있습니다.

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

따라서 테스트 결과는 (Python에서) 다음과 같습니다.

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)

c# From 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;
        }

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#에서 연산자 오버로딩을 통한 세그먼트 벡터의 도트 곱입니다.

포인트가 무한선에 투영되는 것을 활용하고 투영의 스칼라 양이 세그먼트에 투영되는지 여부를 사소한 것으로 알려주는 것을 관찰하는 것이 핵심입니다.우리는 퍼지 공차를 사용하기 위해 스칼라 양의 경계를 조정할 수 있습니다.

투영이 범위 내에 있으면 점에서 투영까지의 거리가 범위 내에 있는지만 테스트합니다.

교차 제품 접근 방식의 장점은 공차가 의미 있는 가치를 가지고 있다는 것입니다.

C# 버전의 Jules 답변:

public static double CalcDistanceBetween2Points(double x1, double y1, double x2, double y2)
{
    return Math.Sqrt(Math.Pow (x1-x2, 2) + Math.Pow (y1-y2, 2));
}

public static bool PointLinesOnLine (double x, double y, double x1, double y1, double x2, double y2, double allowedDistanceDifference)
{
    double dist1 = CalcDistanceBetween2Points(x, y, x1, y1);
    double dist2 = CalcDistanceBetween2Points(x, y, x2, y2);
    double dist3 = CalcDistanceBetween2Points(x1, y1, x2, y2);
    return Math.Abs(dist3 - (dist1 + dist2)) <= allowedDistanceDifference;
}

여기 제게 도움이 된 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);
    return (dotProduct < 0);
}

당신은 또한 매우 편리한 것을 사용할 수 있습니다.scikit-spatial 도서관

예를 들어, 다음을 생성할 수 있습니다.Line두 점으로 정의된 객체a그리고.b:

>>> point_a = [0, 0]
>>> point_b = [1, 0]

>>> line = Line.from_points(point_a, point_b)

그러면 당신은 그것을 사용할 수 있습니다.side_point의 방법Line포인트를 확인하기 위한 클래스c에 달려 있는line그렇지 않으면.

>>> line.side_point([0.5, 0])
0

출력이 다음과 같은 경우0그 때의 포인트c에 달려 있는line.

기울기가 같고 점이 다른 점들 사이에 있는지 확인하는 것은 어떻습니까?

지정된 점(x1, y1) 및 (x2, y2)(x2 > x1) 및 후보 점(a, b)

if (b-y1) / (a-x1) = (y2-y2) / (x2-x1) 그리고 x1 < a < x2

그런 다음 (a,b)는 (x1,y1)과 (x2,y2) 사이의 온라인에 있어야 합니다.

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;
}

점 좌표를 사용하여 해당 선 세그먼트에 대한 선 방정식을 해결한 다음 해당 점이 선 위에 있는지 여부를 확인하여 세그먼트의 경계를 확인하여 해당 점이 선의 내부인지 외부인지 여부를 확인할 수 있습니다.임계값은 공간 어딘가에 부동 소수점 값으로 정의될 가능성이 높고 정확한 임계값을 누르면 안 되기 때문에 일부 임계값을 적용할 수 있습니다.php 예제

function getLineDefinition($p1=array(0,0), $p2=array(0,0)){
    
    $k = ($p1[1]-$p2[1])/($p1[0]-$p2[0]);
    $q = $p1[1]-$k*$p1[0];
    
    return array($k, $q);
    
}

function isPointOnLineSegment($line=array(array(0,0),array(0,0)), $pt=array(0,0)){
    
    // GET THE LINE DEFINITION y = k.x + q AS array(k, q) 
    $def = getLineDefinition($line[0], $line[1]);
    
    // use the line definition to find y for the x of your point
    $y = $def[0]*$pt[0]+$def[1];

    $yMin = min($line[0][1], $line[1][1]);
    $yMax = max($line[0][1], $line[1][1]);

    // exclude y values that are outside this segments bounds
    if($y>$yMax || $y<$yMin) return false;
    
    // calculate the difference of your points y value from the reference value calculated from lines definition 
    // in ideal cases this would equal 0 but we are dealing with floating point values so we need some threshold value not to lose results
    // this is up to you to fine tune
    $diff = abs($pt[1]-$y);
    
    $thr = 0.000001;
    
    return $diff<=$thr;
    
}

언급URL : https://stackoverflow.com/questions/328107/how-can-you-determine-a-point-is-between-two-other-points-on-a-line-segment