标签: computational-geometry

我必须能够为飞行模拟器的航点设置随机位置.数学挑战很简单:

"要在四边形中找到一个随机位置,这个点在任何位置都有相同的可能性."

看起来像这样:

ABCD四边形的示例是:A:[21417.78 37105.97] B:[38197.32 24009.74] C:[1364.19 2455.54] D:[1227.77 37378.81]

提前感谢您提供的任何帮助.:-)

编辑感谢您的回复.我将在周末看看这个,然后将奖励接受的答案.顺便说一下,我应该提到四边形可以是CONVEX OR CONCAVE.Sry'bout dat.

我正在寻找一种打包算法,它将不规则多边形缩小为矩形和直角三角形.该算法应该尝试使用尽可能少的这种形状,并且应该相对容易实现(考虑到挑战的难度).在可能的情况下,它还应该优先考虑三角形的矩形

如果可能,这个问题的答案应该解释建议算法中使用的一般启发式方法.

对于小于100个顶点的不规则多边形,这应该在确定的时间内运行.

目标是为外行人产生不规则多边形的"合理"分解.

应用于解决方案的第一个启发式算法将确定多边形是规则的还是不规则的.在正多边形的情况下,我们将使用我的类似文章中关于常规多边形的方法:正则多边形的有效填充算法

alt text http://img401.imageshack.us/img401/6551/samplebj.jpg

我需要找到Path2D是否与自身相交.现在,我通过简单地从路径中提取一行数据,然后查找是否有任何相交来实现.但它具有O(n ^ 2)复杂度,因此它非常慢.有更快的方法吗？

我有一个凸多边形ABCDE ...(它可以有任意数量的点).我需要对它的所有顶点进行排序,这样任何边都不会相交.
例:

A _____ B
  \   /
   \ /
    X
   / \
  /___\
C       D

ABCD顺序的多边形具有交叉边.但是在ABDC订单中:

A _____ B
  |   |
  |   |
  |   |
  |   |
  |___|
C       D

没有边相交,所以ABDC是预期的输出.

我怎样才能做到这一点？

假设我们被给予少量的物体和它们之间的"距离" - 有什么算法可以将这些物体以近似这些距离的方式拟合到二维空间中的点上？

这里的困难在于"距离"不是欧几里德空间的距离 - 这就是为什么我们只能拟合/近似.

(对于那些对距离概念准确感兴趣的人,它是(有限)集的幂集上的对称距离度量).

我需要找到给定列表中三角形内的点数.这里的问题是,可能有多达一百万点.

我尝试了一种简单的方法:如果三角形的面积等于通过一次取两个三角形点形成的3个三角形的面积之和和要检查的点,则在其内部.这没有任何精度错误,因为我没有除以2来找到该区域.

但我需要更快的东西.目标是速度.是否可以通过某种预处理使其更快,忽略某些基于某些标准或类似的点？

编辑:忘了添加一个关键细节.一旦给出的点数是固定的.然后这些点是静态的,需要检查多达一百万个三角形......

编辑2:证明一个好的(也许是最佳的)方法是使用线扫描.不过,谢谢你的回答!

见上图; 基本上,我想要一个简单的测试来检查一个点是否在线段的范围内.我有的信息(或输入,如果您愿意)是点的坐标和线段终点的坐标.我想要的输出是一个简单的布尔值.我怎样才能以简单的方式检查这个？

假设我有两个盒子(每个盒子都是一个长方体,也就是长方体).我需要编写一个函数来判断尺寸为(a,b,c)的盒子是否可以放入尺寸为(A,B,C)的盒子中,假设允许任何角度旋转(不仅仅是90°) .

棘手的部分是内盒的边缘可能不平行于外盒的边缘.例如,如果沿着主对角线放置,则尺寸(a,b)非常薄但长度为1 <c <√3的盒子可以装入单位立方体(1,1,1 )中.

我见过问题[1],[2]但它们似乎只覆盖了90°的旋转.

我需要确定一组点(每个由浮点元组给出,每个都在[0,1]中)包含两个在彼此的某个阈值(例如0.01)内的点.我还要提一下,在我感兴趣的问题版本中,这些"点"由长度为〜30的元组给出,即它们是[0,1] ^ 30中的点.

我可以使用以下内容测试是否有任何两个在此阈值内:

def is_near(p1, p2):
    return sqrt(sum((x1 - x2)**2 for x1, x2 in zip(p1, p2))) < 0.01  # Threshold.

使用这个我可以使用以下内容检查每一对:

def contains_near(points):
     from itertools import combinations
     return any(is_near(p1, p2) for p1, p2 in combinations(points, r=2))

然而,这在列表的长度上是二次的,这对于我所拥有的长点列表来说太慢了.

有没有解决这个问题的方法？

我尝试过将这些点捕捉到网格中,这样我就可以使用字典/哈希映射来存储它们:

def contains_near_hash(points):
     seen = dict()
     for point in points:
         # The rescaling constant should be 1 / threshold.
         grid_point = tuple([round(x * 100, 0) for x in point])  
         if grid_point in seen:
             for other in seen[grid_point]:
                 if is_near(point, other):
                      return …

我的问题是:我们在2D空间中有N个点,每个点都有一个正重量.给定由两个实数a,b和一个整数k的查询,找到大小AXB的矩形的位置,与边缘平行于轴线,这样的前k个点,即,k个点具有最高权重的总和矩形覆盖的权重最大化？

任何建议表示赞赏.

PS:有两个相关的问题已经得到很好的研究:

• 最大区域总和:找到总权重最大的矩形.复杂性:NlogN.
• top-K查询正交范围:找到给定矩形中的top-k个点.复杂度:O(log(N)^ 2 + k).