I have a list of two-dimensional points and I want to obtain which of them fall within a semi-circle.
我有一个二维点列表,我想获得它们中的哪一个属于半圆。
Originally, the target shape was a rectangle aligned with the x and y axis. So the current algorithm sorts the pairs by their X coord and binary searches to the first one that could fall within the rectangle. Then it iterates over each point sequentially. It stops when it hits one that is beyond both the X and Y upper-bound of the target rectangle.
最初,目标形状是与x和y轴对齐的矩形。因此,当前算法通过它们的X坐标和二进制搜索对这些对进行排序,以便第一个可以落入矩形内。然后它按顺序迭代每个点。当它击中超出目标矩形的X和Y上限的那个时,它会停止。
This does not work for a semi-circle as you cannot determine an effective upper/lower x and y bounds for it. The semi-circle can have any orientation.
这不适用于半圆,因为您无法确定它的有效上/下x和y边界。半圆可以具有任何方向。
Worst case, I will find the least value of a dimension (say x) in the semi-circle, binary search to the first point which is beyond it and then sequentially test the points until I get beyond the upper bound of that dimension. Basically testing an entire band's worth of points on the grid. The problem being this will end up checking many points which are not within the bounds.
最糟糕的情况是,我会在半圆中找到维度(比如x)的最小值,二元搜索到超出它的第一个点,然后依次测试这些点,直到我超出该维度的上限。基本上测试整个乐队在网格上的价值点。这样的问题最终将检查许多不在范围内的点。
11 个解决方案
#1
Checking whether a point is inside or outside a semi-circle (or a rectangle for that matter) is a constant-time operation.
检查点是在半圆内部还是外部(或者对于该问题的矩形)是恒定时间操作。
Checking N points lie inside or outside a semi-circle or rectangle is O(N).
检查位于半圆或矩形内部或外部的N个点是O(N)。
Sorting your N points is O(N*lg(N)).
对N点进行排序为O(N * lg(N))。
It is asymptotically faster to test all points sequentially than it is to sort and then do a fast culling of the points based on a binary search.
按顺序测试所有点比逐行排序然后基于二进制搜索快速剔除点逐渐快。
This may be one of those times where what seems fast and what is fast are two different things.
这可能是那些看似快速而快速的东西是两个不同的东西之一。
EDIT
There's also a dead-simple way to test containment of a point in the semi-circle without mucking about with rotations, transformations, and the like.
还有一种简单的方法来测试半圆中一个点的包含,而不会在旋转,变换等情况下进行扫描。
Represent the semi-circle as two components:
将半圆表示为两个组成部分:
- a line segment from point a to b representing the diameter of the semi-circle
- an orientation of either left-of or right-of indicating that the semi-circle is either to the left or right of line segment ab when traveling from a to b
从a点到b点的线段表示半圆的直径
左侧或右侧的方向,指示当从a到b行进时,半圆是线段ab的左侧或右侧
You can exploit the right-hand rule to determine if the point is inside the semicircle.
您可以利用右手规则来确定该点是否在半圆内。
Then some pseudo-code to test if point p is in the semi-circle like:
然后一些伪代码来测试点p是否在半圆中如下:
procedure bool is_inside:
radius = distance(a,b)/2
center_pt = (a+b)/2
vec1 = b - center_pt
vec2 = p - center_pt
prod = cross_product(vec1,vec2)
if orientation == 'left-of'
return prod.z >= 0 && distance(center_pt,p) <= radius
else
return prod.z <= 0 && distance(center_pt,p) <= radius
This method has the added benefit of not using any trig functions and you can eliminate all square-roots by comparing to the squared distance. You can also speed it up by caching the 'vec1' computation, the radius computation, center_pt computation, and reorder a couple of the operations to bail early. But I was trying to go for clarity.
此方法具有不使用任何触发函数的额外好处,您可以通过与平方距离进行比较来消除所有平方根。您还可以通过缓存'vec1'计算,半径计算,center_pt计算以及重新排序几个操作来提前保释来加速它。但我试图澄清。
The 'cross_product' returns an (x,y,z) value. It checks if the z-component is positive or negative. This can also be sped up by not using a true cross product and only calculating the z-component.
'cross_product'返回(x,y,z)值。它检查z分量是正还是负。这也可以通过不使用真正的交叉乘积并仅计算z分量来加速。
#2
First, translate & rotate the semi-circle so that one end is on the negative X-axis, and the other end is on the positive X-axis, centered on the origin (of course, you won't actually translate & rotate it, you'll just get the appropriate numbers that would translate & rotate it, and use them in the next step).
首先,平移和旋转半圆,使一端位于负X轴上,另一端位于正X轴上,以原点为中心(当然,您实际上不会平移和旋转它) ,你只需得到适当的数字就可以翻译并旋转它,并在下一步中使用它们。
Then, you can treat it like a circle, ignoring all negative y-values, and just test using the square root of the sum of the squares of X & Y, and see if it's less than or equal to the radius.
然后,您可以将其视为圆形,忽略所有负y值,然后使用X和Y的平方和的平方根进行测试,并查看它是否小于或等于半径。
#3
"Maybe they can brute force it since they have a full GPU dedicated to them."
“也许他们可以蛮力,因为他们拥有专用于他们的完整GPU。”
If you have a GPU at your disposal, then there are more ways to do it. For example, using a stencil buffer:
如果您拥有GPU,那么有更多方法可以实现。例如,使用模板缓冲区:
- clear the stencil buffer and set the stencil operation to increment
- render your semicircle to the stencil buffer
- render your points
- read back the pixels and check the values at your points
- the points that are inside the semicircle would have been incremented twice.
清除模板缓冲区并将模板操作设置为递增
将半圆渲染到模板缓冲区
渲染你的观点
读回像素并检查各点的值
半圆内的点会增加两次。
This article describes how stencil buffers can be used in OpenGL.
本文介绍如何在OpenGL中使用模板缓冲区。
#4
If there's a standard algorithm for doing this, I'm sure someone else will come up with it, but if not: you could try sorting the points by distance from the center of the circle and iterating over only those whose distance is less than the semicircle's radius. Or if computing distance is expensive, I'd just try finding the bounding box of the semicircle (or even the bounding square of the circle of which the semicircle is part) and iterating over the points in that range. To some extent it depends on the distribution of the points, i.e. do you expect most of them or only a small fraction of them to fall within the semicircle?
如果有这样做的标准算法,我相信其他人会提出它,但如果没有:你可以尝试按距离圆心的距离对点进行排序,并仅迭代距离小于圆的中心的点。半圆的半径。或者如果计算距离很贵,我只是尝试找到半圆的边界框(或者甚至是半圆所在的圆的边界正方形)并迭代该范围内的点。在某种程度上,它取决于点的分布,即你是否期望它们中的大多数或只有一小部分落在半圆内?
#5
You can find points in a circle and points on one side of a given slope, right?
您可以在一个圆圈中找到点,并在给定斜坡的一侧找到点,对吧?
Just combine the two.
只需将两者结合起来。
#6
Here's part of a function I wrote do get a cone firing arc for a weapon in a tile based game.
这是我写的一个函数的一部分,在基于磁贴的游戏中为武器获得锥形射击弧。
float lineLength;
float lineAngle;
for(int i = centerX - maxRange; i < centerX + maxRange + 1; i++){
if(i < 0){
continue;
}
for(int j = centerY - maxRange; j < centerY + maxRange + 1; j++){
if(j < 0){
continue;
}
lineLength = sqrt( (float)((centerX - i)*(centerX - i)) + (float)((centerY - j)*(centerY - j)));
lineAngle = lineAngles(centerX, centerY, forwardX, forwardY, centerX, centerY, i, j);
if(lineLength < (float)maxRange){
if(lineAngle < arcAngle){
if( (float)minRange <= lineLength){
AddToHighlightedTiles(i,j);
}
}
}
}
}
The variables should be self explanatory and the line angles function takes 2 lines and finds the angle between them. The forwardX and forwardY is just one tile in the correct direction from the center X and Y based on what angle you're pointing in. Those can be gotten easily with a switch statement.
变量应该是自解释的,线角度函数需要2行并找到它们之间的角度。 forwardX和forwardY只是从中心X和Y开始的正确方向上的一个图块,基于您指向的角度。使用switch语句可以轻松获得这些图块。
float lineAngles(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
int a = x2 - x1;
int b = y2 - y1;
int c = x4 - x3;
int d = y4 - y3;
float ohSnap = ( (a * c) + (b * d) )/(sqrt((float)a*a + b*b) * sqrt((float)c*c + d*d) );
return acos(ohSnap) * 180 / 3.1415926545f;
}
#7
- translate the center of the arc to the origin
- compute angle between ordinate axis and end points of radii of semi-cirlce
- translate the point in question by same dx,dy
-
compute distance from origin to translated x,y of point, if d > radius of circle/arc eliminate
如果d>圆/弧的半径消除,则计算从原点到平移的x,y的距离
- compute angle between ordinate axis and end point
- if angle is not between starting and ending arc of semi-cirlce, eliminate
计算纵坐标轴和终点之间的角度
如果角度不在半螺旋的起始和结束弧之间,则消除
points remaning should be inside semi-circle
点重新应该在半圆内
将弧的中心转换为原点
计算纵坐标轴和半螺旋半径终点之间的角度
用相同的dx,dy翻译有问题的点
#8
I guess someone found the same solution as me here but I have no code to show as its pretty far in my memory...
我想有人在这里找到了和我一样的解决方案,但我没有代码可以显示它在我的记忆中相当远......
I'd do it by steps...
1. I'd look if i'm within a circle... if yes look on which side of the circle.
2. By drawing a normal vector that come from the vector made by the semi-sphere. I could know if I'm behind or in front of the vector...and if you know which side is the semi sphere and which side is the void...It will be pretty damn easy to find if you're within the semi sphere. You have to do the dot product.
我是按步骤做的...... 1.我会看看我是否在一个圆圈内...如果是的话,看看圆圈的哪一边。 2.通过绘制来自半球形矢量的法向量。我可以知道我是在后面还是在矢量前面......如果你知道哪一侧是半球形,哪一侧是空洞...如果你在内部那将是非常容易找到的半球形。你必须做点积。
I'm not sure if it's clear enough but the test shouldn't be that hard to do...In the end you have to look for a negative or positive value...if it's 0 you're on the vector of the semisphere so it's up to you to say if it's outside or inside the semi-sphere.
我不确定它是否足够清楚,但测试不应该那么难......最后你必须寻找一个负面或正面的值...如果它是0,你就是在半球所以你可以说它是在半球之外还是半球之内。
#9
The fastest way to do this will depend on your typical data. If you have real-world data to look at, do that first. When points are outside the semi-circle, is it usually because they are outside the circle? Are your semi-circles typically thin pie slices?
最快的方法取决于您的典型数据。如果您要查看真实数据,请先执行此操作。当点在半圆之外时,通常是因为它们在圆外吗?你的半圆圈通常是薄饼片吗?
There are several ways to do this with vectors. You can scale the circle to a unit circle and use cross-products and look at the resultant vectors. You can use dot-products and see how the prospective point lands on the other vectors.
使用矢量有几种方法可以做到这一点。您可以将圆缩放为单位圆并使用交叉积并查看合成矢量。您可以使用点积,看看预期点如何落在其他向量上。
If you want something really easy to understand, first check to make sure it's inside the circle, then get the angle and make sure it's between the angle of the two vectors that dictate the semi-circle.
如果你想要一些非常容易理解的东西,首先检查以确保它在圆圈内,然后获得角度并确保它在两个矢量的角度之间,这决定了半圆。
Edit: I had forgotten that a semicircle is always half a circle. I was thinking of any arbitrary section of a circle.
编辑:我忘记了半圆总是半圈。我在想一个圆圈的任意部分。
Now that I have remembered what a semicircle is, here's how I would do that. It's similar to stbuton's solution, but it represents the semicircle differently.
既然我记得半圆是什么,我就是这样做的。它与stbuton的解决方案类似,但它以不同的方式表示半圆。
I'd represent the semicircle as the unit vector that bisects the semicircle. You can easily get that from either one of the vectors that indicate the boundary of the semicircle (because they are 90 degrees away from the representation) by swapping x and y and negating one of them.
我将半圆表示为将半圆一分为二的单位向量。您可以通过交换x和y并取消其中一个来轻松地从指示半圆边界的任何一个向量(因为它们与表示相距90度)中得到它。
Now you just cross the vector created by subtracting the point to be tested from the circle's center. The sign of z tells you whether the point is in the semicircle, and the length of z can be compared against the radius.
现在,您只需越过通过从圆的中心减去要测试的点而创建的向量。 z的符号告诉您该点是否在半圆中,并且z的长度可以与半径进行比较。
I did all the physics for Cool Pool (from Sierra Online). It's all done in vectors and it's filled with dots and crosses. Vectors solutions are fast. Cool Pool was able to run on a P60, and did reasonable breaks and even spin.
我做了Cool Pool的所有物理学(来自Sierra Online)。这一切都是在矢量中完成的,它充满了点和十字架。矢量解决方案很快。 Cool Pool能够在P60上运行,并且做了合理的休息甚至旋转。
Note: For solutions where you're checking sqrt(xx+yy), don't even do the sqrt. Instead, keep the square of the radius around and compare against that.
注意:对于您正在检查sqrt(xx + yy)的解决方案,请不要执行sqrt。相反,保持半径的平方并与之进行比较。
#10
It would appear that a simple scheme will work here.
这似乎是一个简单的方案。
-
Reduce the number of points in the set, by first computing the convex hull. Only the points on the convex hull will contribute to any interaction with any convex bounding shape. So retain only the subset of points on the perimeter of the hull.
通过首先计算凸包来减少集合中的点数。只有凸包上的点才会促成与任何凸边界形状的任何相互作用。因此,仅保留船体周边的点子集。
-
It can easily be argued that the minimal radius bounding semi-circle must have one edge (two points) of the convex hull coincident along the diameter of the semi-circle. I.e., if some edge of the hull does not lie in the diameter, then there exists a different semi-circle with smaller diameter that contains the same set of points.
可以很容易地认为,最小半径边界半圆必须使凸包的一个边(两个点)沿着半圆的直径重合。即,如果船体的某些边缘不在直径中,则存在具有较小直径的不同半圆,其包含相同的点集。
-
Test each edge in sequence. (A convex hull often has relatively few edges, so this will go quickly.) Now it becomes a simple 1-d minimization problem. If we choose to assume the edge in question lies on the diameter, then we merely need to find the center of the sphere. It must lie along the current line which we are considering to be the diameter. So as a function of the position of the point along the current diameter, just find the point which lies farthest away from the nominal center. By minimizing that distance, we find the radius of the minimal semi-circle along that line as a diameter.
按顺序测试每个边缘。 (凸包通常具有相对较少的边缘,因此这将很快。)现在它成为一个简单的一维最小化问题。如果我们选择假设有问题的边缘在于直径,那么我们只需要找到球体的中心。它必须位于我们考虑为直径的当前线上。因此,作为沿当前直径的点位置的函数,只需找到距离标称中心最远的点。通过最小化该距离,我们发现沿该线的最小半圆的半径作为直径。
Now, just choose the best of the possible semi-circles found over all edges of the convex hull.
现在,只需选择在凸包的所有边缘上找到的最好的半圆。
#11
If your points have integer co-ordinates, the fastest solution may be a lookup table. Since a semicircle is convex, for each y co-ordinate, you get a fixed range of x, so each entry in your lookup table gives maximum and minimum X co-ordinates.
如果您的点具有整数坐标,则最快的解决方案可能是查找表。由于半圆是凸的,对于每个y坐标,你得到一个固定的x范围,因此查找表中的每个条目都给出了最大和最小的X坐标。
Of course you still need to precalculate the table, and if your semicircle isn't fixed, you may be doing that a lot. That said, this is basically one part of what would once have been done to render a semicircle - the full shape would be rendered as a series of horizontal spans by repeatedly calling a horizontal line drawing function.
当然你仍然需要预先计算表格,如果你的半圆没有固定,你可能会做很多事情。也就是说,这基本上是渲染半圆的一部分 - 通过重复调用水平线绘制函数,整个形状将呈现为一系列水平跨度。
To calculate the spans in the first place (if you need to do it repeatedly), you'd probably want to look for an old copy of Michael Abrash's Zen of Graphics Programming. That described Bresenhams well-known line algorithm, and the not-so-well-known Hardenburghs circle algorithm. It shouldn't be too hard to combine the span-oriented versions of the two to quickly calculate the spans for a semi-circle.
要首先计算跨度(如果需要反复进行),您可能想要查找Michael Abrash的图形编程Zen的旧副本。这描述了Bresenhams众所周知的线算法,以及不那么着名的Hardenburghs圈算法。结合两者的跨度版本来快速计算半圆的跨度应该不会太难。
IIRC, Hardenburgh uses the x^2 + y^2 = radius^2, but exploits the fact that you're stepping through spans to avoid calculating square roots - I think it uses the fact that (x+1)^2 = x^2 + 2x + 1 and (y-1)^2 = y^2 - 2y + 1, maintaining running values for x, y, x^2 and (radius^2 - y^2), so each step only requires a comparison (is the current x^2 + y^2 too big) and a few additions. It's done for one octant only (the only way to ensure single-pixel steps), and extended to the full circle through symmetry.
IIRC,Hardenburgh使用x ^ 2 + y ^ 2 = radius ^ 2,但利用了你跨越跨度以避免计算平方根的事实 - 我认为它使用的事实是(x + 1)^ 2 = x ^ 2 + 2x + 1和(y-1)^ 2 = y ^ 2 - 2y + 1,保持x,y,x ^ 2和(radius ^ 2 - y ^ 2)的运行值,因此每个步骤仅需要比较(当前x ^ 2 + y ^ 2太大)和一些补充。它仅用于一个八分圆(确保单像素步长的唯一方法),并通过对称扩展到整圆。
Once you have the spans for the full circle, it should be easy to use Bresenhams to cut off the half you don't want.
一旦你有完整的圆圈跨度,应该很容易使用Bresenhams切断你不想要的一半。
Of course you'd only do all this if you're absolutely certain that you need to (and that you can work with integers). Otherwise stick with stbuton.
当然,如果您完全确定需要(并且可以使用整数),那么您只会执行所有这些操作。否则坚持使用stbuton。
#1
Checking whether a point is inside or outside a semi-circle (or a rectangle for that matter) is a constant-time operation.
检查点是在半圆内部还是外部(或者对于该问题的矩形)是恒定时间操作。
Checking N points lie inside or outside a semi-circle or rectangle is O(N).
检查位于半圆或矩形内部或外部的N个点是O(N)。
Sorting your N points is O(N*lg(N)).
对N点进行排序为O(N * lg(N))。
It is asymptotically faster to test all points sequentially than it is to sort and then do a fast culling of the points based on a binary search.
按顺序测试所有点比逐行排序然后基于二进制搜索快速剔除点逐渐快。
This may be one of those times where what seems fast and what is fast are two different things.
这可能是那些看似快速而快速的东西是两个不同的东西之一。
EDIT
There's also a dead-simple way to test containment of a point in the semi-circle without mucking about with rotations, transformations, and the like.
还有一种简单的方法来测试半圆中一个点的包含,而不会在旋转,变换等情况下进行扫描。
Represent the semi-circle as two components:
将半圆表示为两个组成部分:
- a line segment from point a to b representing the diameter of the semi-circle
- an orientation of either left-of or right-of indicating that the semi-circle is either to the left or right of line segment ab when traveling from a to b
从a点到b点的线段表示半圆的直径
左侧或右侧的方向,指示当从a到b行进时,半圆是线段ab的左侧或右侧
You can exploit the right-hand rule to determine if the point is inside the semicircle.
您可以利用右手规则来确定该点是否在半圆内。
Then some pseudo-code to test if point p is in the semi-circle like:
然后一些伪代码来测试点p是否在半圆中如下:
procedure bool is_inside:
radius = distance(a,b)/2
center_pt = (a+b)/2
vec1 = b - center_pt
vec2 = p - center_pt
prod = cross_product(vec1,vec2)
if orientation == 'left-of'
return prod.z >= 0 && distance(center_pt,p) <= radius
else
return prod.z <= 0 && distance(center_pt,p) <= radius
This method has the added benefit of not using any trig functions and you can eliminate all square-roots by comparing to the squared distance. You can also speed it up by caching the 'vec1' computation, the radius computation, center_pt computation, and reorder a couple of the operations to bail early. But I was trying to go for clarity.
此方法具有不使用任何触发函数的额外好处,您可以通过与平方距离进行比较来消除所有平方根。您还可以通过缓存'vec1'计算,半径计算,center_pt计算以及重新排序几个操作来提前保释来加速它。但我试图澄清。
The 'cross_product' returns an (x,y,z) value. It checks if the z-component is positive or negative. This can also be sped up by not using a true cross product and only calculating the z-component.
'cross_product'返回(x,y,z)值。它检查z分量是正还是负。这也可以通过不使用真正的交叉乘积并仅计算z分量来加速。
#2
First, translate & rotate the semi-circle so that one end is on the negative X-axis, and the other end is on the positive X-axis, centered on the origin (of course, you won't actually translate & rotate it, you'll just get the appropriate numbers that would translate & rotate it, and use them in the next step).
首先,平移和旋转半圆,使一端位于负X轴上,另一端位于正X轴上,以原点为中心(当然,您实际上不会平移和旋转它) ,你只需得到适当的数字就可以翻译并旋转它,并在下一步中使用它们。
Then, you can treat it like a circle, ignoring all negative y-values, and just test using the square root of the sum of the squares of X & Y, and see if it's less than or equal to the radius.
然后,您可以将其视为圆形,忽略所有负y值,然后使用X和Y的平方和的平方根进行测试,并查看它是否小于或等于半径。
#3
"Maybe they can brute force it since they have a full GPU dedicated to them."
“也许他们可以蛮力,因为他们拥有专用于他们的完整GPU。”
If you have a GPU at your disposal, then there are more ways to do it. For example, using a stencil buffer:
如果您拥有GPU,那么有更多方法可以实现。例如,使用模板缓冲区:
- clear the stencil buffer and set the stencil operation to increment
- render your semicircle to the stencil buffer
- render your points
- read back the pixels and check the values at your points
- the points that are inside the semicircle would have been incremented twice.
清除模板缓冲区并将模板操作设置为递增
将半圆渲染到模板缓冲区
渲染你的观点
读回像素并检查各点的值
半圆内的点会增加两次。
This article describes how stencil buffers can be used in OpenGL.
本文介绍如何在OpenGL中使用模板缓冲区。
#4
If there's a standard algorithm for doing this, I'm sure someone else will come up with it, but if not: you could try sorting the points by distance from the center of the circle and iterating over only those whose distance is less than the semicircle's radius. Or if computing distance is expensive, I'd just try finding the bounding box of the semicircle (or even the bounding square of the circle of which the semicircle is part) and iterating over the points in that range. To some extent it depends on the distribution of the points, i.e. do you expect most of them or only a small fraction of them to fall within the semicircle?
如果有这样做的标准算法,我相信其他人会提出它,但如果没有:你可以尝试按距离圆心的距离对点进行排序,并仅迭代距离小于圆的中心的点。半圆的半径。或者如果计算距离很贵,我只是尝试找到半圆的边界框(或者甚至是半圆所在的圆的边界正方形)并迭代该范围内的点。在某种程度上,它取决于点的分布,即你是否期望它们中的大多数或只有一小部分落在半圆内?
#5
You can find points in a circle and points on one side of a given slope, right?
您可以在一个圆圈中找到点,并在给定斜坡的一侧找到点,对吧?
Just combine the two.
只需将两者结合起来。
#6
Here's part of a function I wrote do get a cone firing arc for a weapon in a tile based game.
这是我写的一个函数的一部分,在基于磁贴的游戏中为武器获得锥形射击弧。
float lineLength;
float lineAngle;
for(int i = centerX - maxRange; i < centerX + maxRange + 1; i++){
if(i < 0){
continue;
}
for(int j = centerY - maxRange; j < centerY + maxRange + 1; j++){
if(j < 0){
continue;
}
lineLength = sqrt( (float)((centerX - i)*(centerX - i)) + (float)((centerY - j)*(centerY - j)));
lineAngle = lineAngles(centerX, centerY, forwardX, forwardY, centerX, centerY, i, j);
if(lineLength < (float)maxRange){
if(lineAngle < arcAngle){
if( (float)minRange <= lineLength){
AddToHighlightedTiles(i,j);
}
}
}
}
}
The variables should be self explanatory and the line angles function takes 2 lines and finds the angle between them. The forwardX and forwardY is just one tile in the correct direction from the center X and Y based on what angle you're pointing in. Those can be gotten easily with a switch statement.
变量应该是自解释的,线角度函数需要2行并找到它们之间的角度。 forwardX和forwardY只是从中心X和Y开始的正确方向上的一个图块,基于您指向的角度。使用switch语句可以轻松获得这些图块。
float lineAngles(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
int a = x2 - x1;
int b = y2 - y1;
int c = x4 - x3;
int d = y4 - y3;
float ohSnap = ( (a * c) + (b * d) )/(sqrt((float)a*a + b*b) * sqrt((float)c*c + d*d) );
return acos(ohSnap) * 180 / 3.1415926545f;
}
#7
- translate the center of the arc to the origin
- compute angle between ordinate axis and end points of radii of semi-cirlce
- translate the point in question by same dx,dy
-
compute distance from origin to translated x,y of point, if d > radius of circle/arc eliminate
如果d>圆/弧的半径消除,则计算从原点到平移的x,y的距离
- compute angle between ordinate axis and end point
- if angle is not between starting and ending arc of semi-cirlce, eliminate
计算纵坐标轴和终点之间的角度
如果角度不在半螺旋的起始和结束弧之间,则消除
points remaning should be inside semi-circle
点重新应该在半圆内
将弧的中心转换为原点
计算纵坐标轴和半螺旋半径终点之间的角度
用相同的dx,dy翻译有问题的点
#8
I guess someone found the same solution as me here but I have no code to show as its pretty far in my memory...
我想有人在这里找到了和我一样的解决方案,但我没有代码可以显示它在我的记忆中相当远......
I'd do it by steps...
1. I'd look if i'm within a circle... if yes look on which side of the circle.
2. By drawing a normal vector that come from the vector made by the semi-sphere. I could know if I'm behind or in front of the vector...and if you know which side is the semi sphere and which side is the void...It will be pretty damn easy to find if you're within the semi sphere. You have to do the dot product.
我是按步骤做的...... 1.我会看看我是否在一个圆圈内...如果是的话,看看圆圈的哪一边。 2.通过绘制来自半球形矢量的法向量。我可以知道我是在后面还是在矢量前面......如果你知道哪一侧是半球形,哪一侧是空洞...如果你在内部那将是非常容易找到的半球形。你必须做点积。
I'm not sure if it's clear enough but the test shouldn't be that hard to do...In the end you have to look for a negative or positive value...if it's 0 you're on the vector of the semisphere so it's up to you to say if it's outside or inside the semi-sphere.
我不确定它是否足够清楚,但测试不应该那么难......最后你必须寻找一个负面或正面的值...如果它是0,你就是在半球所以你可以说它是在半球之外还是半球之内。
#9
The fastest way to do this will depend on your typical data. If you have real-world data to look at, do that first. When points are outside the semi-circle, is it usually because they are outside the circle? Are your semi-circles typically thin pie slices?
最快的方法取决于您的典型数据。如果您要查看真实数据,请先执行此操作。当点在半圆之外时,通常是因为它们在圆外吗?你的半圆圈通常是薄饼片吗?
There are several ways to do this with vectors. You can scale the circle to a unit circle and use cross-products and look at the resultant vectors. You can use dot-products and see how the prospective point lands on the other vectors.
使用矢量有几种方法可以做到这一点。您可以将圆缩放为单位圆并使用交叉积并查看合成矢量。您可以使用点积,看看预期点如何落在其他向量上。
If you want something really easy to understand, first check to make sure it's inside the circle, then get the angle and make sure it's between the angle of the two vectors that dictate the semi-circle.
如果你想要一些非常容易理解的东西,首先检查以确保它在圆圈内,然后获得角度并确保它在两个矢量的角度之间,这决定了半圆。
Edit: I had forgotten that a semicircle is always half a circle. I was thinking of any arbitrary section of a circle.
编辑:我忘记了半圆总是半圈。我在想一个圆圈的任意部分。
Now that I have remembered what a semicircle is, here's how I would do that. It's similar to stbuton's solution, but it represents the semicircle differently.
既然我记得半圆是什么,我就是这样做的。它与stbuton的解决方案类似,但它以不同的方式表示半圆。
I'd represent the semicircle as the unit vector that bisects the semicircle. You can easily get that from either one of the vectors that indicate the boundary of the semicircle (because they are 90 degrees away from the representation) by swapping x and y and negating one of them.
我将半圆表示为将半圆一分为二的单位向量。您可以通过交换x和y并取消其中一个来轻松地从指示半圆边界的任何一个向量(因为它们与表示相距90度)中得到它。
Now you just cross the vector created by subtracting the point to be tested from the circle's center. The sign of z tells you whether the point is in the semicircle, and the length of z can be compared against the radius.
现在,您只需越过通过从圆的中心减去要测试的点而创建的向量。 z的符号告诉您该点是否在半圆中,并且z的长度可以与半径进行比较。
I did all the physics for Cool Pool (from Sierra Online). It's all done in vectors and it's filled with dots and crosses. Vectors solutions are fast. Cool Pool was able to run on a P60, and did reasonable breaks and even spin.
我做了Cool Pool的所有物理学(来自Sierra Online)。这一切都是在矢量中完成的,它充满了点和十字架。矢量解决方案很快。 Cool Pool能够在P60上运行,并且做了合理的休息甚至旋转。
Note: For solutions where you're checking sqrt(xx+yy), don't even do the sqrt. Instead, keep the square of the radius around and compare against that.
注意:对于您正在检查sqrt(xx + yy)的解决方案,请不要执行sqrt。相反,保持半径的平方并与之进行比较。
#10
It would appear that a simple scheme will work here.
这似乎是一个简单的方案。
-
Reduce the number of points in the set, by first computing the convex hull. Only the points on the convex hull will contribute to any interaction with any convex bounding shape. So retain only the subset of points on the perimeter of the hull.
通过首先计算凸包来减少集合中的点数。只有凸包上的点才会促成与任何凸边界形状的任何相互作用。因此,仅保留船体周边的点子集。
-
It can easily be argued that the minimal radius bounding semi-circle must have one edge (two points) of the convex hull coincident along the diameter of the semi-circle. I.e., if some edge of the hull does not lie in the diameter, then there exists a different semi-circle with smaller diameter that contains the same set of points.
可以很容易地认为,最小半径边界半圆必须使凸包的一个边(两个点)沿着半圆的直径重合。即,如果船体的某些边缘不在直径中,则存在具有较小直径的不同半圆,其包含相同的点集。
-
Test each edge in sequence. (A convex hull often has relatively few edges, so this will go quickly.) Now it becomes a simple 1-d minimization problem. If we choose to assume the edge in question lies on the diameter, then we merely need to find the center of the sphere. It must lie along the current line which we are considering to be the diameter. So as a function of the position of the point along the current diameter, just find the point which lies farthest away from the nominal center. By minimizing that distance, we find the radius of the minimal semi-circle along that line as a diameter.
按顺序测试每个边缘。 (凸包通常具有相对较少的边缘,因此这将很快。)现在它成为一个简单的一维最小化问题。如果我们选择假设有问题的边缘在于直径,那么我们只需要找到球体的中心。它必须位于我们考虑为直径的当前线上。因此,作为沿当前直径的点位置的函数,只需找到距离标称中心最远的点。通过最小化该距离,我们发现沿该线的最小半圆的半径作为直径。
Now, just choose the best of the possible semi-circles found over all edges of the convex hull.
现在,只需选择在凸包的所有边缘上找到的最好的半圆。
#11
If your points have integer co-ordinates, the fastest solution may be a lookup table. Since a semicircle is convex, for each y co-ordinate, you get a fixed range of x, so each entry in your lookup table gives maximum and minimum X co-ordinates.
如果您的点具有整数坐标,则最快的解决方案可能是查找表。由于半圆是凸的,对于每个y坐标,你得到一个固定的x范围,因此查找表中的每个条目都给出了最大和最小的X坐标。
Of course you still need to precalculate the table, and if your semicircle isn't fixed, you may be doing that a lot. That said, this is basically one part of what would once have been done to render a semicircle - the full shape would be rendered as a series of horizontal spans by repeatedly calling a horizontal line drawing function.
当然你仍然需要预先计算表格,如果你的半圆没有固定,你可能会做很多事情。也就是说,这基本上是渲染半圆的一部分 - 通过重复调用水平线绘制函数,整个形状将呈现为一系列水平跨度。
To calculate the spans in the first place (if you need to do it repeatedly), you'd probably want to look for an old copy of Michael Abrash's Zen of Graphics Programming. That described Bresenhams well-known line algorithm, and the not-so-well-known Hardenburghs circle algorithm. It shouldn't be too hard to combine the span-oriented versions of the two to quickly calculate the spans for a semi-circle.
要首先计算跨度(如果需要反复进行),您可能想要查找Michael Abrash的图形编程Zen的旧副本。这描述了Bresenhams众所周知的线算法,以及不那么着名的Hardenburghs圈算法。结合两者的跨度版本来快速计算半圆的跨度应该不会太难。
IIRC, Hardenburgh uses the x^2 + y^2 = radius^2, but exploits the fact that you're stepping through spans to avoid calculating square roots - I think it uses the fact that (x+1)^2 = x^2 + 2x + 1 and (y-1)^2 = y^2 - 2y + 1, maintaining running values for x, y, x^2 and (radius^2 - y^2), so each step only requires a comparison (is the current x^2 + y^2 too big) and a few additions. It's done for one octant only (the only way to ensure single-pixel steps), and extended to the full circle through symmetry.
IIRC,Hardenburgh使用x ^ 2 + y ^ 2 = radius ^ 2,但利用了你跨越跨度以避免计算平方根的事实 - 我认为它使用的事实是(x + 1)^ 2 = x ^ 2 + 2x + 1和(y-1)^ 2 = y ^ 2 - 2y + 1,保持x,y,x ^ 2和(radius ^ 2 - y ^ 2)的运行值,因此每个步骤仅需要比较(当前x ^ 2 + y ^ 2太大)和一些补充。它仅用于一个八分圆(确保单像素步长的唯一方法),并通过对称扩展到整圆。
Once you have the spans for the full circle, it should be easy to use Bresenhams to cut off the half you don't want.
一旦你有完整的圆圈跨度,应该很容易使用Bresenhams切断你不想要的一半。
Of course you'd only do all this if you're absolutely certain that you need to (and that you can work with integers). Otherwise stick with stbuton.
当然,如果您完全确定需要(并且可以使用整数),那么您只会执行所有这些操作。否则坚持使用stbuton。