标签: computational-geometry

我用 Graphics 对象绘制了一条线。我想根据鼠标拖动的程度将这条线旋转一定的角度。我可以获得旋转它所需的度数，但是我如何根据该角度旋转线呢？

谢谢你！

我有一个工作类，可以生成给定的正多边形：多边形中心、多边形半径和边数。两个私有成员函数的实现细节见这里。

类接口如下所示：

class RegularPolygon: public Closed_polyline{
public:
    RegularPolygon(Point c, int r, int n)
        : center(c), radius(r), sidesNumber(n) 
    { generatePoly(); }

private:
    Point center;
    int radius;
    int sidesNumber;
    void generatePoly();
    void rotateCoordinate(Point& axisOfRotation, Point& initial, 
                          double angRads, int numberOfRotations);
};

问题：

我被要求实现使用一组坐标¹生成正多边形的第二种方法。构造函数首先需要对传递的坐标执行有效性检查：

RegularPolygon(vector<Point>& vertices)
   :center(), radius(), sideNumber()
{
   // validity check of the elements of vertices
}

我最初的想法是：

1. 检查每对坐标是否产生相同的边长。
2. 检查每条线（由一对坐标生成）的相对方向。（它们彼此之间应成 360/多边形边角）

问题：

1. 我如何检查所有线是否都正确定向，即它们的相对方向？ 解决了
2. 是否有任何标准算法可以确定一组坐标是否是正多边形的顶点？

笔记：

检查[1] …

假设我在一个文件夹中有一堆不同大小的图像。目标是以空白最少的方式将图像放入多个页面（例如 A4）中。不应涉及任何压缩或调整大小。一些图像被旋转是可以接受的。
这是我想出的，但不尝试以任何方式“适合”图像：

montage *.jpg -mode concatenate -tile 2x2 -page A4 -geometry +20+20 out.pdf

是否可以使用 imagemagick 和 montage 开关？
我想计算几何算法应该改变上面命令的 2x2 和 +20+20 部分，对吗？

我正在开发一个需要坐标映射的项目 - 确定坐标点是否存在于一系列多边形中。映射的数量相当大 - 跨越 100 多个多边形的约 1000 万个坐标。

在继续之前，我已经查看了此处和此处的问题。这个问题并不多余，因为它涉及动态点和静态多边形。

我通过在 200 万个多边形的子集中映射单个坐标来缩小该问题的项目范围。这是我使用的代码：

from shapely.geometry import shape, Point

f = open('path/to/file.geojson', 'r')
data = json.loads(f.read())

point = Point(42.3847, -71.127411)
for feature in data['features']:
    polygon = shape(feature['geometry'])
    if polygon.contains(point):
        print(polygon)

迭代 200 万个多边形（在本例中为建筑足迹）大约需要 30 秒（时间太长）。

我也尝试过使用mplPath如下：

import matplotlib.path as mplPath

building_arrays = [np.array(data['features'][i]['geometry']['coordinates'][0])
                   for i, v in enumerate(tqdm(data['features']))]
bbPath_list = [mplPath.Path(building)
               for building in tqdm(building_arrays)]

for b in tqdm(bbPath_list):
    if b.contains_point((-71.1273842, 42.3847423)):
        print(b)

这大约需要 6 秒。一个改进，但考虑到我需要的映射量，仍然有点慢。 …

我正在尝试解决这个问题：http : //codeforces.com/problemset/problem/268/C

Manao 发明了一个新的数学术语——一组漂亮的点。如果满足以下条件，他称平面上的一组点是美丽的：

1. 集合中每个点的坐标都是整数。
2. 对于集合中的任意两点，它们之间的距离是非整数。

考虑所有满足不等式的点 (x,?y)：0???x???n; 0???y?m; x?+?y?>?0。选择它们的最大尺寸子集，使其也是一组漂亮的点。

输入

单行包含两个空格分隔的整数 n 和 m (1???n,?m???100)。

输出

在第一行打印一个整数——找到的漂亮集合的大小 k。在接下来的 k 行中的每一行中，打印一对空格分隔的整数——分别是集合中一个点的 x 和 y 坐标。

如果有多个最佳解决方案，您可以打印其中任何一个。

解决方案似乎非常简单。像这样

#include <cstdio>
main(){
    int i=-1,m,n;
    scanf("%d %d",&m,&n);
    m=(m>n)?n:m;
    printf("%d\n",m+1);
    while(i<m)
        printf("%d %d\n",++i,m-i-1);
}

我无法理解如何得出算法。你能帮忙吗？谢谢。

是否有任何特殊原因需要多个姿势(例如变化z或旋转)来获得相机矩阵的焦距和主点？换句话说,用单一姿势校准针孔相机是否足够？即通过保持校准对象的位置(比如标准棋盘)不变？

我需要编写和算法用水平等距线填充闭合多义线.

我用矩形和圆圈做了类似的事情,这里是后者的代码片段:

// circle parameters: center(point(0).x, point(0).y), radius
int offsetX = point(0).x + radius;
int offsetY = point(0).y + radius;
for(int i = -radius; i < radius; i += spacing){
    int ry = i;
    int rx = sqrt(double(radius*radius - ry*ry));
    // the parameters are pair of coordinates of the horizontal line
    fl_line(offsetX - rx, offsetY + i, 
            offsetX + rx, offsetY + i);
}

在闭合多义线的情况下,额外的难度(对我而言)是水平线的坐标不会从单个方程(圆,矩形的高度等)中提取,而是从方程中提取.具有相同"y"坐标的线,不会连续匹配.

题:

1. 你能否提供一些有关如何创建一个用水平线填充封闭多边形线的算法的见解？

我正在尝试从映射数据构建导航网格。其中一个步骤涉及将二值图像（其中 0 表示占用空间，1 表示空闲空间）转换为平面直线图。

我试图找出一种方法来做到这一点，这有点可靠。我目前的想法是使用 Canny 边缘检测器，然后通过 OpenCV 的 Hough 线变换运行它。但是，这并不能保证检测到的线以代表原始形状的方式连接。

可以安全地假设地图相对平滑，并且没有任何区域相互接触。

编辑 - 这是一个示例图像：

白色区域代表可用空间

黑色区域代表占用空间

我有一个Polygon对象，我正在寻找一种有效的方法来找到严格位于其内部（而不是其边界上）的任何点。最好的方法是什么？

我有以下想法，但我不太喜欢：

1. 对多边形进行三角测量并报告三角测量边之一上的点（太昂贵）。
2. 检查多边形的缠绕方向并报告位于距多边形边缘之一 epsilon 距离的点（在边缘情况下不起作用）。

我在python中绘制了一个角度

这是代码

x = [0,0.5,1]
y = [0,0.5,0]
plt.scatter(x,y)
plt.plot(x,y)
plt.show()

有没有办法以编程方式检查角度是否为直角？