Yep, on any plane
Here is the rough test code: make a selection of n coplanar guide points on any face, type 'graham' in the console and it draws the convex hull correctly. As you will see, code is yours almost entirely. It's likely there is something wrong in my classes or methods.
def graham()
pts=[]
# Selection of coplanar guide points to array pts
Sketchup.active_model.selection.each { |cp| pts.push(cp.position) }
# Transform points to horizontal plane
t1=Geom;;Transformation.new(pts[0],pts[0].vector_to(pts[1]),pts[0].vector_to(pts[2]))
horizPoints = pts.map { |pt| pt.transform(t1.inverse) }
# Sort by X and Y
points = sort_points_by_x_y(horizPoints)
# Graham
l_upper = [ points[0], points[1] ]
2.upto(points.length - 1) do |i|
l_upper << points[i]
while l_upper.length > 2 && !right_turn?(l_upper.last(3))
l_upper.delete_at(-2)
end
end
l_lower = [ points[-1], points[-2] ]
(points.length - 3).downto(0) do |i|
l_lower << points[i]
while l_lower.length > 2 && !right_turn?(l_lower.last(3))
l_lower.delete_at(-2)
end
end
l_lower.delete_at(0)
l_lower.delete_at(-1)
# Reset convex hull to its original transform
hull=(l_upper + l_lower).map! { |pt| pt.transform(t1) }
# draw hull
Sketchup.active_model.entities.add_line(hull)
Sketchup.active_model.entities.add_line(hull.last,hull.first)
end
def right_turn?(points)
p, q, r = points
return (determinant_3x3([1,p.x,p.y,1,q.x,q.y,1,r.x,r.y]) < 0.0)
end
def determinant_3x3(array)
a,b,c,d,e,f,g,h,i = array
return ((a*e*i) - (a*f*h) + (b*f*g) - (b*d*i) + (c*d*h) - (c*e*g))
end
def sort_points_by_x_y(points)
return points.sort! { |a,b| a.x==b.x ? a.y <=> b.y ; a.x <=> b.x }
end
Offline
