现有一个多边形，需要用半径为10的圆去覆盖该多边形，有以下四点条件要满足：
1.圆与圆之间可以覆盖，但必须覆盖完整个多边形；
2.必须用最少的圆；
3.圆心坐标必须在多边形的范围里面；
4.传入参数为多边形的顶点坐标和圆的半径；
5.结果为圆心坐标的数组集合；
按该问题设计一个js算法函数去实现该功能
demo代码：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Konva Polygon with Blinking Animation</title>
<script src="https://cdn.jsdelivr.net/npm/konva@8.0.3/konva.min.js"></script>
</head>
<body>
<div id="container"></div>
<script>
var width = window.innerWidth;
var height = window.innerHeight;
var stage = new Konva.Stage({
container: 'container',
width: width,
height: height
});
var layer = new Konva.Layer();
stage.add(layer);
// 创建多边形的路径数据
const points = [
{ x: 280, y: 248 },
{ x: 316, y: 466 },
{ x: 1034, y: 584 },
{ x: 1179, y: 507 },
{ x: 1010, y: 337 },
];
// 获取多边形的顶点
const polygonPoints = points;
let pathData = "M";
for (let i = 0; i < points.length; i++) {
pathData += ` ${points[i].x} ${points[i].y}`;
if (i < points.length - 1) {
pathData += " L";
} else {
pathData += " Z";
}
}
// 创建多边形
const polygonPath = new Konva.Path({
data: pathData,
fill: "#ccc", // 初始颜色为灰色
stroke: "blue",
strokeWidth: 1,
name: "polygon_1",
});
// 添加多边形到层中
layer.add(polygonPath);
// 小圆半径
const radius = 100;
// 缓动动画：多边形颜色变为红色
const anim = new Konva.Animation(function (frame) {
/* const scale = Math.sin(frame.time * 0.002) * 0.5 + 0.5;
polygonPath.fill("rgb(" + Math.floor(255 * scale) + ", 0, 0)"); // 渐变的红色 */
// 获取一个范围在 0 到 1 之间的值
const scale = Math.sin(frame.time * 0.002) * 0.5 + 0.5;
// 计算从 #ffffff 到 #ff0000 的渐变色
const r = Math.floor(255); // 红色保持不变
const g = Math.floor(255 - 255 * scale); // 绿色从 255 逐渐变为 0
const b = Math.floor(255 - 255 * scale); // 蓝色从 255 逐渐变为 0
// 设置多边形的填充颜色
polygonPath.fill(`rgb(${r}, ${g}, ${b})`);
layer.batchDraw();
}, layer);
// 启动缓动动画
anim.start();
// 填充多边形区域的函数
function fillPolygonWithCircles(polygonPoints, radius) {
let circles = [];
// 计算多边形边界框
const minX = Math.min(...polygonPoints.map(p => p.x));
const maxX = Math.max(...polygonPoints.map(p => p.x));
const minY = Math.min(...polygonPoints.map(p => p.y));
const maxY = Math.max(...polygonPoints.map(p => p.y));
// 遍历边界框内的点，使用半径间隔的 75% 填充以减少空隙
const step = radius * 0.74;
for (let x = minX; x <= maxX; x += step) {
for (let y = minY; y <= maxY; y += step) {
const center = { x, y };
// 检查圆心是否在多边形内
if (isPointInPolygon(center.x, center.y, polygonPoints)) {
circles.push({ center, radius });
// 跳过已经覆盖的区域
y += step - 1; // 跳过已经覆盖的区域
}
}
}
return circles;
}
// 填充多边形
const circles = fillPolygonWithCircles(points, radius);
console.log('填充多边形的圆:', circles);
// 绘制圆圈
function drawCircles(circles) {
circles.forEach(circle => {
const konvaCircle = new Konva.Circle({
x: circle.center.x,
y: circle.center.y,
radius: radius,
fill: "#fff",
stroke: "blue",
dash: [5, 5],
strokeWidth: 1,
draggable: true,
globalCompositeOperation: 'source-over', // 圆形不遮盖底层线段
// fill: 'rgba(204, 204, 204, 0.5)',
});
layer.add(konvaCircle);
isScope(konvaCircle);
});
layer.batchDraw(); // 更新图层，确保绘制内容生效
}
// 网格化多边形区域，创建一个覆盖多边形的小网格
function generateGrid(polygonPoints, step) {
let grid = [];
const minX = Math.min(...polygonPoints.map(p => p.x));
const maxX = Math.max(...polygonPoints.map(p => p.x));
const minY = Math.min(...polygonPoints.map(p => p.y));
const maxY = Math.max(...polygonPoints.map(p => p.y));
for (let x = minX; x <= maxX; x += step) {
for (let y = minY; y <= maxY; y += step) {
if (isPointInPolygon(x, y, polygonPoints)) {
grid.push({ x, y });
}
}
}
return grid;
}
// 计算两点之间的距离
function distance(p1, p2) {
return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
}
// 检查一个圆形是否覆盖多个网格点
function isCircleCoverGrid(circle, grid, radius) {
let covered = [];
grid.forEach(point => {
if (distance(circle, point) <= radius) {
covered.push(point);
}
});
return covered;
}
// 贪心算法：选择圆形覆盖多边形
function greedyCoverPolygon(polygonPoints, radius) {
const step = radius; // 网格化的步长，基于圆的直径
let grid = generateGrid(polygonPoints, step); // 网格化区域
console.log(grid, 'grid');
let coveredGrid = []; // 存储已覆盖的网格
let circles = []; // 存储已选择的圆形
let circlesG = []; // 存储已选择的圆形
// 逐步选择圆形，覆盖多边形
while (coveredGrid.length < grid.length) {
let bestCircle = null;
let maxCovered = 0;
let bestCovered = [];
// 尝试选择一个圆形
for (let i = 0; i < grid.length; i++) {
const point = grid[i];
circlesG = { x: point.x, y: point.y, radius: radius };
if (!coveredGrid.includes(point)) {
let circle = { x: point.x, y: point.y, radius: radius };
// 获取该圆形可以覆盖的网格点
let covered = isCircleCoverGrid(circle, grid, radius);
// 选择覆盖最多的网格点的圆形
if (covered.length > maxCovered) {
maxCovered = covered.length;
bestCircle = circle;
bestCovered = covered;
}
}
}
// 更新已覆盖网格，并将圆形加入已选圆形中
if (bestCircle) {
circles.push(bestCircle);
bestCovered.forEach(point => {
if (!coveredGrid.includes(point)) {
coveredGrid.push(point);
}
});
}
}
return circlesG;
}
// 调用贪心算法来选择圆形覆盖多边形
const circles1 = greedyCoverPolygon(polygonPoints, radius);
// 输出选择的圆形位置
console.log('选择的圆形：', circles1);
// 计算圆形是否覆盖了多边形区域
function isPointInCircle(point, circle) {
const dx = point.x - circle.x();
const dy = point.y - circle.y();
const distance = Math.sqrt(dx * dx + dy * dy);
return distance < circle.radius();
}
// 计算一个圆形是否覆盖了多边形内的某个点
function isPointInCircle1(point, circle) {
const dx = point.x - circle.x;
const dy = point.y - circle.y;
const distance = Math.sqrt(dx * dx + dy * dy);
return distance < circle.radius;
}
// 判断点是否在多边形内部的函数 (射线法)
function isPointInPolygon(x, y, polygonPoints) {
let inside = false;
for (let i = 0, j = polygonPoints.length - 1; i < polygonPoints.length; j = i++) {
const xi = polygonPoints[i].x, yi = polygonPoints[i].y;
const xj = polygonPoints[j].x, yj = polygonPoints[j].y;
const intersect = ((yi > y) !== (yj > y)) &&
(x < (xj - xi) * (y - yi) / (yj - yi) + xi);
if (intersect) inside = !inside;
}
return inside;
}
function isScope(circle) {
// 更新拖动边界
circle.dragBoundFunc((pos) => {
let newPosX = pos.x;
let newPosY = pos.y;
// console.log(polygonPoints, 'polygonPoints');
// const circleRadius = circle.radius();
// 判断圆心是否在多边形内部
if (isPointInPolygon(newPosX, newPosY, polygonPoints)) {
// 如果圆心在多边形内部，允许拖动
return { x: newPosX, y: newPosY };
} else {
// 如果圆心超出了多边形，限制圆心到多边形内部
// 这里我们不做复杂的边界调整，只是返回原位
return circle.position(); // 保持原位置
}
});
// 用于遮住区域的功能
circle.on("dragmove", function () {
const circlePos = circle.getClientRect();
// 获取多边形路径上的点，检查哪些点被圆形遮挡
points.forEach(point => {
if (isPointInCircle(point, circle)) {
// 在圆形内部的点，阻止颜色变化
polygonPath.fill("gray"); // 被圆形遮挡的区域颜色保持灰色
} else {
// 在圆形外部的点，恢复颜色变化
polygonPath.fill("red"); // 恢复为红色
}
});
layer.batchDraw(); // 更新图层
});
}
// 绘制每一条线段
function drawPolygonEdges(points) {
const lines = [];
for (let i = 0; i < points.length; i++) {
const startPoint = points[i];
const endPoint = points[(i + 1) % points.length]; // 使得最后一个点和第一个点连接
const line = new Konva.Line({
points: [startPoint.x, startPoint.y, endPoint.x, endPoint.y],
stroke: 'blue', // 线段颜色
strokeWidth: 1, // 线段宽度
lineJoin: 'round', // 线连接处的样式
lineCap: 'round', // 线的端点样式
});
layer.add(line); // 将线段添加到图层
lines.push(line);
}
layer.batchDraw(); // 强制更新图层以渲染线段
}
// 绘制填充圆
drawCircles(circles);
// 调用函数来绘制多边形的线段
drawPolygonEdges(points);
// 将层添加到舞台
stage.add(layer);
</script>
</body>
</html>
