如何删除远离段的点？ [英] How to remove points that are far from a segment?
问题描述
我在这里阅读了如何保持两点之间的点（即：属于段的一部分，有些不精确）：我怎么知道一个点是否在某条线附近？
I read how to keep points that are between two points (ie. : that are part of a segment, with some imprecision) here : How can I tell if a point is nearby a certain line?
因此，我用Java实现了这个小算法，我的代码是（请注意变量的名称应该是明确的！:)：
Thus, I implemented this little algorithm in Java, and my code is (note that the variables' name should be clear for you ! :) ) :
List<Cupple> returned = new ArrayList<>(points_to_test);
for(Cupple c : points_to_test) {
/*if(c == segment_first_point || c == segment_last_point) {
continue;
}*/
if(Math.abs(Math.abs(
(segment_last_point.getNumber(0) - segment_first_point.getNumber(0))
*
(segment_first_point.getNumber(1) - c.getNumber(1))
-
(segment_first_point.getNumber(0) - c.getNumber(0))
*
(segment_last_point.getNumber(1) - segment_first_point.getNumber(1))
)
/
Math.sqrt(
Math.pow((segment_last_point.getNumber(0) - segment_first_point.getNumber(0)), 2)
+
Math.pow((segment_last_point.getNumber(1) - segment_first_point.getNumber(1)), 2)
)
) > maximal_allowed_distance) {
returned.remove(c);
}
}
return returned;
确定您理解：
-
返回是包含在段上或段附近的点的列表（以及确定的不精确/最大距离）如果一个点超出该段是变量：maximal_allowed_distance）
returnedis the list with points that are on the segment, or near the segment (and the "imprecision" / maximal distance that determine if a point is out of the segment is the variable :maximal_allowed_distance)
points_to_test 是我的图表中存在的所有点：我的段+段中真正的点+几乎在段上的点（< = maximal_allowed_distance ）+远离细分的点数（> maximal_allowed_distance ）。 我的小算法的想法是我删除所有后者。
points_to_test are ALL the points that are present in my graph : the both of my segment + the points that are really on the segment + the points that are almost on the segment (<= maximal_allowed_distance) + the points that are far from the segment (> maximal_allowed_distance). The idea of my little algorithm is that I remove all the latter.
segment_ [first | last] ] _point 是两个部分的极端
c 是当前点 points_to_test 我想知道它是远离段还是（根据 maximal_allowed_distance ）
c is the current point of points_to_test and I want to know if it is far from the segment or in (according to the maximal_allowed_distance)
getNumber（0）返回点的X坐标， getNumber（1）返回Y值。
getNumber(0) returns the X coordinate of the point, getNumber(1) returns the Y one.
但是，它不起作用。它没有返回优点（即：分段中的分数，考虑到 maximal_allowed_distance ）。
However, it does not work. It doesn't return the good points (ie. : the points that are in the segment, taking account of maximal_allowed_distance).
你知道我是否误解了我在这个问题的第一行给你的答案吗？你看到我自己实现这个算法有什么错误吗？
Do you know if I misunderstood the answer I gave you in the first line of this question ? Do you see any mistake in my own implementation of this algorithm ?
推荐答案
注意，引用的方法确定距无限线的距离。如果您只需要有限段附近的点，您可以修改它。
Note, that cited method determines distance from infinite line. If you need points near limited segment only, you would modify it.
在任何情况下算法都应该找到远离该线的点。如果不这样做，请检查
a）是否找到要删除的点数
b）是否能够删除对象 c 属于 points_to_test 列表，从返回列表
In any case algorithm should find points far from the line. If it does not do this, check
a) whether it ever finds points to remove
b) whether it is able to remove object c that belongs to points_to_test list, from returned list
编辑
有一种相当有效的方法来查找点和线段之间的距离使用矢量算术
// Copyright 2001 softSurfer, 2012 Dan Sunday
// This code may be freely used, distributed and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.
// Assume that classes are already given for the objects:
// Point and Vector with
// coordinates {float x, y, z;} (z=0 for 2D)
// appropriate operators for:
// Point = Point ± Vector
// Vector = Point - Point
// Vector = Scalar * Vector
// Line with defining endpoints {Point P0, P1;}
// Segment with defining endpoints {Point P0, P1;}
//===================================================================
// dot product (3D) which allows vector operations in arguments
#define dot(u,v) ((u).x * (v).x + (u).y * (v).y + (u).z * (v).z)
#define norm(v) sqrt(dot(v,v)) // norm = length of vector
#define d(u,v) norm(u-v) // distance = norm of difference
// dist_Point_to_Segment(): get the distance of a point to a segment
// Input: a Point P and a Segment S (in any dimension)
// Return: the shortest distance from P to S
float
dist_Point_to_Segment( Point P, Segment S)
{
Vector v = S.P1 - S.P0;
Vector w = P - S.P0;
double c1 = dot(w,v);
if ( c1 <= 0 )
return d(P, S.P0);
double c2 = dot(v,v);
if ( c2 <= c1 )
return d(P, S.P1);
double b = c1 / c2;
Point Pb = S.P0 + b * v;
return d(P, Pb);
}
这篇关于如何删除远离段的点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
