有效地获取边界框中的等距网格位置 [英] Efficiently getting isometric grid positions within a bounding box

问题描述

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

I have an isometric grid system who's coordinates start from [0,0] in the left hand corner of the grid (The corner shown in the above image) with x incrementing towards the bottom of the image and y incrementing towards the top (so [0, height] would be the top corner and [width, 0] would be the bottom corner in a diamond shape with width and height being the size of the grid ie. 200 x 200 squares)

无论如何，我需要获得的帮助是获取图像中所示蓝色框中包含的等轴测网格位置的数组.缺少对每个x，y屏幕pos进行迭代并获得相应网格位置的信息(请参阅我之前提出的有关如何从屏幕位置转换为网格位置的问题

Anyways what I need help with is getting an array of isometric grid positions that are contained within the blue box shown in the image. Short of iterating over every x,y screen pos and getting the corresponding grid position (See this question I posed earlier on how to convert from a screen position to a grid positon Get row/column on isometric grid.) i'm not sure how to achieve this effeciently.

我之前发现一个问题，几乎完全相同在此处链接.答案是渲染网格对于每个网格正方形具有不同颜色的图像，然后检测该正方形下面存在什么颜色，我已经实现了此解决方案，但是速度很慢！我几乎在考虑检查选择框中每个像素的网格位置会更快.为什么哦，为什么javascript循环这么慢！

There was a question I found earlier that is almost exactly the same Link here. The answer was to render the grid to an image with different colors for each grid square and then detect what colors were present under the square, I have implemented this solution but it is quite slow! I'm almost thinking checking the grid position for each pixel in the selection box would be faster. Why oh why is javascript so slow at looping!

我确实需要基于我的坐标系来解决此问题的数学方法，但是我似乎无法想出任何可行的方法(并且也可以处理选择框).

I really need a mathematical solution to this problem based on my coordinate system but I can't seem to come up with something that works (and handles the selection box going off the grid as well)

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

Please let me know if you need more information.

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

Unfortunately the supplied answers haven't worked so far, as the selection is like having a diamond selected area on a square grid, there is really no top left, bottom right corner to iterate through unless I missed the point of the answers? I have optimized the render approach but on a large selection, it still adds a noticeable drop in frames as it loops through all the pixel checking color and getting the corresponding square

推荐答案

线性代数就是答案.这里有两个感兴趣的坐标系:屏幕坐标和等距坐标.将选定区域的角从屏幕坐标转换为等轴坐标将极大地帮助您.

Linear algebra is the answer. There are two coordinate systems of interest here: screen coordinates and isometric coordinates. Converting the corners of the selected region from screen coordinates to isometric coordinates will greatly help you.

让theta是在屏幕上测量的等轴测坐标的x轴和y轴之间的角度，单位是在等轴测坐标中一步的像素长度. 然后

Let theta be the angle between the x and y axes of the isometric coordinates, measured on the screen and unit be the pixel length of one step in the isometric coordinates. Then

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];
}

颠倒这种关系，我们得到

Inverting this relationship, we get

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;

现在将选择框每个角的屏幕坐标转换为等轴坐标，并获得最小和最大x和y.

Now convert the screen coordinates of each corner of the selection box to isometric coordinates and get the minimum and maximum x and 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]内，但并非该框中的所有点都位于选择区之内.

All the selected isometric points lie inside of the isometric box [minX, maxX] x [minY, maxY], but not all of the points in that box are inside the selection.

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

You could do a lot of different things to weed out the points in that box that are not in the selection; I'd suggest iterating over integer values of the isometric x and y, converting the isometric coordinates to screen coordinates, and then testing to see if that screen coordinate lies within the selection box, to wit:

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);
    }
  }
}

这篇关于有效地获取边界框中的等距网格位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！