基于散点坐标绘制Canvas外接矩形/圆形/多边形的数学方法问询

Hey there! Let's break down the math behind creating those bounding shapes for your scatter points in Canvas—super handy when you want to highlight groups of data. I'll walk you through the three shapes you mentioned: rectangles, circles, and convex polygons (aka convex hulls).

This is the simplest one—no fancy math needed, just finding extreme values:

• Math Steps:
  • Iterate through all your scatter points to find:
    • minX: The smallest x-coordinate among all points
    • maxX: The largest x-coordinate among all points
    • minY: The smallest y-coordinate among all points
    • maxY: The largest y-coordinate among all points
  • The rectangle's top-left corner is (minX, minY)
  • Width = maxX - minX, Height = maxY - minY
• Canvas Implementation:
  Just pass these values to the rect() method:

  ctx.rect(minX, minY, maxX - minX, maxY - minY);
  ctx.fill(); // or ctx.stroke()
  

  Example: If your points are [(10,20), (30,50), (5,15)], minX=5, maxX=30, minY=15, maxY=50—so the rectangle is rect(5,15,25,35).

This is the smallest circle that can contain all your points. The math has two core cases, and we typically use the recursive Welzl algorithm to compute it efficiently:

• Core Math Cases:
  1. Circle defined by two points: The two points are the diameter of the circle.
     • Center = ((x1 + x2)/2, (y1 + y2)/2)
     • Radius = sqrt((x2 - x1)² + (y2 - y1)²) / 2
  2. Circle defined by three points: Find the intersection of the perpendicular bisectors of two line segments formed by the points—this intersection is the center.
     • For points A(x1,y1), B(x2,y2), C(x3,y3):
       1. Compute midpoint of AB: M1 = ((x1+x2)/2, (y1+y2)/2)
       2. Compute slope of AB: k1 = (y2 - y1)/(x2 - x1); the perpendicular slope is -1/k1 (handle vertical/horizontal lines separately)
       3. Repeat step 1-2 for BC to get midpoint M2 and perpendicular slope k_perp2
       4. Solve the two perpendicular bisector equations to find the center (cx, cy)
       5. Radius = sqrt((cx - x1)² + (cy - y1)²)
• Welzl Algorithm Overview:
  1. If there are no points, return a circle with radius 0. If only one point, return a circle centered at that point with radius 0.
  2. Pick a random point p, recursively compute the MEC for the remaining points.
  3. If p is inside that circle, it's the MEC for all points. If not, p must lie on the edge of the new MEC—recursively compute the MEC with p added to the boundary points.
• Canvas Implementation:
  Use the arc() method once you have center and radius:

  ctx.arc(cx, cy, radius, 0, Math.PI * 2);
  ctx.fill(); // or ctx.stroke()
  

A convex hull is the smallest convex polygon that contains all your points—all points lie either on the polygon's edges or inside it. The Andrew's monotone chain algorithm is a popular, easy-to-implement method:

• Math Steps (Andrew's Algorithm):
  1. Sort Points: Sort all points by x-coordinate (and y-coordinate if x's are equal).
  2. Build Lower Hull:
     • Iterate through the sorted points, adding each to the lower hull array.
     • After adding a point, check the last three points a, b, c in the array. Use the cross product to check the turn direction:

       cross = (xb - xa) * (yc - ya) - (yb - ya) * (xc - xa)
       

       • If cross <= 0, the three points make a non-counter-clockwise turn (either clockwise or collinear)—remove b from the array and repeat the check.
  3. Build Upper Hull:
     • Iterate through the sorted points in reverse order, adding each to the upper hull array.
     • Use the same cross product check as the lower hull, removing points that cause non-counter-clockwise turns.
     • Exclude the last point of the upper hull (it duplicates the first point of the lower hull).
  4. Combine Hulls: The convex hull is the combination of the lower and upper hull arrays.
• Canvas Implementation:
  Draw the polygon by connecting the convex hull points:

  ctx.beginPath();
  convexHullPoints.forEach((point, index) => {
    if (index === 0) ctx.moveTo(point.x, point.y);
    else ctx.lineTo(point.x, point.y);
  });
  ctx.closePath();
  ctx.fill(); // or ctx.stroke()
  

Once you've calculated these values, plugging them into Canvas's drawing methods is straightforward. For convex hulls, just loop through the computed points to draw the polygon edges.

内容的提问来源于stack exchange，提问作者Sowmya