获取相交线的面积（CGPoints）

Question

我有一个 CGPoints 数组，我想找到那些构建形状的点。请看附图：

红色圆圈只是标记我有的点。

如何找到问号所在的区域？

谢谢。

Answer 1

您将不得不从第一条线段开始检查交叉点。显然，如果前两条线段相交，那么它们就是同一条线，而你的形状只是一条线，所以请忽略这种情况。当您继续沿着线段向下移动时，一旦找到相交的线段对，您就得到了您的形状。

检查线段 2 与线段 1。然后检查线段 3 与线段 2，然后检查线段 1。然后检查 4 与 3，然后 2，然后 1，等等...如果你发现线段 7 与线段 3 相交，删除线段 3 的第一个点并将其设置为您找到的交点。然后删除线段7的最后一个点，设置为你找到的交点。你有你的形状。

这是一个找到 2 条线段交点的示例方法（用 C# 编写，但它是直接数学，因此应该很容易转换为您喜欢的任何语言）。 Taken from here:

// Determines if the lines AB and CD intersect.
static bool LinesIntersect(PointF A, PointF B, PointF C, PointF D)
{
    PointF CmP = new PointF(C.X - A.X, C.Y - A.Y);
    PointF r = new PointF(B.X - A.X, B.Y - A.Y);
    PointF s = new PointF(D.X - C.X, D.Y - C.Y);

    float CmPxr = CmP.X * r.Y - CmP.Y * r.X;
    float CmPxs = CmP.X * s.Y - CmP.Y * s.X;
    float rxs = r.X * s.Y - r.Y * s.X;

    if (CmPxr == 0f)
    {
        // Lines are collinear, and so intersect if they have any overlap

        return ((C.X - A.X < 0f) != (C.X - B.X < 0f))
            || ((C.Y - A.Y < 0f) != (C.Y - B.Y < 0f));
    }

    if (rxs == 0f)
        return false; // Lines are parallel.

    float rxsr = 1f / rxs;
    float t = CmPxs * rxsr;
    float u = CmPxr * rxsr;

    return (t >= 0f) && (t <= 1f) && (u >= 0f) && (u <= 1f);
}

Answer 2

我找到了解决办法。

此函数 returns 每个区域的多边形被相交线封闭。

func intersectionOfLineFrom(p1: CGPoint, to p2: CGPoint, withLineFrom p3: CGPoint, to p4: CGPoint) -> NSValue? {
    let d: CGFloat = (p2.x - p1.x) * (p4.y - p3.y) - (p2.y - p1.y) * (p4.x - p3.x)
    if d == 0 {
        return nil
    }
    // parallel lines
    let u: CGFloat = ((p3.x - p1.x) * (p4.y - p3.y) - (p3.y - p1.y) * (p4.x - p3.x)) / d
    let v: CGFloat = ((p3.x - p1.x) * (p2.y - p1.y) - (p3.y - p1.y) * (p2.x - p1.x)) / d
    if u < 0.0 || u > 1.0 {
        return nil
    }
    // intersection point not between p1 and p2
    if v < 0.0 || v > 1.0 {
        return nil
    }
    // intersection point not between p3 and p4
    var intersection: CGPoint = CGPointZero
    intersection.x = p1.x + u * (p2.x - p1.x)
    intersection.y = p1.y + u * (p2.y - p1.y)

    return NSValue(CGPoint: intersection)
}


func intersectedPolygons(points: [CGPoint]) -> [[CGPoint]] {
    var removeIndexBelow : Int = 0
    var removeIndexAbove : Int = 0

    var resultArrays : [[CGPoint]] = [[CGPoint]]()

    for i in 1..<points.count {
        let firstLineStart = points[i-1] as CGPoint
        let firstLineEnd = points[i] as CGPoint
        for var j = points.count-1; j > i+1; j-- {
            let lastLineStart = points[j-1] as CGPoint
            let lastLineEnd = points[j] as CGPoint
            if let intersect: NSValue = self.intersectionOfLineFrom(firstLineStart, to: firstLineEnd, withLineFrom: lastLineStart, to: lastLineEnd){
                var pointsCopy = points
                let intersection = intersect.CGPointValue()
                pointsCopy[i-1] = intersection
                pointsCopy[j] = intersection
                removeIndexBelow = i
                removeIndexAbove = j
                let fullPoly = Array(pointsCopy[removeIndexBelow-1..<removeIndexAbove])
                resultArrays.append(fullPoly)
                break;
            }
        }
    }

    return resultArrays
}

获取相交线的面积（CGPoints）

Get area of intersecting line (CGPoints)

polygon

line

cgpoint

ios