javascript - 有效地获取边界框内的等距网格位置

Question

我有一个等距网格系统，其坐标从网格左手 Angular 的 [0,0] 开始(上图中显示的 Angular )，x 向图像底部递增，y 向顶部递增(所以 [0, height] 将是顶 Angular ， [width, 0] 将是菱形的底 Angular ，宽度和高度是网格的大小，即 200 x 200 正方形)

无论如何，我需要帮助的是获取图像中显示的蓝色框内包含的等距网格位置数组。没有迭代每个 x,y 屏幕位置并获得相应的网格位置(请参阅我之前提出的关于如何从屏幕位置转换为网格位置的问题 Get row/column on isometric grid.)我不确定如何有效地实现这一点。

我之前发现的一道题几乎一模一样Link here.答案是将网格渲染为每个网格正方形具有不同颜色的图像，然后检测正方形下方存在的颜色，我已经实现了这个解决方案，但速度很慢!我几乎在想检查选择框中每个像素的网格位置会更快。为什么哦，为什么 javascript 在循环时这么慢!

我真的需要一个基于我的坐标系的数学解决方案来解决这个问题，但我似乎无法想出一些可行的方法(并且处理选择框脱离网格)

如果您需要更多信息，请告诉我。

编辑:不幸的是，到目前为止所提供的答案还没有奏效，因为选择就像在方形网格上选择了一个菱形区域，实际上没有左上角和右下角可以迭代，除非我错过了要点答案？我已经优化了渲染方法，但在大量选择中，它仍然会增加明显的帧下降，因为它循环遍历所有像素检查颜色并获得相应的正方形

Answer 1

线性代数就是答案。这里有两个感兴趣的坐标系:屏幕坐标和等距坐标。将所选区域的 Angular 点从屏幕坐标转换为等距坐标将对您有很大帮助。

令 theta 为等距坐标的 x 轴和 y 轴之间的 Angular ，在屏幕上测量，单位为等距坐标中一步的像素长度。 然后

var c = Math.cos(theta/2);
var s = Math.sin(theta/2);
var origin = [oX, oY]; //the pixel coordinates of (0, 0)
var unit = 20;
var iso2Screen = function(iso) {
  var screenX = origin[0] + unit * (iso[0] * c + iso[1] * c);
  var screenY = origin[1] + unit * (iso[0] * -s + iso[1] * s);
  return [screenX, screenY];
}

反转这种关系，我们得到

var screen2Iso = function(screen) {
  var isoX = ((screen[0] - origin[0]) / c - (screen[1] - origin[1]) / s) / unit;
  var isoY = ((screen[0] - origin[0]) / c + (screen[1] - origin[1]) / s) / unit;

现在将选择框每个 Angular 的屏幕坐标转换为等距坐标，并得到最小和最大x和y。

var cornersScreen = ...//4-element array of 2-element arrays
var cornersIso = [];
for(var i = 0; i < 4; i++) {
  cornersIso.push(screen2Iso(cornersScreen[i]));
}
var minX, maxX, minY, maxY;
minX = Math.min(cornersIso[0][0], cornersIso[1][0], cornersIso[2][0], cornersIso[3][0]);
maxX = Math.max(cornersIso[0][0], cornersIso[1][0], cornersIso[2][0], cornersIso[3][0]);
minY = Math.min(cornersIso[0][1], cornersIso[1][1], cornersIso[2][1], cornersIso[3][1]);
maxY = Math.max(cornersIso[0][1], cornersIso[1][1], cornersIso[2][1], cornersIso[3][1]);

所有选定的等距点都位于等距框 [minX, maxX] x [minY, maxY] 内，但并非该框中的所有点都在选择范围内。

您可以做很多不同的事情来清除该框中不在选择中的点；我建议迭代等距 x 和 y 的整数值，将等距坐标转换为屏幕坐标，然后测试该屏幕坐标是否位于选择框内，即:

var sMinX, sMaxX, sMinY, sMaxY;
sMinX = Math.min(cornersScreen[0][0], cornersScreen[1][0], cornersScreen[2][0], cornersScreen[3][0]);
sMaxX = Math.max(cornersScreen[0][0], cornersScreen[1][0], cornersScreen[2][0], cornersScreen[3][0]);
sMinY = Math.min(cornersScreen[0][1], cornersScreen[1][1], cornersScreen[2][1], cornersScreen[3][1]);
sMaxY = Math.max(cornersScreen[0][1], cornersScreen[1][1], cornersScreen[2][1], cornersScreen[3][1]);
var selectedPoints = [];
for(var x = Math.floor(minX); x <= Math.ceil(maxX); x++) {
  for(var y = Math.floor(minY); x <= Math.ceil(maxY); y++) {
    var iso = [x,y];
    var screen = iso2Screen(iso);
    if(screen[0] >= sMinX && screen[0] <= sMaxX && screen[1] >= sMinY && screen[1] <= sMaxY) {
      selectedPoints.push(iso);
    }
  }
}