한 점이 선분의 다른 두 점 사이에 있는지 어떻게 확인할 수 있습니까?
각 점에 대해 x 정수와 ay 정수로 표시되는 2 개의 점 (a 및 b라고 함)이있는 2 차원 평면이 있다고 가정 해 보겠습니다.
다른 점 c가 a와 b로 정의 된 선분에 있는지 어떻게 확인할 수 있습니까?
나는 파이썬을 가장 많이 사용하지만 어떤 언어로 된 예제가 도움이 될 것입니다.
있는지 확인 외적 점은, b와 c가 일치하는 경우를 알려줍니다, 다리우스 베이컨을 알려줍니다로 (바) 및 (CA)의은 0입니다.
그러나 c가 a와 b 사이인지 알고 싶기 때문에 (ba)와 (ca) 의 내적 이 양수 이고 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의과 ' b의. 사용은 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
이 답변은 세 가지 업데이트가 엉망이었습니다. 그들로부터 가치있는 정보 : 브라이언 헤이즈의 장 에서 아름다운 코드 - 유용한 배경 공선 테스트 기능에 대한 설계 공간을 다룹니다. Vincent의 답변 은이 문제를 개선하는 데 도움이되었습니다. 그리고 x 또는 y 좌표 중 하나만 테스트 할 것을 제안한 것은 Hayes였습니다. 원래 코드는 한 and자리에 if a.x != b.x else.
다음은 또 다른 접근 방식입니다.
- 두 점이 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)
여기에 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;
}
보다 기하학적 인 접근 방식을 사용하여 다음 거리를 계산하십시오.
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
세 가지 가능성이 있기 때문입니다.
- 3 개의 점은 삼각형을 형성합니다 => ac + bc> ab
- 동일 선상에 있고 c 는 ab 세그먼트 외부에 있음 => ac + bc> ab
- 동일 선상에 있고 c 는 ab 세그먼트 내부에 있음 => ac + bc = ab
좋아, 선형 대수 (벡터의 외적)에 대한 많은 언급이 있으며 이것은 실제 (즉, 연속 또는 부동 소수점) 공간에서 작동하지만 두 점이 정수 로 표현 되었으므로 외적은 정확하지 않다고 구체적으로 언급했습니다. 대략적인 솔루션을 제공 할 수 있지만 솔루션입니다.
올바른 해결책은 두 점 사이에 Bresenham의 선 알고리즘 을 사용 하고 세 번째 점이 선의 점 중 하나인지 확인하는 것입니다. 포인트가 충분히 멀어 알고리즘 계산이 성능이 좋지 않다면 (그리고 그렇게하려면 정말 커야합니다) 저는 여러분이 주변을 파헤쳐 서 최적화를 찾을 수있을 것이라고 확신합니다.
(ca)와 (ba) 사이의 스칼라 곱은 길이의 곱과 같아야합니다 (이는 벡터 (ca)와 (ba)가 같은 방향으로 정렬되어 있음을 의미 함). 또한 (ca)의 길이는 (ba)의 길이보다 작거나 같아야합니다. 의사 코드 :
# 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 캔버스에서 사용하기 위해 자바 스크립트에 필요했습니다. 그래서 Darius Bacon이 제공 한 답변을 coffeescript로 수정했습니다.
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
제가 학교에서 한 방법은 다음과 같습니다. 좋은 생각이 아닌 이유를 잊었습니다.
편집하다:
@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()
선분 ( 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)
따라서 테스트는 다음과 같습니다 (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: How do I find the distance from a point to a line?
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;
}
Here is some Java code that worked for me:
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;
}
how about just ensuring that the slope is the same and the point is between the others?
given points (x1, y1) and (x2, y2) ( with x2 > x1) and candidate point (a,b)
if (b-y1) / (a-x1) = (y2-y2) / (x2-x1) And x1 < a < x2
Then (a,b) must be on line between (x1,y1) and (x2, y2)
An answer in C# using a Vector2D class
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;
}
Note that
s * s
is the dot product of the segment vector via operator overloading in C#
The key is taking advantage of the projection of the point onto the infinite line and observing that the scalar quantity of the projection tells us trivially if the projection is on the segment or not. We can adjust the bounds of the scalar quantity to use a fuzzy tolerance.
If the projection is within bounds we just test if the distance from the point to the projection is within bounds.
The benefit over the cross product approach is that the tolerance has a meaningful value.
You can use the wedge and dot product:
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
Here is my solution with C# in Unity.
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;
}
C# version of Jules' answer:
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;
}
'programing' 카테고리의 다른 글
| : not (: empty) CSS 선택기가 작동하지 않습니까? (0) | 2020.09.13 |
|---|---|
| "Mysql 행 크기가 너무 큼"에 대한 제한 변경 (0) | 2020.09.13 |
| __del__ 메서드는 무엇이며 어떻게 호출합니까? (0) | 2020.09.13 |
| .sql 파일을 SQLite 3으로 어떻게 가져 옵니까? (0) | 2020.09.13 |
| 403을 제공하는 MVC4 스타일 번들 (0) | 2020.09.13 |