标签: line-segment

我需要一个基本函数来找到点和线段之间的最短距离.随意用您想要的任何语言编写解决方案; 我可以把它翻译成我正在使用的(Javascript).

编辑:我的线段由两个端点定义.所以我的线段AB由两点A (x1,y1)和B (x2,y2).我试图找到这个线段和一个点之间的距离C (x3,y3).我的几何技能很生疏,所以我看到的例子令人困惑,我很遗憾地承认.

给定两条共线线段AB和CD,如何找到它们是否重叠？如何找到重叠的起点和终点？

以下是我正在使用的方法.我首先确保A <B和C <D.

if(pa < pc){
  if(pc < pb){
    if(pd < pb){
      //  overlap exists; CD falls entirely within AB
    }
    else {
      //  overlap exists; CB is the overlapping segment
    }
  }
  else {
    //  no overlap exists; AB lies before CD
  }
}
else {
  if(pa < pd){
    if(pb < pd){
      //  overlap exists; AB lies entirely within CD
    }
    else {
      //  overlap exists; AD is the overlapping segment
    }
  }
  else {
    //  no overlap …

我在这里发布了一个相关但不一样的问题/sf/ask/579578891/

背景:我有很多图片看起来像这样:

我想识别所有共线的线段,然后测量这些线段的长度.在上图中,有3对段位于具有负斜率的假想线上.最长的线段没有一对因此不会被考虑,即必须至少有2个共线段.

我得到以下内容:

I  = imread('http://dl.dropbox.com/u/18072545/c_39_green.tif'); 
BW = edge(I,'canny');
[H,T,R] = hough(BW);
NUMPEAKS=15;
PEAKTHRESHOLD= 80; 
SUPPRESSNHBR=[40 40];
P  = houghpeaks(H,NUMPEAKS,'threshold',PEAKTHRESHOLD,'NHoodSize',SUPPRESSNHBR); 
MINLENGTH_OF_SEGMENT=50;
GAPLENGTH_TO_MERGE=30;
lines = houghlines(BW,T,R,P,'FillGap',GAPLENGTH_TO_MERGE,'MinLength',MINLENGTH_OF_SEGMENT);
max_len = 0;
figure, imshow(I), hold on
for k = 1:length(lines)
  xy = [lines(k).point1; lines(k).point2];
  plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','green');
  plot(xy(1,1),xy(1,2),'x','LineWidth',2,'Color','yellow');
  plot(xy(2,1),xy(2,2),'x','LineWidth',2,'Color','red');
end

我不得不玩这些参数以获得合理的性能(尽管我无法找到一个参数来捕获位于底部的段的起始位).但是,我无法避免找到多个重叠的段.

有人可以帮助我1.防止识别重叠的部分.2.识别所有共线的线

非常感谢!

在C#或Java中是否存在任何现有的Bentley-Ottmann算法实现/库？

我有两组n个节点.现在我想将一组中的每个节点与另一组中的另一个节点连接起来.结果图应该没有交叉点.

我知道几种扫描线算法(Bentley-Ottmann-Algorithm来检查交叉点发生的位置,但除了蛮力方法之外,我找不到解决这些交叉点的​​算法.

一组中的每个节点可以连接到另一组中的任何其他节点.

任何解决这个问题的(一种有效的)算法的指针？无需实施.

编辑1:

以下是该问题的一种解决方案n=7:

黑点是一组节点,红点是一组.每个黑色节点必须连接到一个红色节点,以便连接它们的线不交叉.

EDIT2:

为了进一步说明:所有节点的位置都是固定的,结果图将有n个边.我也没有任何证据证明存在解决方案,但我无法创建一个没有解决方案的例子.我确信在那里有一个证据可以创建这样一个平面图.此外,只需要一种解决方案,而不是所有可能的解决方案.

Suppose I have a set of 2d line segments that are all connected. I need an algorithm that finds the outermost segments in the set. That is, the minimal subset that bounds the same region.

Note: this is not the same as finding the convex hull of the points making up the segments.

Edit: On the top is the initial set of segments. Below that is the same outline with interior segments deleted. (Ignore the little grey crosses, they're just …

我正在解析一些数据，这些数据以线段数组的形式给出，这些线段描述了几个闭合的任意形状/多边形。这些形状可以是凹形的。这是我正在查看的简化示例：

但是，我提供的数据具有任意顺序的段。根据示例，我的数据将类似于{V,E,D,X,U,A,Z,C,B,W,Y}。因此，绘制线段将显示正确的形状，但是对形状进行任何操作都不会变得容易。

我正在尝试对上面的数组进行排序，以使每个闭合形状的线段都按照连接顺序排列，并且每个形状的线段都组合在一起。

所以

{V,E,D,X,U,A,Z,C,B,W,Y}

会成为

[ {A,B,C,D,E} , {X,Y,Z} , {U,V,W} ]

每组线段的顺序对我来说都无关紧要，只是各个线段是按顺序排列的。我也不关心每组的特定开始部分。

以便

[ {Y,Z,X} , {C,D,E,A,B} , {W,U,V} ]

同样有效。

我没有遍历几何的经验，而我的基本尝试和粗略的在线搜索并没有提供任何快速解决方案。我调查了凹壳，但是鉴于数据已经知道这些点之间的联系，这似乎有些过分。

我正在寻找Python函数，它可以计算从3D中的点（x_0，y_0，z_0）到由其端点（x_1，y_1，z_1）和（x_2，y_2，z_2）定义的线段的距离。

我只找到了这个问题的 2D 解决方案。

有一些解决方案可以找到 3d 中点到线的距离，但不能找到线段的距离，如下所示：

（图片取自特殊情况下计算点到线段的距离）

我有一条光线,我需要找到它所触及的最近的线段.如果我先对行段进行排序,我认为可以在O(log n)时间内执行此操作,但我不记得如何对它们进行排序...我认为某种树最适合,但我如何排序它们的起点和终点都是？如果可能的话,我还想快速插入这个数据结构.

一条光线与一条线段有很多代​​码,但我需要一条光线对比很多线段...我不知道google的条款.

指向相应文章的链接很好,C++代码甚至更好.谢谢!:)

PS:线段实际上是非自相交多边形的边缘,按CCW顺序排序......但我认为以不同的方式对它们进行排序可能有一些优势？

这都是2D.

第二个想法,我不完全确定这是可能的.某种空间分区可能有所帮助,但除此之外,我无法想出任何方式对线进行排序,以便可以将它们与任意射线进行比较.

在Java中,如何使用PathIterator迭代约束条件的线段Area？该Area仅由线的约束(但曲线的支持不会伤害).

该方法应返回所有线段的集合.

只需检查\xef\xbc\x8c就不需要找到点了。
\n坐标 z 不= 0。\n堆栈溢出中的老问题都是关于 2d 的。\n提前感谢

我在二维空间中有一个正方形（宽度=高度）。该正方形当前由两个点定义：BottomLeft(X1,Y1) 和 TopRight(X2,Y2)。

正方形是轴对齐的，因此找到其他两个角就像 (X1, Y2) 和 (X2, Y1) 一样简单。

我还有两点——一是总是在方阵内，二是肯定在方阵外。它们不一定位于广场的中心——它们可以位于任何地方。我也知道他们的坐标。

我需要的是找到这两点定义的线段与正方形边之间的交点。我还想知道我与正方形的哪一边相交。给我带来麻烦的是线对角线延伸并且靠近正方形角的情况 - 例如它可以与顶线或边线相交。

暴力法是尝试计算正方形每条边的交点并检查它是否存在。可以通过计算第二个点相对于正方形的位置并丢弃两条线来优化它（例如，如果 X 和 Y 坐标都增加，则无需检查正方形的底部和左侧）。

我想知道是否有更好/更快的解决方案来解决我的问题？我会用Java写

我有一个大小为 10x10 的 2D 单元格数组，以及许多成对浮点值的点，例如：(1.6, 1.54), (4.53, 3.23)。对 (x,y) 使得 x<10 和 y<10

每个单元格取其坐标与单元格坐标具有相同整数部分的点。所以 arr[3][7] 将取 x={3...3.99(9)} 和 y={7...7.99(9)} 的点，例如 (3.5, 7.1) 或 (3.2, 7.6 ）。类似地， (1.6, 1.54) 在 arr[1][1] 中，(4.53, 3.23) 在 arr[4][3] 中，等等。

每个点在数组中都有一个很容易找到的指定位置，因为我只需要将 x 和 y 转换为 int 即可去掉小数点。

但我想找到数组中的哪些单元格与两点 A(x,y) 和 B(x,y) 之间的线段相交。

例如：A(1.5, 2.5) 和 B(4.3, 3.2) 用索引 [1][2]、[2][2]、[3,3] 和 [3,4] 交叉数组中的单元格

有什么算法吗？

这是一个类似的问题： 网格中的单元格被一条线交叉（PHP）