我在圆周上有三个点:

pt A =(Ax,Ay); pt B =(Bx,By); pt C =(Cx,Cy);

如何计算圆的中心？

在Processing(Java)中实现它.

我找到了答案并实施了一个有效的解决方案:

pt A = (A.x, A.y);
pt B = (B.x, B.y);
pt C = (C.x, C.y);

我有一个详细的2D多边形(代表一个地理区域),它由一组非常大的顶点定义.我正在寻找一种算法,它将简化和平滑多边形(减少顶点的数量),其约束条件是生成的多边形的区域必须包含详细多边形的所有顶点.

对于上下文,这是一个复杂多边形边缘的示例:

我的研究:

• 我找到了Ramer-Douglas-Peucker算法,它将减少顶点的数量 - 但生成的多边形将不包含所有原始多边形的顶点.请参阅维基百科上的这篇文章Ramer-Douglas-Peucker

• 我考虑过扩展多边形(我相信这也称为向外多边形偏移).我发现了以下问题:扩展多边形(仅凸面)和膨胀多边形.但我不认为这会大大减少我的多边形的细节.

感谢您给我的任何建议!

给定一个二维平面,其中有n个点.我需要生成一个划分平面的线的方程,使得一侧有n/2个点,另一侧有n/2个点.(顺便说一句,这不是家庭工作,我只是想解决问题)

我有一个计算几何问题,我觉得应该有一个相对简单的解决方案,但我无法弄明白.

我需要确定由几个线段定义的区域的非凸轮廓.

我知道各种非凸壳体算法(例如alpha形状),但我不需要完全通用的算法,因为线段在大多数情况下定义了一个独特的解决方案.

正如@ Jean-FrançoisCorbett指出的那样,有些情况下有多种解决方案.我显然需要更多地考虑我的定义.

但是,我要做的是逆向工程并使用专有的文件格式,以便我可以对自己和其他人收集的数据进行基本分析.文件格式很简单,但确定用于定义边界的算法要困难得多.

放入导致非唯一解决方案的许多边缘情况会导致相关软件在没有警告的情况下崩溃或者无法读取文件.

因此,当存在多个解决方案时,要么生成一个可接受的解决方案,要么能够确定存在多个解决方案,这是可以接受的.

问题定义:

多边形的轮廓不应该穿过任何段,并且应该由连接所有段的端点的线组成.所有段必须完全位于多边形的边界内或沿着多边形的边界.大纲中不能使用多个端点(通过在需要多边形关闭的软件库的末尾添加第一个点来忽略"关闭"多边形.).

如果有多个解决方案符合此标准,那么任何一种解决方案都是可以接受的.(能够确定解决方案何时非唯一,这将是非常好的,但这不是绝对必要的.)

例子:

举个例子,我有以下几点:

我想描述以下几个方面:

它也适用于非交叉段.例如

我认为(？)在任何一种情况下都有一个独特的解决方案,符合之前的标准.(编辑:一般来说,没有一个独特的解决方案,正如@ Jean-FrançoisCorbett所指出的那样.但是,我仍然对能够产生一种可接受的解决方案的算法感兴趣.)

测试用例

对于测试用例,这是生成上述数字的代码.我在这里使用python,但问题是与语言无关.

import matplotlib.pyplot as plt

def main():
    test1()
    test2()
    plt.show()

def test1():
    """Intersecting segments."""
    segments = [[(1, 1), (1, 3)],
                [(3.7, 1), (2, 4)],
                [(2, 0), (3.7, 3)],
                [(4, 0), (4, 4)],
                [(4.3, 1), (4.3, 3)],
                [(0, 2), (6, 3)]]

    desired_outline = [segments[0][0], segments[5][0], segments[0][1], 
                       segments[1][1], segments[2][1], segments[3][1],
                       segments[4][1], segments[5][1], segments[4][0],
                       segments[3][0], segments[1][0], segments[2][0],
                       segments[0][0]]

    plot(segments, desired_outline)

def test2():
    """Non-intersecting segments."""
    segments …

我发现这个挑战问题说明如下:

假设XY平面上有n个矩形.编写一个程序来计算可以与在该平面上绘制的单条直线交叉的最大可能矩形数.

我一直在集思广益,但找不到任何解决方案.也许在某个阶段,我们使用动态编程步骤,但无法弄清楚如何开始.

编程语言R中最有效的方法是计算两个向量之间的角度？

如果你有2个点,(x1,y1)和(x2,y2),它们代表一个矩形的两个相对的角,还有另外两个点,(x3,y3)和(x4,y4),它们代表a的2个端点线段,如何检查线段是否与矩形相交？

(线段只是给定端点之间包含的段.它不是由这两个点定义的无限长度线.)

问题是:

给定具有x和y坐标的N个点(在2D中),找到点P(在N个给定点中),使得从其他(N-1)个点到P的距离之和最小.

这一点通常称为几何中位数.有没有有效的算法来解决这个问题,除了天真的算法O(N^2)？

我正在制作一个游戏,在那里我创建一个随机的省份地图(风险或外交).为了创建该地图,我首先生成一系列半随机点,然后计算这些点的Delaunay三角剖分.

完成后,我现在正在寻找创建点的Voronoi图表作为省边界的起点.此时我的数据(没有双关语)由原始的点系列和Delaunay三角形的集合组成.

我已经在网上看到过很多方法可以做到这一点,但是大多数方法都与Delaunay的衍生方式有关.我很想找到一些不需要集成到Delaunay的东西,但可以单独根据数据工作.如果做不到这一点,我正在寻找相对几何新手可以理解的东西,而不是最佳速度.谢谢!

我在2D空间中有一组矩形和任意形状.形状不是多边形(可以是圆形),矩形具有不同的宽度和高度.任务是使用尽可能接近的矩形近似形状.我无法更改矩形尺寸,但允许旋转.

这听起来非常类似于包装问题和覆盖问题,但覆盖区域不是矩形...

我想这是NP的问题,而且我很确定应该有一些论文显示出很好的启发式来解决它,但我不知道该怎么去谷歌？我应该从哪里开始？

更新:我想到了一个想法,但我不确定它是否值得调查.如果我们将形状限定为充满水的物理模具,该怎么办？每个矩形被认为是带有尺寸的带正电粒子.现在删除最小的矩形.然后在随机点放下下一个大小.如果矩形太近,它们会相互排斥.继续添加矩形直到全部使用.这种方法有用吗？