标签: computational-geometry

我有一个托管Google Earth Plugin实例的应用程序,我有兴趣获取当前的地图比例并在我的应用程序中使用它.

我知道我可以使用GEOptions并设置Scale Legend可见性,但我想在我的应用程序中使用实际的比例值,但我找不到它的API.

有没有办法做到这一点？

如果没有,我如何使用当前视图计算当前比例？

我正在寻找一种算法，该算法将从简单的凹面多边形减去一个矩形并返回其余的多边形。如果矩形将多边形包围，则其余部分为null。在大多数情况下，矩形和多边形之间至少会共享一条边。

我一直在浏览互联网，但是找不到很好的线索。

有人可以指出我正确的方向吗？

我需要一种表征2D点集大小的方法，以便可以根据视口的比例确定将它们渲染为空间中的单个点还是代表性多边形。我已经有了一种算法来计算集合的凸包以生成代表性多边形，但是我需要一种表征其大小的方法。一个明显的度量是凸包上点之间的最大距离，即集合的直径。但是我真的更感兴趣于垂直于其直径的横截面的大小，以找出边界多边形有多窄。给定顶点和最远点的索引的排序列表（理想情况是在Python中），是否有一种简单的方法来做到这一点？

或者，是否有一种简单的方法来计算一组点的最小面积边界椭圆的半径？我已经看到了解决此问题的一些方法，但是没有什么可以轻易转换为Python的，所以我真的在寻找可以交钥匙的东西。

Google地球桌面应用程序显示了一行map length和ground length一行.

在谷歌地球插件中,我想做一个类似的事情,那就是我希望确定ground length一个镶嵌细分KmlLineString的地形.

我可以这样做,如果是这样,怎么样？

如果每个点的每个坐标是p/q形式的有理数,并且p和q的有界值,则表明在平面中n个点的凸包可以在O(n)时间内计算.

注意:这是一个家庭作业问题.我可以想到以某种方式避免扫描所有点使用Jarvis March.也许这可以通过向固定方向投射光线(使用合理条件)来检查下一个点存在的位置来完成.

所以,今天我一直在努力解决一个坦率的现在真气的问题.

给定平面上三角形的一组顶点(仅3个点,6个自由参数),我需要计算该三角形与{0,0}和{1,1}定义的单位平方的交点区域.(我之所以选择这个,是因为2D中的任何方形都可以转换为此方,同一个转换可以移动3个顶点).

所以,现在问题简化为只有6个参数,3个点......我认为这个问题很短,我愿意编写完整的解决方案/找到完整的解决方案.

(如果可能的话,我想在GPU上运行超过200万个三角形,每个<0.5秒.至于需要简化/没有数据结构/库)

就我对解决方案的尝试而言,我已经...列出了我想出的方法,其中没有一个看起来很快或者......特定于好的情况(太笼统).

选项1:找到封闭的多边形,它可以是从三角形到6格的任何东西.通过在我发现的O(n)时间算法中使用一些凸多边形的交叉来做到这一点.然后我会按CW或CCw顺序对这些交点(新顶点,最多7个O(n log n))进行排序,这样我就可以在点上运行一个简单的区域算法(基于格林函数)( O(n)再次).对于与另一个m-gon相交的任意凸n-gon,这是我能提供的最快速度.但是......我的问题绝对不是那么复杂,它是一个特例,所以它应该有一个更好的解决方案......

选项2:因为我知道它是一个三角形和单位正方形,所以我可以用更强力的方式找到交叉点列表(而不是使用一些算法......坦率地说实施起来有点令人沮丧,如上所列)

只有19分要检查.4个点是三角形内的正方形角.正方形内有三角三角形.然后对于三角形的每条线,每条线将与正方形相交4条线(例如,y = 0,y = 1,x = 0,x = 1条线).那是另外12点.所以,12 + 3 + 4 = 19点检查.一旦我有了这个交叉点,最多6个,最少3个点,我可以跟进我能想到的两种方法中的一种.

2a:通过增加x值对它们进行排序,然后简单地将形状分解为其子三角形/ 4-gon形状,每个形状都有一个基于限制顶部和底部线的简单公式.总结一下这些地区.

或2b:再以某种循环方式对交点进行排序,然后根据绿色函数计算区域.

不幸的是,就我所知,这仍然是最复杂的.为了找到交点,我可以开始分解所有的情况,因为我知道它的正方形只有0和1,这使得数学删除了一些条款..但它不一定简单.

选项3:根据各种条件开始分离问题.例如.正方形内的0,1,2或3个三角形点.然后针对每种情况,遍历所有可能数量的交叉点,然后针对每个多边形形状的情况,唯一地记下区域解决方案.

选项4:一些具有重载步骤功能的配方.这是我最想要的那个,我怀疑它会有点......很大,但也许我很乐观这是可能的,并且一旦我有了公式,这将是计算最快的运行时间.

---总的来说,我知道可以使用一些高级库(例如限幅器)来解决它.我还意识到,在使用各种数据结构(链表,然后对其进行排序)时,编写通用解决方案并不是那么难.如果我只需要这样做几次,所有这些情况都可以.但是,因为我需要将它作为一个图像处理步骤运行,每张图像大约> 9*1024*1024次,我正在拍摄图像...让我说1 fps(技术上我会想要推动这个速度尽可能快地上升,但是下限是1秒来计算这些三角形交叉区域问题中的900万个).这在CPU上可能是不可能的,这很好,我可能最终会在Cuda中实现它,但我确实想要在这个问题上推动速度限制.

编辑:所以,我最终选择了2b.由于可能只有19个交叉点,其中最多6个将定义形状,我首先找到3到6个顶点.然后我按循环(CCW)顺序对它们进行排序.然后我通过计算该多边形的面积来找到该区域.

这是我写的测试代码(这是为了Igor,但应该是可读的伪代码)不幸的是它有点长啰嗦,但是......我认为除了我糟糕的排序算法(不应该超过20掉期) ,所以编写更好的排序没有那么多开销)...除了排序之外,我认为我不能让它更快.尽管如此,我对选择此选项时可能有的任何建议或疏忽持开放态度.

function calculateAreaUnitSquare(xPos, yPos)
wave xPos
wave yPos

// First, make array of destination. Only 7 possible results at most for this geometry. 
Make/o/N=(7) outputVertexX  = NaN
Make/o/N=(7) outputVertexY  = NaN

variable pointsfound = 0

// Check 4 corners of square
// Do this …

我需要生成随机分叶轮廓,如下所示

有关如何做到这一点的任何想法或算法？我将使用的软件是matlab,但是如果你用其他语言发布解决方案我也没问题...

ps我只需要绘制一个类似于上面的随机轮廓......

我正在使用序列化管道.我正在拿一个模型并将其导出.我不希望导出任何带孔的模型.我如何检测到一个洞并报告错误？

我可以访问所有顶点,边,面等.

这是我的意思的图片.

你可以看到脸上有个洞.我对几何学很陌生,所以请尝试用外行术语来解释.

我试图解决第6章 - 点位置"计算几何算法和应用,第3版 - 德伯格等人"一书的一些练习.不幸的是,我不知道如何解决以下练习:

Given a convex polygon P as an array of its n vertices in sorted order
along the boundary. Show that, given a query point q, it can be tested in
time O(log n) whether q lies inside P.

我的想法到目前为止: 我知道确定一个点是否位于O(log n)中的p内的唯一方法是使用有向无环图.为了使用有向无环图,我需要构建它,这在O(log n)中是不可能的.因此,我需要使用有序数组,但我所知道的唯一解决方案将花费O(N).

我希望有人可以帮助我.

我是python的新手。我在3d空间中有两个向量，我想知道两个之间的角度

我试过了：

vec1=[x1,y1,z1]

vec2=[x2,y2,z2]

angle=np.arccos(np.dot(vec1,vec2)/(np.linalg.norm(vec1)*np.linalg.norm(vec2)))

但是当更改顺序时，vec2，vec1获得相同的角度，并且不更高。当向量的顺序改变时，我想给我更大的角度。