标签: computational-geometry

我有x1,y1和x2,y2,形成一个线段.如何得到另一条x3,y3-x4,y4,它与图片中的第一行平行.我可以简单地将n添加到x1和x2以获得并行线,但它不是我想要的.我希望线条在图片中平行.

下面是2个矩形.给定矩形顶点的坐标 - (x1,y1)...(x8,y8),如何重叠区域的面积(下图中的白色)？

注意:

1. 积分坐标可能是任意的
2. 矩形可以重叠也可以不重叠
3. 当矩形不重叠时,假设面积为0,或者它们在点或线处重叠.
4. 如果一个矩形在另一个矩形内,则计算较小矩形的面积.

谷歌访谈期间我被问到这个问题.我们给出一个由字母-F,L,R组成的字符串. - 这是机器人遵循的指令

F-向前迈出一步.

向左转弯.

向右转.

字符串长度最多为2500个字符.

字符串无限次地运行.我们需要判断是否存在具有半径的圆,r(r可以是任何实数),这样机器人永远不会离开圆.我被困在这一点.我想到使用凸包,但如何检查无限次.用代码进行解释将不胜感激.请帮忙.提前致谢

我正在寻找几何算法的具体来源;

像两条线交叉等简单的东西很容易(并且很容易找到),但是我想找到一些算法来处理更棘手的事情,例如找到通过扩展给定多边形一定量形成的形状; 具有弯曲边等形状的快速算法

任何好的提示？谢谢!

给定平面上的一组点,找到由这两个点中的任何两个点形成的最短线段.

我怎样才能做到这一点？琐碎的方法显然是计算每个距离,但我需要另一种算法进行比较.

我最近在接受采访时被问到这个问题.虽然我是上不来的Ø(ñ ²)的解决方案,面试官与一个痴迷Ø(ñ)解决方案.我还检查了其他几个我理解的O(n log n)解决方案,但是O(n)解决方案仍然不是我的一杯茶,它假定约会按开始时间排序.

有谁能解释一下？

问题陈述:您有n个约会.每个约会包含开始时间和结束时间.您必须有效地重新调整所有冲突的约会.

人:1,2,3,4,5
App开始:
2,4,29,10,22 App结束:5,7,34,11,36

答案:2x1 5x3

O(n log n)算法:单独的起点和终点如下:

2s,4s,29s,10s,22s,5e,7e,34e,11e,36e

然后对所有这些点进行排序(为简单起见,我们假设每个点都是唯一的):

2s,4s,5e,7e,10s,11e,22s,29s,34e,36e

如果我们连续开始没有结束那么它是重叠的:2s,4s相邻,所以重叠就在那里

我们将保持"s"的计数,并且每次遇到它时将+1,并且当遇到e时,我们将计数减少1.

四叉树和kd树之间的主要区别是什么？我知道他们在很多方面分裂了点,但我不明白为什么我们会使用一个而不是另一个.我需要一个允许我计算给定区域中有多少点(2D点)的结构.基本上,我试图检测点集群.

我正在努力实现各种细分算法(例如catmull-clark); 要有效地执行此操作,需要一种很好的方法来存储有关细分多边形网格的信息.我实现了flipcode概述的半边数据结构,但现在我不确定如何从顶点填充数据结构!

我最初的尝试是

• 创建顶点
• 将顶点分组为面
• 对面内的顶点进行排序(使用它们相对于质心的角度)
• 对于每个面,抓取第一个顶点,然后遍历排序的顶点列表以创建半边列表.

但是,这会创建一个没有任何关于相邻面信息的面(一半边)列表!这也感觉有点不对,因为看起来好像是真正的第一类物体,边缘提供辅助信息; 我真的觉得我应该从顶点创建边缘,然后从那里整理出面.但同样,我不太确定如何以这种方式去做 - 我想不出一种方法来创建一个半边列表而不先创建面.

有关将顶点(和面)数据转换为半边的最佳方法的建议吗？

您将在平面上获得一组U个n点,并且可以在恒定时间内计算任意一对点之间的距离.选择一个名为C的U的子集,使得C中恰好有k个点,并且C中最远的2个点之间的距离对于给定的k尽可能小.1 <k <= n

除了明显的n-choose-k解决方案之外,最快的方法是什么？

我正在寻找一些相当容易的(我知道多边形联合不是一个简单的操作,但也许有人可以用一个相对简单的方法指向我的方法)合并两个相交的多边形.多边形可以是没有孔的凹面,输出多边形也不应该有孔.多边形以逆时针方式表示.我的意思是在图片上显示.正如你所看到的那样,即使在多边形的组合中有一个洞,我也不需要它在输出中.输入多边形肯定没有洞.我认为没有漏洞应该更容易,但我仍然没有想法.