I’ve searched the forum and I can’t seem to find this topicso I will revisit it again.
I’ve got a 3D point and I would like to check if it is on a edge defined by two verticies. I am familiar with the on_line? method however this is not precise enough for me since the point may actually fall on the line in space but not actually be between the two endpoints.
I can’t seem to find a method to do this check but I might be missing something so again I bring the question to the forum.
The point_in_polygon method seems to work, see code below:
# Create a point that we want to check. (Note that the 3rd coordinate,
# the z, is ignored for purposes of the check.)
point = Geom::Point3d.new(5, 5, 10)
# Create a series of points of a triangle we want to check against.
triangle = []
triangle << Geom::Point3d.new(0, 0, 0)
triangle << Geom::Point3d.new(10, 10, 0)
# triangle << Geom::Point3d.new(0, 10, 0)
# Test to see if our point is inside the triangle, counting hits on
# the border as an intersection in this case.
hits_on_border_count = true
status = Geom.point_in_polygon_2D(point, triangle, hits_on_border_count)
Note that I have removed the third point and I am only checking along a line segment.
I would suggest to get 3 distances: 1) distance from a testing point to an edge starting point (say d1); 2) distance from a testing point to an edge ending point (say d2); 3) distance from an edge starting point to an ending point, i.e. edge length (say edge_len).
So testing point would be on an edge in case if d1+d2=edge_len.
Such way should take slightly less time to execute in contrast to Geom.point_in_polygon_2D method I guess.
In computer graphics one avoids distance computations because the square root takes a multiple of the time of simple arithmetric operations. Assuming the on_line? method is already efficiently implemented using the perpendicular dot product:
def point_on_line_segment(query_point, point1, point2)
[0, 1, 2].each{ |x| # For dimensions x, y, z
# If the query point is not in between the limits of the line segment this dimension, it cannot be on the line segment.
unless (point1[x] <= query_point[x] && query_point[x] <= point2[x])
|| (point2[x] <= query_point[x] && query_point[x] <= point1[x])
return false
end
}
# Otherwise the query point is within the bounding box, now check whether it is actually on the line.
return query_point.on_line?([point1, point2])
end
A singleton method added to the query point that tests the vector directions …
def point.query_between?(point1, point2)
point.on_line?([point1, point2]) &&
not point.vector_to(point1).samedirection?( point.vector_to(point2) )
end
… ie, if the query point is on the line and is between the two endpoints,
then the vectors will be pointing in opposite directions.
I don’t know if this is faster than Andreas’ idea or not.
This is an interesting solution to the problem.
Computationally how intensive is the point_in_polygon_2D method? Is there any information on this from SketchUp?
I did not test what happens if the query point is coincident with one of the endpoints.
Ie, one of vectors would have 0 length and no direction.
SketchUp does not give this kind of information.
You’ll have to do profiling, or run the a test a number of times and compute average time per call.
I am very surprised that it doesn’t raise an exception as a polygon needs 3 vertices min.
Referring to your 2nd post. The conclusion is invalid.
The points Z coordinate is just projected directly downwards on the ground plane.
The 2D check is not actually done in the plane of the points in question.
So, in reality, you get a false result as the polygon (line segment) is on the ground plane, but the point you are testing is actually 10 units above it.
So you must first check 3D-wise if the point in on plane (or line) before using the 2D projection test.
This did occur to me and it could potentially cause a problem where a wall line sits directly above another wall line and the plugin thinks one wall segment is intersecting a wall segment on a floor above it. As you suggest I will need to check if they are on the same plane if I choose to use this method.
Yes it’s true. But I think there is another considiration which should be kept in mind in regards to performance: Ruby code seems often to run slower, than some method provided by API. So in case if distance calculations would be performed by API methods (not by ruby code), the whole result may actually run faster. Anyway I think it can be still interesting to test performance of a distance method.
def point_on_line_segment2(query_point, point1, point2)
d1=query_point.distance(point1)
d2=query_point.distance(point2)
edg_len=point1.distance(point2)
on_edge=true
on_edge=false if edg_len<d1+d2
on_edge
endIt feels like method suggested by @DanRathbun will be the fastest, but I would suggest to enhance its robustness a little bit by adding a check for coincedences of a query point with segment points, because samedirection? method may raise an error in case if given vector and/or vector to check against has a zero length.
We noted this also… so …
def point_between?(point, point1, point2)
return true if point == point1 || point == point2
point.on_line?([point1, point2]) &&
not point.vector_to(point1).samedirection?( point.vector_to(point2) )
end
The args must be Geom::Point3d objects to leverage the == method to within SketchUp tolerance.
Ie, Array args must be converted to Geom::Point3d.
Seems like final edition of point_between? is the most appropriate solution so it can be marked as a solution (for those who may search forum for a similar topic).
What about to check the BoundingBox?
I think if you have an “edge” in the code already, this can be more simple like:
edge.bounds.contains?(query_point)
Or
def point_between2?(query_point, point1, point2)
boundingbox = Geom::BoundingBox.new
boundingbox.add(point1, point2)
return true if boundingbox.contains?(query_point)
end
I believe it is faster than methods above…
EDIT: It works only if the edge is paralel one of the global axes.
I’m afraid that bounding box is not enough to make sure that query point is on edge.
I’m afraid you are right!
I thought “Bounding boxes are only large enough to exactly bound the entities.” BUT I did not take into consideration “aligned with the global axes”.
So, my method works only if the edge is paralel one of the global axes… 
I think it is possible to add a query_point.on_line? check to a code that you suggested and it will become a modification of a method suggested by @Aerilius. Maybe it will be interesting to test performance of such edition as well.
Quick and dirty test.
(I hope I did not made a mistake)
#@Aerilius
def p_b2_Ae(qp, p1, p2)
[0, 1, 2].each{ |x| unless (p1[x] <= qp[x] && qp[x] <= p2[x]) || (p2[x] <= qp[x] && qp[x] <= p1[x])
return false
end
}
return qp.on_line?([p1, p2])
end
#@kirill200777
def p_b2_ki(qp, p1, p2)
d1=qp.distance(p1)
d2=qp.distance(p2)
edg_len=p1.distance(p2)
on_edge=true
on_edge=false if edg_len<d1+d2
on_edge
end
#@DanRathbun
def p_b2_Da(qp, p1, p2)
return true if qp == p1 || qp == p2
qp.on_line?([p1, p2]) && !qp.vector_to(p1).samedirection?(qp.vector_to(p2))
end
#@dezmo
def p_b2_De(qp, p1, p2)
boundingbox = Geom::BoundingBox.new
boundingbox.add( p1, p2)
boundingbox.contains?(qp) && qp.on_line?([p1, p2])
end
#Test
p1=[0,0,0];p2=[10,10,10]
(1..3).each{|i|
puts
qp=[0,0,0]if i==1
qp=[1,1,1] if i==2
qp=[0,0,100] if i==3
puts "Test #{i}: Is qp=#{qp} on the edge between p1=#{p1} & p2=#{p2}?"
start = Time.now
1000000.times{ p_b2_Ae(qp, p1, p2)}
puts "p_b2_Ae: #{Time.now-start} #{p_b2_Ae(qp, p1, p2)}"
start = Time.now
1000000.times{ p_b2_ki(qp, p1, p2)}
puts "p_b2_ki: #{Time.now-start} #{p_b2_ki(qp, p1, p2)}"
start = Time.now
1000000.times{ p_b2_Da(qp, p1, p2)}
puts "p_b2_Da: #{Time.now-start} #{p_b2_Da(qp, p1, p2)}"
start = Time.now
1000000.times{ p_b2_De(qp, p1, p2)}
puts "p_b2_De: #{Time.now-start} #{p_b2_De(qp, p1, p2)}"
puts
}
The tets result:
(DellM4700, corei7(gen4), NVIDIA QK1000M, W7/32bit, SU2014Pro)
Test 1: Is qp=[0, 0, 0] on the edge between p1=[0, 0, 0] & p2=[10, 10, 10]?
p_b2_Ae: 1.567784 true
p_b2_ki: 1.976988 true
p_b2_Da: 0.261131 true
p_b2_De: 2.170085 true
Test 2: Is qp=[1, 1, 1] on the edge between p1=[0, 0, 0] & p2=[10, 10, 10]?
p_b2_Ae: 1.588794 true
p_b2_ki: 1.944972 true
p_b2_Da: 2.897448 true
p_b2_De: 2.103051 true
Test 3: Is qp=[0, 0, 100] on the edge between p1=[0, 0, 0] & p2=[10, 10, 10]?
p_b2_Ae: 0.815408 false
p_b2_ki: 1.957978 false
p_b2_Da: 1.488744 false
p_b2_De: 1.238619 false
Interesting result, for sure depends on the points positions.
I don’t know exactly what the conclusions are…? 
I made some test and found that the quickest is
def point_within_segment_5?(pt, pt1, pt2)
x1, y1, z1 = pt1.to_a
x2, y2, z2 = pt2.to_a
x, y, z = pt.to_a
(x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2) >= (x1-x)*(x1-x) + (y1-y)*(y1-y) + (z1-z)*(z1-z) + (x2-x)*(x2-x) + (y2-y)*(y2-y) + (z2-z)*(z2-z)
endApparently, the Sketchup Ruby methods, even if it written in C, add some overhead.
The equivalent method below is more readable but slower
def point_within_segment_6?(pt, pt1, pt2)
(pt1.distance(pt2) >= pt.distance(pt1) + pt.distance(pt2))
endOn my machine, with 1 million trials
Fredo
Fascinating stuff.
So what is the final consensus on the best method to use?
I do find it a bit odd that this method or function is not part of the SU API, seems like it would be a handy tool to have at one’s disposal.
I think there is no final consensus. Different machines different result… even if the points are different position the results are vary. Maybe Dan’s method the fastest in the average, but not all the time.
@Fredo6 did not mentioned what was the points he have been tested with, but I’m sure there where “big” differences if the result is true or false, or the test point on the endpoint or not…
So here are ~6 different method and in a “normal daily usage” (?) we can use what we prefer personally…