标签: computational-geometry

如何测试一条线是否有一个位于三角形内(而不是边缘)的点.(全部为2D).

目前我在想我会这样做:

• 定义直线,三角形的每一边为Ax + By + C = 0,并有一个xrange.
• 检查线是否与三角形的任何线相交.
• 如果是,请检查这不是在行的末尾.

有一个更好的方法吗？

我将处理数以千计的问题。我可以实现或使用Fortunes算法的现有实现来生成点的Voronoi图，但是我的应用程序还要求我了解每个Voronoi单元的邻接关系。

更具体地说，对于任何Voronoi细胞，我需要知道与之相邻的细胞。在这一点上，我不必担心输出或存储方法，因为我很可能可以对实现进行优化以使其对我有利。

有谁知道一种算法，或者更好地意识到一种可以完成小区邻接确定的算法？我将做的工作是在python中进行，但是任何事情都将是很棒的，因为我可以轻松地翻译代码。

谢谢！

我有一组(x,y)点,我想从这些点插入任何点"内部"这一点的值.(下图中的黄色区域).

问题是我找不到任何好办法:

1. 找到将成为插值点边界的多边形(绿线)
2. 测试点是否在多边形内部.我找到了Point in Polygon算法,但我不确定在一定范围内取得所有点并测试它们是否属于多边形是一个好主意.我想找到一种方法让我测试的点数少于(max(x)-min(x))*(max(y)-min(y)),理想情况下是一种知道哪些点到做我的迭代.

编辑:在第二部分我正在迭代图像中的所有点(像素),我想要做的只是迭代黄色字段中的点.

你有领导吗？

Ps:如果有任何帮助,我用C++编写代码.

在下面绘制的2D数组中,我们有兴趣找到"肿块"区域.正如您所看到的,它不是一个连续的图形.此外,我们知道"肿块"区域的大致尺寸.下面给出了一组数据.第一列包含y值,第二列包含x值.关于如何检测像这样的肿块区域的任何建议？

   21048        -980
   21044        -956
   21040        -928
   21036        -904
   21028        -880
   21016        -856
   21016        -832
   21016        -808
   21004        -784
   21004        -760
   20996        -736
   20996        -712
   20992        -684
   20984        -660
   20980        -636
   20968        -612
   20968        -588
   20964        -564
   20956        -540
   20956        -516
   20952        -492
   20948        -468
   20940        -440
   20936        -416
   20932        -392
   20928        -368
   20924        -344
   20920        -320
   20912        -296
   20912        -272
   20908        -248
   20904        -224
   20900        -200
   20900        -176
   20896        -152
   20888        -128
   20888        -104
   20884         -80
   20872         -52
   20864 …

我有3个随机点,需要相对于它们形成的平面法线(其中一个)逆时针顺序排序.

所以问题是:我有分数,我有正常 - 我如何逆时针订购它们？

我已经看过这篇关于使用极地形式的帖子,但我不确定这是否是我想要的,我应该使用什么点.

给定n个点,其中没有三个是共线的.i和j,如果用i&j作为直径形成的圆不包含任何其他点,则2分是朋友.在O(nlogn)中给出所有这些点

问题如下: -

给你N个不同大象的生命时间,表示为一对整数.

恩.[5,10] [6,15] [2,7]意味着,一只大象从5年级到10年级生活.第二只大象从6年级到15年级,依此类推.

您可以假设大象最多只能活M年.(不是问题的一部分,但我们可能需要它来表示算法的复杂性.)

根据这些数据,找出最大数量的大象居住的年份.任意解决关系.

我已经尝试了几种方法,但没有任何实质性的东西可以打败天真的解决方案的复杂性.天真的解决方案是: -

1. Maintain an array(call it ctr).
2. For every set you encounter, 
    increment all values of ctr in that range.
3. Once you have traversed all sets, 
    find the index with the highest value in ctr.

很容易看出复杂性将是O(N*M).

有人能提供更好的解决方案吗？

另一个问题是:是否存在可以在O(1)时间内更改值范围的数据结构？在数组中,要修改k个元素,您显然需要O(k)时间.还有什么更好的？

Hilbert空间/平面填充曲线是否有任何扩展,将非正方形表面映射到矢量/线[用于图像映射到矢量]？

我搜索非迭代，封闭形式的算法，以找到最接近3d线集合的点的最小二乘解。它类似于3d点三角剖分（以最大程度地减少重新投影），但似乎更简单，更快？

线可以以任何形式描述，即2点，点和单位方向或类似形式。

一个农民有n只山羊.巧合的是,他还在一个他希望山羊放牧的地方有固定岗位.他想把每只山羊绑在一根绳子上.他想给每个山羊尽可能多的回旋余地地 - 但是,羊的绳索是臭名昭著的纠缠不清,所以他不能让任何山羊可以漫步到另一只山羊的领地.他可能使用的最大绳索数量是多少？(这个问题最多会有50只山羊)

思考了一会后,我不知道如何解决这个问题.谢谢回答.

(原始问题:https://open.kattis.com/problems/goatropes)