Visual LISP, AutoLISP and General Customization

## Visual LISP, AutoLISP and General Customization

Contributor
Posts: 11
Registered: ‎02-21-2008
Message 11 of 12 (109 Views)

# Re: Steiner Tree Problem

11-22-2012 08:37 AM in reply to: owenp

Kent,

Thanks for this, I always get confused trying to use "foreach", and I still can't get my head around that if statement that checks for the greater than 120 degree angle, but I'm pleased it works. Well done.

Any chance it could be used to solve the 4 point problem, no matter where the four points are?

I'm so grateful for your help, I bit off more than I could chew with this project.

*Expert Elite*
Posts: 4,814
Registered: ‎09-13-2004
Message 12 of 12 (103 Views)

# Re: Steiner Tree Problem

11-22-2012 01:48 PM in reply to: owenp

owenp wrote:

....

Thanks for this, I always get confused trying to use "foreach", and I still can't get my head around that if statement that checks for the greater than 120 degree angle, but I'm pleased it works. Well done.

Any chance it could be used to solve the 4 point problem, no matter where the four points are?

....

The (if) about the 120-degree-or-larger angle doesn't do it by actually checking the angle.  It just checks whether the initially-calculated triangles-on-the-outside-based Fermat point falls outside the triangle, by comparing the distance from the vertex closest to it to one of the other vertices with the distance from the calculated Fermat point to that other vertex -- if the latter is greater, it's outside, or if it's equal, it's right on that closest vertex.  [To see where that calculated Fermat point falls outside, comment out that entire (if) function with the test, so it neither moves the fp point nor removes a vertex from the list of points before drawing the tree.]

I have a feeling the unlimited four-point problem is going to be a far more significant challenge for AutoLISP, involving a lot of comparisons of distances.  Maybe it can be done by solving the three-point case with each possible combination of three points, and somehow comparing the results.  Or it could be by solving for four points and testing whether the resulting tree extends outside the quadrilateral, though that could be a challenge for certain configurations, e.g. something like a Y arrangement of points.  But I'll play with it.

Kent Cooper

Recently Solved