Detect if a point is within the convex hull of a list of points.

[Quistess Alpha]

This was kinda fun to think through.

integer within_hull(vector test, list points)
{   integer ind_a= 0;
    integer ind_b= 1;
    integer ind_c= 2; // indexes for 3 points from points.
    vector a = llList2Vector(points,ind_a);
    vector b = llList2Vector(points,ind_b);
    vector c = llList2Vector(points,ind_c);
    integer len = llGetListLength(points);
    // for all pairs of 3 points a,b,c:
    while(ind_c<len)
    {
        vector normal = (b-a)%(c-a);
        integer side = (test-a)*normal >0; // on which side of the plane defined by a,b,c is test?
        integer outside = TRUE; //early return variable.
        integer ind_p = len;
        // for each other point p:
        while(~--ind_p)
        {   if(ind_p!=ind_a && ind_p!=ind_b && ind_p!=ind_c)
            {   vector p = llList2Vector(points,ind_p);
                if( (((p-a)*normal)>0) != side)
                {   //llOwnerSay("point del");
                    // p is on opposite side from test:
                    // remove it from list.
                    points = llDeleteSubList(points,ind_p,ind_p);
                    // fix indexes!
                    --len;
                    if(ind_c>ind_p) --ind_c;
                    if(ind_b>ind_p) --ind_b;
                    if(ind_a>ind_p) --ind_a; 
                }else
                {   // it is possible test is within points:
                    outside = FALSE;
                }
            }
        }
        if(outside) // there were no points on the same side of a,b,c as test, therefore it is impossible it is within the cloud:
        {   return FALSE;
        }
        
        // set indexes for next loop:
        if((ind_a+1)<ind_b)
        {   a = llList2Vector(points,++ind_a);
        }else
        {   a = llList2Vector(points,ind_a=0);
            if((ind_b+1)<ind_c)
            {   b = llList2Vector(points,++ind_b);
            }else
            {   b = llList2Vector(points,ind_b=1);
                c = llList2Vector(points,++ind_c);
            }
        }
        //llOwnerSay("Debug: "+llList2CSV([ind_a,ind_b,ind_c]));
    }
    // either the initial point list had fewer than 4 points, or test is within the convex hull:
    return TRUE;
}


default
{

    touch_start(integer total_number)
    {
        // for debug, determine if this object is within the convex hull of all nearby objects named "Test Point"
        llSensor("Test Point","",PASSIVE,7.0,PI);
    }
    sensor(integer n)
    {   llOwnerSay("Found "+(string)n+" test points.");
        list points;
        while(~--n)
        {   points+=llDetectedPos(n);
        }
        integer inside = within_hull(llGetPos(),points);
        if(inside)
        {   llOwnerSay("Within hull!");
        }else
        {   llOwnerSay("Out of bounds!");
        }
    }
}

I'm pretty sure it works, but I didn't test it super rigorously.

[animats]

I think I see what's going on there.

If you can turn the point cloud into a mesh of triangles, it's much faster to run this test.

Convex hull vs. convex hull is amazingly cheap to compute, but I would not want to have to implement it in LSL.