我如何确定两条直线是否相交，如果相交，在x,y点处?
当前回答
如果矩形的每条边都是一条线段，并且用户绘制的部分也是一条线段，那么您只需检查用户绘制的线段是否与四条边线段相交。这应该是一个相当简单的练习，给定每个段的起点和终点。
其他回答
找到两条线段的正确交点是一项具有大量边缘情况的非简单任务。下面是一个用Java编写的、有效的、经过测试的解决方案。
本质上，在求两条线段的交点时，有三种情况会发生:
线段不相交 有一个唯一的交点 交点是另一段
注意:在代码中，我假设x1 = x2和y1 = y2的线段(x1, y1)， (x2, y2)是有效的线段。从数学上讲，线段由不同的点组成，但为了完整起见，我在这个实现中允许线段作为点。
代码是从我的github回购
/**
* This snippet finds the intersection of two line segments.
* The intersection may either be empty, a single point or the
* intersection is a subsegment there's an overlap.
*/
import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;
import java.util.ArrayList;
import java.util.List;
public class LineSegmentLineSegmentIntersection {
// Small epsilon used for double value comparison.
private static final double EPS = 1e-5;
// 2D Point class.
public static class Pt {
double x, y;
public Pt(double x, double y) {
this.x = x;
this.y = y;
}
public boolean equals(Pt pt) {
return abs(x - pt.x) < EPS && abs(y - pt.y) < EPS;
}
}
// Finds the orientation of point 'c' relative to the line segment (a, b)
// Returns 0 if all three points are collinear.
// Returns -1 if 'c' is clockwise to segment (a, b), i.e right of line formed by the segment.
// Returns +1 if 'c' is counter clockwise to segment (a, b), i.e left of line
// formed by the segment.
public static int orientation(Pt a, Pt b, Pt c) {
double value = (b.y - a.y) * (c.x - b.x) -
(b.x - a.x) * (c.y - b.y);
if (abs(value) < EPS) return 0;
return (value > 0) ? -1 : +1;
}
// Tests whether point 'c' is on the line segment (a, b).
// Ensure first that point c is collinear to segment (a, b) and
// then check whether c is within the rectangle formed by (a, b)
public static boolean pointOnLine(Pt a, Pt b, Pt c) {
return orientation(a, b, c) == 0 &&
min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) &&
min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
// Determines whether two segments intersect.
public static boolean segmentsIntersect(Pt p1, Pt p2, Pt p3, Pt p4) {
// Get the orientation of points p3 and p4 in relation
// to the line segment (p1, p2)
int o1 = orientation(p1, p2, p3);
int o2 = orientation(p1, p2, p4);
int o3 = orientation(p3, p4, p1);
int o4 = orientation(p3, p4, p2);
// If the points p1, p2 are on opposite sides of the infinite
// line formed by (p3, p4) and conversly p3, p4 are on opposite
// sides of the infinite line formed by (p1, p2) then there is
// an intersection.
if (o1 != o2 && o3 != o4) return true;
// Collinear special cases (perhaps these if checks can be simplified?)
if (o1 == 0 && pointOnLine(p1, p2, p3)) return true;
if (o2 == 0 && pointOnLine(p1, p2, p4)) return true;
if (o3 == 0 && pointOnLine(p3, p4, p1)) return true;
if (o4 == 0 && pointOnLine(p3, p4, p2)) return true;
return false;
}
public static List<Pt> getCommonEndpoints(Pt p1, Pt p2, Pt p3, Pt p4) {
List<Pt> points = new ArrayList<>();
if (p1.equals(p3)) {
points.add(p1);
if (p2.equals(p4)) points.add(p2);
} else if (p1.equals(p4)) {
points.add(p1);
if (p2.equals(p3)) points.add(p2);
} else if (p2.equals(p3)) {
points.add(p2);
if (p1.equals(p4)) points.add(p1);
} else if (p2.equals(p4)) {
points.add(p2);
if (p1.equals(p3)) points.add(p1);
}
return points;
}
// Finds the intersection point(s) of two line segments. Unlike regular line
// segments, segments which are points (x1 = x2 and y1 = y2) are allowed.
public static Pt[] lineSegmentLineSegmentIntersection(Pt p1, Pt p2, Pt p3, Pt p4) {
// No intersection.
if (!segmentsIntersect(p1, p2, p3, p4)) return new Pt[]{};
// Both segments are a single point.
if (p1.equals(p2) && p2.equals(p3) && p3.equals(p4))
return new Pt[]{p1};
List<Pt> endpoints = getCommonEndpoints(p1, p2, p3, p4);
int n = endpoints.size();
// One of the line segments is an intersecting single point.
// NOTE: checking only n == 1 is insufficient to return early
// because the solution might be a sub segment.
boolean singleton = p1.equals(p2) || p3.equals(p4);
if (n == 1 && singleton) return new Pt[]{endpoints.get(0)};
// Segments are equal.
if (n == 2) return new Pt[]{endpoints.get(0), endpoints.get(1)};
boolean collinearSegments = (orientation(p1, p2, p3) == 0) &&
(orientation(p1, p2, p4) == 0);
// The intersection will be a sub-segment of the two
// segments since they overlap each other.
if (collinearSegments) {
// Segment #2 is enclosed in segment #1
if (pointOnLine(p1, p2, p3) && pointOnLine(p1, p2, p4))
return new Pt[]{p3, p4};
// Segment #1 is enclosed in segment #2
if (pointOnLine(p3, p4, p1) && pointOnLine(p3, p4, p2))
return new Pt[]{p1, p2};
// The subsegment is part of segment #1 and part of segment #2.
// Find the middle points which correspond to this segment.
Pt midPoint1 = pointOnLine(p1, p2, p3) ? p3 : p4;
Pt midPoint2 = pointOnLine(p3, p4, p1) ? p1 : p2;
// There is actually only one middle point!
if (midPoint1.equals(midPoint2)) return new Pt[]{midPoint1};
return new Pt[]{midPoint1, midPoint2};
}
/* Beyond this point there is a unique intersection point. */
// Segment #1 is a vertical line.
if (abs(p1.x - p2.x) < EPS) {
double m = (p4.y - p3.y) / (p4.x - p3.x);
double b = p3.y - m * p3.x;
return new Pt[]{new Pt(p1.x, m * p1.x + b)};
}
// Segment #2 is a vertical line.
if (abs(p3.x - p4.x) < EPS) {
double m = (p2.y - p1.y) / (p2.x - p1.x);
double b = p1.y - m * p1.x;
return new Pt[]{new Pt(p3.x, m * p3.x + b)};
}
double m1 = (p2.y - p1.y) / (p2.x - p1.x);
double m2 = (p4.y - p3.y) / (p4.x - p3.x);
double b1 = p1.y - m1 * p1.x;
double b2 = p3.y - m2 * p3.x;
double x = (b2 - b1) / (m1 - m2);
double y = (m1 * b2 - m2 * b1) / (m1 - m2);
return new Pt[]{new Pt(x, y)};
}
}
下面是一个简单的用法示例:
public static void main(String[] args) {
// Segment #1 is (p1, p2), segment #2 is (p3, p4)
Pt p1, p2, p3, p4;
p1 = new Pt(-2, 4); p2 = new Pt(3, 3);
p3 = new Pt(0, 0); p4 = new Pt(2, 4);
Pt[] points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
Pt point = points[0];
// Prints: (1.636, 3.273)
System.out.printf("(%.3f, %.3f)\n", point.x, point.y);
p1 = new Pt(-10, 0); p2 = new Pt(+10, 0);
p3 = new Pt(-5, 0); p4 = new Pt(+5, 0);
points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
Pt point1 = points[0], point2 = points[1];
// Prints: (-5.000, 0.000) (5.000, 0.000)
System.out.printf("(%.3f, %.3f) (%.3f, %.3f)\n", point1.x, point1.y, point2.x, point2.y);
}
C和Objective-C
基于Gareth Rees的回答
const AGKLine AGKLineZero = (AGKLine){(CGPoint){0.0, 0.0}, (CGPoint){0.0, 0.0}};
AGKLine AGKLineMake(CGPoint start, CGPoint end)
{
return (AGKLine){start, end};
}
double AGKLineLength(AGKLine l)
{
return CGPointLengthBetween_AGK(l.start, l.end);
}
BOOL AGKLineIntersection(AGKLine l1, AGKLine l2, CGPoint *out_pointOfIntersection)
{
// http://stackoverflow.com/a/565282/202451
CGPoint p = l1.start;
CGPoint q = l2.start;
CGPoint r = CGPointSubtract_AGK(l1.end, l1.start);
CGPoint s = CGPointSubtract_AGK(l2.end, l2.start);
double s_r_crossProduct = CGPointCrossProductZComponent_AGK(r, s);
double t = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), s) / s_r_crossProduct;
double u = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), r) / s_r_crossProduct;
if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
{
if(out_pointOfIntersection != NULL)
{
*out_pointOfIntersection = CGPointZero;
}
return NO;
}
else
{
if(out_pointOfIntersection != NULL)
{
CGPoint i = CGPointAdd_AGK(p, CGPointMultiply_AGK(r, t));
*out_pointOfIntersection = i;
}
return YES;
}
}
CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
CGPoint CGPointSubtract_AGK(CGPoint p1, CGPoint p2)
{
return (CGPoint){p1.x - p2.x, p1.y - p2.y};
}
CGPoint CGPointAdd_AGK(CGPoint p1, CGPoint p2)
{
return (CGPoint){p1.x + p2.x, p1.y + p2.y};
}
CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
CGPoint CGPointMultiply_AGK(CGPoint p1, CGFloat factor)
{
return (CGPoint){p1.x * factor, p1.y * factor};
}
许多函数和结构都是私有的，但是你应该很容易就能知道发生了什么。 这是公开的在这个回购https://github.com/hfossli/AGGeometryKit/
上面有很多解决方案，但我认为下面的解决方案很简单，很容易理解。
矢量AB和矢量CD相交当且仅当
端点a和b在线段CD的两边。 端点c和d在线段AB的对边。
更具体地说，a和b在线段CD的对面当且仅当两个三元组中有一个是逆时针顺序的。
Intersect(a, b, c, d)
if CCW(a, c, d) == CCW(b, c, d)
return false;
else if CCW(a, b, c) == CCW(a, b, d)
return false;
else
return true;
这里的CCW代表逆时针，根据点的方向返回真/假。
来源:http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf 第二页
基于@Gareth Rees的回答，Python版本:
import numpy as np
def np_perp( a ) :
b = np.empty_like(a)
b[0] = a[1]
b[1] = -a[0]
return b
def np_cross_product(a, b):
return np.dot(a, np_perp(b))
def np_seg_intersect(a, b, considerCollinearOverlapAsIntersect = False):
# https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282
# http://www.codeproject.com/Tips/862988/Find-the-intersection-point-of-two-line-segments
r = a[1] - a[0]
s = b[1] - b[0]
v = b[0] - a[0]
num = np_cross_product(v, r)
denom = np_cross_product(r, s)
# If r x s = 0 and (q - p) x r = 0, then the two lines are collinear.
if np.isclose(denom, 0) and np.isclose(num, 0):
# 1. If either 0 <= (q - p) * r <= r * r or 0 <= (p - q) * s <= * s
# then the two lines are overlapping,
if(considerCollinearOverlapAsIntersect):
vDotR = np.dot(v, r)
aDotS = np.dot(-v, s)
if (0 <= vDotR and vDotR <= np.dot(r,r)) or (0 <= aDotS and aDotS <= np.dot(s,s)):
return True
# 2. If neither 0 <= (q - p) * r = r * r nor 0 <= (p - q) * s <= s * s
# then the two lines are collinear but disjoint.
# No need to implement this expression, as it follows from the expression above.
return None
if np.isclose(denom, 0) and not np.isclose(num, 0):
# Parallel and non intersecting
return None
u = num / denom
t = np_cross_product(v, s) / denom
if u >= 0 and u <= 1 and t >= 0 and t <= 1:
res = b[0] + (s*u)
return res
# Otherwise, the two line segments are not parallel but do not intersect.
return None
如果矩形的每条边都是一条线段，并且用户绘制的部分也是一条线段，那么您只需检查用户绘制的线段是否与四条边线段相交。这应该是一个相当简单的练习，给定每个段的起点和终点。
