假设我有一组巨大的非重叠矩形和整数坐标,它们一劳永逸地固定
我有另一个矩形A,其整数坐标的坐标正在移动(但你可以假设它的大小是常数)
查找哪些矩形与A交叉(或内部)的最有效方法是什么？我不能简单地遍历我的设置,因为它太大了.谢谢
编辑:矩形都与轴平行
我试图找到目的地点,给定起点纬度/长度,方位和距离.下面这个网站的计算器给了我想要的结果.
http://www.movable-type.co.uk/scripts/latlong.html
当我尝试通过代码实现相同的时候,我得不到正确的结果.
以下是我的代码 -
private GLatLng pointRadialDistance(double lat1, double lon1,
double radianBearing, double radialDistance)
{
double rEarth = 6371.01;
lat1 = DegreeToRadian(lat1);
lon1 = DegreeToRadian(lon1);
radianBearing = DegreeToRadian(radianBearing);
radialDistance = radialDistance / rEarth;
double lat = Math.Asin(Math.Sin(lat1) * Math.Cos(radialDistance) + Math.Cos(lat1)
* Math.Sin(radialDistance) * Math.Cos(radianBearing));
double lon;
if (Math.Cos(lat) == 0)
{ // Endpoint a pole
lon = lon1;
}
else
{
lon = ((lon1 - Math.Asin(Math.Sin(radianBearing) * Math.Sin(radialDistance) / Math.Cos(lat))
+ Math.PI) % (2 * Math.PI)) - Math.PI; …假设我有很多多边形,构造多边形的最佳算法是什么 - 可能是所有这些多边形的并集孔？
为了我的目的,你可以想象每个多边形作为一个拼图块,当你完成它们你会得到一个很好的图片.但问题是,缺少一小部分(比如<5%)的拼图,你仍然要求尽可能完整地形成一幅画面; 这是多边形(或多边形) - 可能有孔 - 我想形成.
我天真的方法是取两个多边形,合并它们,然后取另一个多边形,将它与两个多边形的并集联合起来,然后重复这个过程,直到每个单元都结合在一起.然后我将遍历联合多边形列表并检查是否仍然可以组合一些多边形,并且我将重复此过程,直到获得满意的结果.
但这似乎是一种非常天真的方法.我只是想知道还有其他更好的算法吗？
我问这个问题是出于问题,因为我的快速和肮脏的实现似乎已经足够好了.但是我很好奇什么是更好的实现.
我有一个真实世界数据的图表.没有重复的X值,X值在图表上以一致的速率递增,但Y数据基于实际输出.我想以编程方式从任意给定点P找到图上最近的点.我正在努力寻找一种有效(即快速)的算法来做到这一点.我不需要确切的最近点,我可以找到一个"接近"最近点的点.
显而易见的懒惰解决方案是增加图中的每个点,计算距离,然后找到距离的最小值.然而,理论上这对于大型图表来说可能很慢; 对我想要的东西来说太慢了.
由于我只需要一个近似的最近点我想象理想的最快方程将涉及生成最佳拟合线并使用该线来实时计算该点的位置; 但这听起来像是一个潜在的数学头痛,我不打算接受.
我的解决方案是一个hack,只能因为我认为我的点P不是任意的,即我假设P通常接近我的图线,当发生这种情况时,我可以从考虑中划掉远处的X值.我计算与P共用X坐标的线上的点的接近程度,并使用该点与P之间的距离来计算可能更接近点的最大/最小X值.
我不禁觉得应该有一个更快的算法然后我的解决方案(这是有用的,因为我假设99%的时间我的点P将是一个接近线的点).我尝试使用谷歌搜索更好的算法,但发现很多算法不太合适,以至于在所有不合适的算法混乱中很难找到我想要的东西.那么,这里有没有人有一个更有效的建议算法？请记住,我不需要一个完整的算法,因为我的工作符合我的需要,我只是好奇什么是正确的解决方案.
我想在2D平面中创建一组非退化的大量随机点云(在整个集合中没有直线3个点).我有一个天真的解决方案,它生成一个随机浮点对P_new(x,y),并检查到现在生成的每一对点(P1,P2),如果点(P1,P2,P)位于同一行或不同.这需要对添加到列表中的每个新点进行O(n ^ 2)检查,使得整个复杂度为O(n ^ 3),如果我想生成超过4000个点(超过40分钟),则非常慢.有没有更快的方法来生成这些非简并点？
在Matlab中,您可以通过指定中心和半径来绘制圆形,如下所示:
R = 10;
Center = [5,8];
circle(Center,R,1000,'b-');
hold on
plot(Center(1),Center(2),'g.')
MatLab的相同代码不适用于GNU Octave.在给定中心x,y坐标和半径的情况下,哪个八度代码会绘制一个圆？
我们有一个表格的间隔列表.对于每个间隔,我们想要计算嵌套在其中的其他间隔的数量. [ai, bi]
例如,如果我们有两个间隔,A = [1,4]和B = [2,3].然后计数B将0是没有嵌套间隔B; 和计数A将1作为B内适合A.
我的问题是,是否存在针对此问题的子 算法,其中间隔的数量是多少？O(n2)n
编辑: 以下是间隔符合的条件.间隔的终点是浮点数.a i/b i的下限是0,上限是max float的最大值.此外,存在i <b i的条件,因此没有长度为0的间隔.
我试图通过使用我的网络摄像头从具有已知全球位置的四个基准点的图像中获得全局姿势估计.
我检查了很多stackexchange问题和一些文章,我似乎无法得到一个正确的解决方案.我得到的位置编号是可重复的,但绝不与摄像机移动成线性比例.仅供参考我使用的是C++ OpenCV 2.1.
在这个链接上描绘了我的坐标系和下面使用的测试数据.
% Input to solvePnP():
imagePoints = [ 481, 831; % [x, y] format
520, 504;
1114, 828;
1106, 507]
objectPoints = [0.11, 1.15, 0; % [x, y, z] format
0.11, 1.37, 0;
0.40, 1.15, 0;
0.40, 1.37, 0]
% camera intrinsics for Logitech C910
cameraMat = [1913.71011, 0.00000, 1311.03556;
0.00000, 1909.60756, 953.81594;
0.00000, 0.00000, 1.00000]
distCoeffs = [0, 0, 0, 0, 0]
% output of solvePnP():
tVec = [-0.3515;
0.8928;
0.1997]
rVec = [2.5279; …opencv computational-geometry camera-calibration pose-estimation extrinsic-parameters
给定一组在平面上的点的,α-形状的概念,对于给定的正数α,通过找到Delaunay三角剖分并删除对于其中至少一个边缘的长度超过了阿尔法任何三角形定义.这是使用d3的示例:
http://bl.ocks.org/gka/1552725
问题是,当有数千个点时,简单地绘制所有内部三角形对于交互式可视化来说太慢了,所以我想找到边界多边形.这不是那么简单,因为从这个例子可以看出,有时可能会有两个这样的多边形.
作为简化,假设已经执行了一些聚类,因此保证每个三角测量的唯一边界多边形.找到这个边界多边形的最佳方法是什么？特别是,边缘必须一致地排序,它必须支持"洞"的可能性(想想圆环或圆环形状 - 这在GeoJSON中是可表达的).