javascript - 从数组中获取外部点并围绕它们绘制以创建最大的形状

Question

好的，伙计们，我有一堆较小的形状(所有正方形都有 4 个点，顶部、右侧、底部和左侧，每个都有一个 x 和 y)。我从所有正方形中提取了所有点的数组，如下所示:

[[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1], [2, 2], ... 等等]

可能有数百个正方形聚集在一起形成任何形状。

我想知道的是:

我将如何提取位于所有点外围的所有点，然后遍历它们，以便我可以在这些点的外部绘制一条路径，以创建所有正方形的轮廓形状一个集群。

我正在使用 javascript 和 Canvas 来绘制形状。

干杯。

Answer 1

获取外部路径的暴力方法概述(未优化!)

1. 从所有矩形的边创建线段，并将所有线段放入一个数组中。线段对象的形状可能如下所示:{id:1,x0:,y0:,x1:,y1:}

   • 红色线段:[#1,#6]、[#6,#7]、[#7,#8]、[#8,#1]
   • 蓝色线段:[#3,#4]、[#4,#10]、[#10,#9]、[#9,#3]

2. 遍历数组并找到最左边 x0 的段。如果有多个段具有最左边的 x0，则从该子集中选择具有最顶部 y0 的段。 (这是图中的标记#1)

3. 将此称为“源片段”(图中标记#1 到标记#6)。

4. 遍历数组并找到与源段相交的段(如果有)。不要针对自身测试源片段 ;-)。您可以使用下面的线-线相交 算法来查找与源线的交点。直线交点算法返回 2 条线段的交点(如果有)。 (插图中的标记#2)

5. 计算源线段的 x0,y0 与交点的 x,y 点之间的距离。您可以使用距离公式(图中标记#1 和标记#2 之间的距离) 计算距离:

   var dx = intersection.x - source.x0;
   var dy = intersection.y - source.y0;
   var distance=Math.sqrt(dx*dx+dy*dy);
   

6. 对每个段与源段执行步骤#4-#5，找到与源段最快相交的段(==距离最小)。 (这个相交线段是图中的 marker#9 到 marker#3)

7. 如果没有相交线，则使用源线的 x1,y1 并将 x1,y1 称为“交点”。 图中标记#3 和标记#4 之间有一条没有交点的线段。

8. 在交点处，您必须确定是转向相交线段的 x0,y0 还是转向它的 x1,y1。通过始终转到相交线段的 x1、y1 来“顺时针”走。

9. 交点 x,y 和相交线的 x0,y0(或 x1,y1)之间的新线段现在是新的“源线段”。 这个新的源片段是插图上的标记#2 到标记#3

   • 如果新源的末端 x,y 返回到您在步骤#2 中找到的相同原始 x,y，那么您已经求解了周长。恭喜! 当您从插图上的标记 #8 行进到标记 #1 时会发生这种情况

   • 如果不是，则使用这个新的源片段返回步骤#3。

注意:此方法将仅查找附加(接触)的矩形 -- 不会发现任何断开连接的矩形。您可能想要做的另一项任务是查看是否有任何 rect 断开连接并决定您要如何处理该断开连接的 rect。 插图上的绿色矩形未连接。

此算法将找到 2 条线段的交点(如果有):

// Get interseting point of 2 line segments (if any)
// Attribution: http://paulbourke.net/geometry/pointlineplane/
function line2lineIntersection(p0,p1,p2,p3) {

    var unknownA = (p3.x-p2.x) * (p0.y-p2.y) - (p3.y-p2.y) * (p0.x-p2.x);
    var unknownB = (p1.x-p0.x) * (p0.y-p2.y) - (p1.y-p0.y) * (p0.x-p2.x);
    var denominator  = (p3.y-p2.y) * (p1.x-p0.x) - (p3.x-p2.x) * (p1.y-p0.y);        

    // Test if Coincident
    // If the denominator and numerator for the ua and ub are 0
    //    then the two lines are coincident.    
    if(unknownA==0 && unknownB==0 && denominator==0){return(null);}

    // Test if Parallel 
    // If the denominator for the equations for ua and ub is 0
    //     then the two lines are parallel. 
    if (denominator == 0) return null;

    // If the intersection of line segments is required 
    // then it is only necessary to test if ua and ub lie between 0 and 1.
    // Whichever one lies within that range then the corresponding
    // line segment contains the intersection point. 
    // If both lie within the range of 0 to 1 then 
    // the intersection point is within both line segments. 
    unknownA /= denominator;
    unknownB /= denominator;

    var isIntersecting=(unknownA>=0 && unknownA<=1 && unknownB>=0 && unknownB<=1)

    if(!isIntersecting){return(null);}

    return({
        x: p0.x + unknownA * (p1.x-p0.x),
        y: p0.y + unknownA * (p1.y-p0.y)
    });
}