在给定方向上环绕等距点集

Question

让我们考虑一个二维（纬度、经度）点集。集合中的点等距（大约）相互距离为 0.1 degree \times 0.1 degree 。集合中的每个点都是边长 0.1 度的正方形网格的中心（即正方形两条对角线的交点）。每个方块都与相邻的方块相邻。

我们的目标是得到轮廓多边形的坐标，由给定方向的正方形网格的边界边形成（将用图说明）。此多边形内部 没有孔 。

让我们考虑一个大小为 10（点集）的样本数据集。

lat_x <- c(21.00749, 21.02675, 21.00396, 21.04602, 21.02317, 
           21.06524, 21.00008, 21.04247, 21.08454, 21.0192)

和

lon_y <- c(88.21993, 88.25369, 88.31292, 88.28740, 88.34669, 
           88.32118, 88.40608, 88.38045, 88.35494, 88.43984)

这是上面几点的粗略图，后面是一些插图，

上面样本中的黑点是 (lat,lon) 点。

蓝色方框是方格。

正方形的给定方向 (\theta) 是 $theta$=50 度。

我们的目标是获得轮廓多边形（黄色）的有序（顺时针或逆时针）坐标。

注意： 这个问题与非常相似，@laune 给出了一个很好的答案。目标是获得没有方向（或 0 度方向）的轮廓多边形。但在目前的设置中，我需要在绘制正方形网格和生成的多边形时包括方向（非零）。

非常感谢解决上述问题的任何人提供的任何建议、java 或 R 代码或有用的参考。

Answer 1

我会这样做：

可能是一些二维数组点分组来匹配网格

这应该会加快以下所有操作。
计算平均网格大小（左起 img1）

作为两个向量
创建蓝点(img2)

如：gray_point (+/-) 0.5*blue_vector
创建红点(img3)

如：blue_point (+/-) 0.5*red_vector
创建灰线列表(img4)

取距离接近平均网格距离的所有 2 个原始（灰色）点并为它们添加线
创建红线列表(img4)

取距离接近平均网格距离的所有 2 个原始（灰色）点，如果它不与灰色线的任何线相交，则为它们添加线
重新排序线点以匹配多边形缠绕...
角度

计算红色矢量的角度（通过 atan2）
计算蓝色矢量的角度（通过 atan2）
return绝对值小的那个

[edit1] 对评论的回复

网格大小

找到几个彼此最接近的点，所以选择任何一个点并找到所有最接近它的点。可能的距离应该接近：

sqrt(1.0)*d,sqrt(1+1)*d,sqrt(1+2)*d,sqrt(2+2)*d,...

其中 d 是网格大小，因此为几个选取的点计算 d。记住找到的第一个最小的 d 并丢弃所有与最小的不相似的。取它们的平均值并称其为 d

网格向量

取任意点 A 并找到离它最近的点 B，距离接近 d。例如+/-10%比较：|(|A-B|-d)|<=0.1*d现在网格向量是(B-A)。找到其中的几个（选择不同的 A,B）并按 x,y 坐标的符号将它们分成 4 组。

然后通过取反一组向量将负方向组连接在一起，这样您将有 2 个向量列表（红色、蓝色方向）并从中生成平均向量（红色、蓝色向量）

换点

你取任意点 A 并向其添加或减去一半红色或蓝色向量（不是它的大小！！！）例如：

A.x+=0.5*red_vector.x;
A.y+=0.5*red_vector.y;

行列表

每 2 点组合 A,B 嵌套 2 个 for（灰线为原始线，红色轮廓线为红色线）并添加距离条件

|(|A-B|-d)|<=0.1*d

如果是 true，将行 (A,B) 添加到列表中。这里是伪 C++ 示例：

    int i,j,N=?;       // N is number of input points in pnt[]
    double x,y,d=?,dd=d*d,de=0.1*d; // d is the avg grid size
    double pnt[N][2]=?;    // your 2D points
    for (i=0;i<N;i++)      // i - all points
     for (j=i+1;j<N;j++)   // j - just the rest no need to test already tested combinations
       {
       x=pnt[i][0]-pnt[j][0];
       y=pnt[i][1]-pnt[j][1];
       if (fabs((x*x)+(y*y)-dd)<=de) ... // add line pnt[i],pnt[j] to the list...
       }

在给定方向上环绕等距点集

Wraping of equispaced point set in a given direction

java

algorithm

r

geospatial

graph-algorithm