5
$\begingroup$

For example on an object like a banana, a snake or a C shaped object.

Is there a way to find the 2 "endpoints" or the 2 vertices that are furthest apart using geometry nodes?

$\endgroup$
3
  • $\begingroup$ Important to clarify your metric: furthest apart in 3D space, or the longest route through the geometry? $\endgroup$
    – Robin Betts
    Feb 21 at 8:45
  • $\begingroup$ Preferrably longest route through the geometry. $\endgroup$
    – muckyu
    Feb 21 at 11:20
  • 1
    $\begingroup$ @muckyu can you make some example meshes, manually position the points that are further apart and explain the algorithm (e.g. draw a path from one to another) on why they are considered to be the furthest apart? That would make it a good question. For example, a "shortest path" could be used to get all possible paths through edges, and then pick the longest, but it's still not really "the longest path", because you could make it shorter by going through diagonals of the faces, and then shorter still by just arbitrarily traveling through the mesh. $\endgroup$ Feb 21 at 11:34

1 Answer 1

5
$\begingroup$

This is the most efficient way I could find: rather than measuring distances between each pair of points, I'm making a copy (copying has to be done in order to iterate on every possible pair - and a repeat zone is in general much slower than the old ways) and moving chosen point to the origin. Now the distance to this point is just the length of the position vector:

You can use this group like so:

Robin Betts' convex hull optimization:

$\endgroup$
6
  • 1
    $\begingroup$ Not sure... Could you reduce this to the same method on the convex hull? $\endgroup$
    – Robin Betts
    Feb 21 at 12:29
  • $\begingroup$ @RobinBetts good question! I think you're correct, this could be optimized by the convex hull. The simple proof being, that convex hull never creates (does it?) new points. $\endgroup$ Feb 21 at 13:49
  • 1
    $\begingroup$ @RobinBetts ...And for any point it's always another point that is the furthest, because if 2 points building in edge are in equal distance, than the edge is inside the sphere defined by this distance. The same goes for 3 points and a triangle. And if any point disappeared in convex hull, then that point was closer than some points on the hull... I think so but I'm still making some tests $\endgroup$ Feb 21 at 13:58
  • 1
    $\begingroup$ @muckyu see edit. $\endgroup$ Feb 22 at 9:33
  • 1
    $\begingroup$ +1 clever solution!! $\endgroup$
    – Chris
    Feb 23 at 8:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .