标签: computational-geometry

我在我的搜索中找到了计算几何算法库,用于将凹多边形分解为最小数量的凸组件.链接网站和众多谷歌搜索结果表明它有python绑定,这将非常方便,但所有链接都已死!这是怎么回事？我现在在哪里可以得到它？

问题
我想将网格(2D阵列)划分为随机形状的部分(想想地球的构造板块).

标准是:

• 用户输入网格大小(程序应该缩放,因为这可能非常大).
• 用户输入网格划分因子(多少部分).
• 网格是矩形六角网格,顶部和底部封顶,左右环绕.
• 零件没有碎片.
• 其他部分内没有零件.
• 没有微小或超大的部件.
• 随机形状的部分,不是完美的圆形,或者是蜿蜒的蛇形.

我的解决方案

• 创建一个可以访问/操作相邻单元格的方法.
• 随机确定每个部分的大小(所有部分的总和等于整个2D阵列的大小).
• 用最后一部分的id号填充整个2D数组.
• 除了最后一个部分:
• 在2D阵列的随机单元格中种植当前部件ID号.
• 迭代整个阵列并将每个单元的地址存储在已经使用当前部件ID号播种的任何单元旁边.
• 提取其中一个存储的地址,并使用当前的板ID编号填充该单元格(因此部件开始形成).
• 重复,直到达到零件尺寸.

请注意,为了避免在其内部长出"臂"或大孔的部分,我创建了两个存储阵列:一个用于与一个单元相邻的单元,当前部件ID号,另一个用于与多个单元相邻的单元,然后我在前者之前用尽了后者.

运行我的解决方案提供以下内容:
网格大小:200
宽度:20
高度:10个
部分:7

66633333111114444466
00033331111114444466
00003331111114444466
00003331111144444660
0000333111164444660
00000336111664422600
00000336615522222200
00006655555522222200
00006655555552222220
00066655555552222220

产品号:0产品
尺寸:47

部件号:1
零件尺寸:30

产品号:2产品
尺寸:26

产品号:3产品
尺寸:22

产品号:4产品
尺寸:26

产品号:5产品
尺寸:22

产品号:6产品
尺寸:27

我的解决方案有问题:

• 最后一部分总是支离破碎 - 在上面的例子中有三个独立的六人组.
• 当零件在死胡同中形成并且没有足够的空间来扩展到它们的全尺寸时算法会停止(算法不允许在其他部分上形成零件,除非它是最后一部分,它是整个开始时的2D阵列).
• 如果我在形成2d阵列​​之前没有指定零件尺寸,只需要指定零件数量并随意生成零件尺寸,这就会留下形成微小零件的可能性,这可能不是在那里,特别是当2D阵列非常大时.我目前的零件尺寸方法将零件尺寸限制在2D阵列总尺寸的10%到40%之间.如果有一些超级优雅的方法可以做到这一点,我可能没有指定零件尺寸 - 用户将拥有的唯一控件是二维阵列尺寸和零件数量.

其他想法:

• 将部件形成完美对齐的正方形,然后在2D阵列上运行并随机允许每个部件侵入其他部件,将它们翘曲成随机形状.
• 在网格上绘制蛇形线并填充创建的空间,可能使用这样的数学:http://mathworld.wolfram.com/PlaneDivisionbyLines.html

结论:
所以这就是问题:我是一名初学程序员,不确定我是否以正确的方式解决了这个问题.我可以创建一些更多的"补丁"方法,将碎片部分移动到一起,并允许形成部分"跳出"死胡同,如果它们卡在它们中,但它感觉凌乱.

你会如何解决这个问题？我可以用一些性感的数学来简化一些事情吗？

谢谢

可能重复:
查找点是否位于矩形内

有一个采访问题,"如何确定一个点是否位于矩形内"

请注意,矩形也可以旋转.因此,检查矩形内部点的简单解决方案在这里不起作用......

请分享您对这个问题的看法..

我在互联网上找到了一个链接,并试图理解它,但失败了....请问这里的任何一个机构可以提供完整的计算机图形逻辑解决方案,因为我已经忘记了所有的基础知识.... 如何确定一个点是否在矩形内.

我试图想出一种方法,用于在给定区域(在我的情况下是一个正方形)中生成X量的随机点.造成这种问题的一个原因是每个点必须至少与所有其他点相距Y个单位.

首先想到的是(在c#中)检查新点和所有现有点之间的距离:

while(points.Count < pointsToGenerate)
{
     Point newPoint = NewPoint();
     bool addPoint = true;
     foreach(Point p in points)
     {
          if((p - newPoint).Length() < minDistance)
          {
              addPoint = false;
              break;
          }
     }

     if(addPoint)
     {
          points.Add(newPoint);
     }
}

现在这肯定会有效,但如果没有找到有效点,这将成为一个永无止境的循环.所以在那里投入一个神奇的数字Z作为尝试的极限？

if(loopCount > 100)
{
     break;
}

现在这有一些明显的问题.如果这些点是随机生成的,那么即使存在放置点的位置,loopCount也可以超过Z. 它不仅可以,而且会发生!

我能做的是为每个传递创建一个可用点列表,然后选择其中一个随机点.除了一件事:性能,这将完美无缺.我的应用程序中不需要超级性能,但面积为1000 ^ 2.即使我将自己限制为整数,每次通过也要检查很多要点!

所以,我能想到的可能还不够,因此我希望得到一些帮助.有没有更好的方法在区域A中生成X点,点Y之间的距离最小？

谢谢!

编辑:更好,我的意思是通常更好地实现性能与完美的平衡.我知道,有点模糊.我并不确定我有多少开销可以产生这些点,所以我基本上比我自己的方法更优雅.

〜罗伯特

我正在制作一个程序,您可以点击地图查看其周围区域的"特写视图",例如在Google地图上.

当用户点击地图时,它会获得他们点击的X和Y坐标.

让我们假设我有一系列布尔值,这些特写视图图片是:

public static boolean[][] view_set=new boolean[Map.width][Map.height];
//The array of where pictures are.  The map has a width of 3313, and a height of 3329.

程序搜索文件夹,其中图像被命名为在地图上拍摄地点的X和Y坐标.该文件夹包含以下图像(以及更多,但我只列出五个):

2377,1881.jpg, 2384,1980.jpg, 2389,1923.jpg, 2425,1860.jpg, 2475,1900.jpg

这意味着:

view_set[2377][1881]=true;
view_set[2384][1980]=true;
view_set[2389][1923]=true;
view_set[2425][1860]=true;
view_set[2475][1900]=true;

如果用户点击例如2377,1882的X和Y,那么我需要程序来确定哪个图像最接近(在这种情况下答案是2377,1881).

任何帮助将不胜感激,谢谢.

我需要解决动态凸包算法问题,即保持2D点的凸包,我可以添加和删除点.

天真的做法很明显O(N); 无论何时N添加/删除其中一个点,我们都会从头开始重新计算凸包.但是,我无法承受线性时间,因此我正在寻找一种次线性算法.到目前为止,我已经找到了一堆纸,所有这些都描述了一些具有疯狂时间限制的复杂算法,这需要花费很长时间才能实现.即使是最古老的高效算法,由于Overmars和Leeuween,这O(log^2 N)似乎太复杂了.(像往常一样,这些论文中描述的大多数算法在结构/算法方面都有很多依赖性来自其他参考文献)

我正在寻找更简单,更不一定新颖的东西,在最坏的情况下(例如O(sqrt N))在线性方面表现优于线性.最后,我不介意时间是否摊销.有任何想法吗？

(简单来说,我主要是指不需要超过几百行代码的东西.)

我有2个三角形和顶点p0,p1,p2,p3.这两个三角形共享边缘.从这两个三角形我想制作一个由4个顶点给出的四面体.我使用的库要求"应该给出4个顶点,使得在从外面观察时,在图中定义四面体面的四个顶点三元组以逆时针顺序出现".假设两个三角形中的一个是p0,p1,p2,则将法线计算为(p1-p0)(交叉)(p2-p0).有人可以告诉我一种方法来确保满足这个条件吗？

四面体网格中的点位置是否有任何经过验证的数据结构,其中四面体都是不相交的,但彼此"接触"？即大多数面孔都是正好两个四面体的面孔.

按位置我的意思是我想找出给定点位于哪个四面体中,或者它是否位于任何四面体中.

到目前为止,我尝试过:

1. 一个简单的KD树.这对我的需求来说太慢了,因为平均树深非常高,我仍然有很多单独的四面体在每片叶子中进行测试.

2. 一个网格,包含每个单元格的所有交叉四面体.这似乎工作得更好,但仍然不够快.首先,网格包含许多空单元格,因为我的整体网格不是非常"四四方方".其次,大多数实际上含有四面体的细胞确实含有大量细胞(10+).我想这是因为很多四面体共享每个顶点,一旦顶点在一个单元格中,所有相邻的四面体也是如此.

关于输入数据的一些进一步信息:网格通常不是凸的并且可以具有孔或内含物.虽然最后两个有点不太可能,但我必须处理它们,如果没有(昂贵和复杂的？)预处理,这使得"行走"变得不可能.

假设我在一般位置有n个线段.对于我的每个n段,我如何快速计算它相交的其他n-1的数量？

我可以在O(n ²)时间内天真地做这件事.我可以在O((n + k)log n)时间内使用相当简单的扫描线算法(Bentley-Ottmann)找到所有交叉点,其中k是这样的交叉点的数量,然后将我发现的交叉点聚合成一堆计数.

不过,我不需要找到交叉路口; 我只是想知道有多少.我没有看到如何将扫描线算法修改得更快,因为它需要为每个交叉点重新排序树中的两个东西,我想不出任何其他没有遇到同样问题的技术.

我也有兴趣听听如何计算总交叉口数量.

好吧,近似一个带有多边形的圆圈和毕达哥拉斯的故事可能是众所周知的.但另一种方式呢？

我有一些多边形,实际上应该是圆圈.但是,由于测量误差,它们不是.所以,我正在寻找的是最能"近似"给定多边形的圆.

在下图中,我们可以看到两个不同的例子.

我的第一个Ansatz是找到点到中心的最大距离以及最小值.我们正在寻找的圈子可能介于两者之间.

这个问题有没有算法？