About

As described on the polygon point generator page, the following script generates a point within a polygon by using an encompassing minimal circle to generate the points and then applying a select-reject algorithm to those generated points.

Code

wasPolygonPoint.lsl
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
list wasDualQuicksort(list a, list b) {
    if(llGetListLength(a) <= 1) return a+b;
 
    float pivot_a = llList2Float(a, 0);
    a = llDeleteSubList(a, 0, 0);
    vector pivot_b = llList2Vector(b, 0);
    b = llDeleteSubList(b, 0, 0);
 
    list less = [];
    list less_b = [];
    list more = [];
    list more_b = [];
 
    do {
        if(llList2Float(a, 0) > pivot_a) {
            less += llList2List(a, 0, 0);
            less_b += llList2List(b, 0, 0);
            jump continue;
        }
        more += llList2List(a, 0, 0);
        more_b += llList2List(b, 0, 0);
@continue;
        a = llDeleteSubList(a, 0, 0);
        b = llDeleteSubList(b, 0, 0);
    } while(llGetListLength(a));
    return wasDualQuicksort(less, less_b) + [ pivot_a ] + [ pivot_b ] + wasDualQuicksort(more, more_b);
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2014 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
// determines whether the segment AB intersects the segment CD
integer wasSegmentIntersect(vector A, vector B, vector C, vector D) {
    vector s1 = <B.x - A.x, B.y - A.y, B.z - A.z>;
    vector s2 = <D.x - C.x, D.y - C.y, D.y - C.z>;
 
    float d = (s1.x * s2.y -s2.x * s1.y);
 
    if(d == 0) return FALSE;
 
    float s = (s1.x * (A.y - C.y) - s1.y * (A.x - C.x)) / d;
    float t = (s2.x * (A.y - C.y) - s2.y * (A.x - C.x)) / d;
 
    // intersection at <A.x + (t * s1.x), A.y + (t * s1.y), A.z + (t * s1.z)>;
    return (integer)(s >= 0 && s <= 1 && t >= 0 && t <= 1 && 
            A.z + t*(B.z - A.z) == C.z + s*(D.z - C.z));
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
//    www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html    //
///////////////////////////////////////////////////////////////////////////
integer wasPointInPolygon(vector p, list polygon) {
    integer inside = FALSE;
    integer i = 0;
    integer nvert = llGetListLength(polygon);
    integer j = nvert-1;
    do {
        vector pi = llList2Vector(polygon, i);
        vector pj = llList2Vector(polygon, j);
        if ((pi.y > p.y) != (pj.y > p.y))
            if(p.x < (pj.x - pi.x) * (p.y - pi.y) / (pj.y - pi.y) + pi.x)
                inside = !inside;
        j = i++;
    } while(i<nvert);
    return inside;
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
//    www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html    //
///////////////////////////////////////////////////////////////////////////
list wasPointToPolygon(list polygon, vector point) {
    integer i = llGetListLength(polygon)-1;
    list l = [];
    do {
        l = llListInsertList(l, (list)llVecDist(point, llList2Vector(polygon, i)), 0);
    } while(--i>-1);
    l = wasDualQuicksort(l, polygon);
    return [llList2Float(l, 0), llList2Vector(l, 1)];
 
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
//    www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html    //
///////////////////////////////////////////////////////////////////////////
vector wasPolygonCentroid(list polygon, vector start, float tollerance, integer power) {
    // calculate the distance to the point farthest away from the start.
    list wpf = wasPointToPolygon(polygon, start);
    float dist = llList2Float(wpf, 0);
    vector next = llList2Vector(wpf, 1);
 
    // now calculate the next jump point
    next = start + ((dist/power)/dist) * (next-start);
 
    // if it falls withing the tollerance range, return it;
    if(llVecMag(start-next) < tollerance) return next;
    return wasPolygonCentroid(polygon, next, tollerance, power*power);
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2011 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
vector wasCirclePoint(float radius) {
    float x = llPow(-1, 1 + (integer) llFrand(2)) * llFrand(radius*2);
    float y = llPow(-1, 1 + (integer) llFrand(2)) * llFrand(radius*2);
    if(llPow(x,2) + llPow(y,2) <= llPow(radius,2))
        return <x, y, 0>;
    return wasCirclePoint(radius);
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2011 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
vector wasPolygonPoint(list polygon) {
    vector c = wasPolygonCentroid(polygon, llList2Vector(polygon, 0), 0.05, 2);
    float r = llList2Float(wasPointToPolygon(polygon, c), 0);
    vector d;
    do {
        d = c + wasCirclePoint(r);
    } while(wasPointInPolygon(d, polygon) == FALSE);
    return d;
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
// determines whether the path between the current positon m and the 
// computed next position d will intersect any two sides of the polygon
vector wasPolygonPath(vector m, list polygon) {
    integer c = llGetListLength(polygon) - 1;
    vector d = wasPolygonPoint(polygon);
    integer i = 0;
    do {
        vector s = llList2Vector(polygon, c);
        vector p = llList2Vector(polygon, c-1);
        // project in plane
        if(wasSegmentIntersect(
            <m.x, m.y, 0>, 
            <d.x, d.y, 0>, 
            <s.x, s.y, 0>, 
            <p.x, p.y, 0>))
            ++i;
    } while(--c > 0);
    if(i > 1) return wasPolygonPath(m, polygon);
    return d;
}
 
integer _targetID = 0;
moveTo(vector position) {
    llTargetRemove(_targetID);
    _targetID = llTarget(position, .1);
    llLookAt(position, .6, .6);
    llMoveToTarget(position, 1);    
}
 
///////////////////////////////////////////////////////////////////////////
// these points represent the coordinates of the points that define the  //
// contour (permimeter) of the polgyon                                   //
///////////////////////////////////////////////////////////////////////////
list polygonPoints = [
    <163.349121, 171.559189, 3400.894287>,
    <165.56424, 170.422821, 3400.894287>,
    <164.364594, 169.194382, 3400.894287>,
    <165.171875, 167.453903, 3400.894287>,
    <162.345123, 167.61731, 3400.894287> 
];
 
default
{
    state_entry() {
        llVolumeDetect(TRUE);
        // first move to any point within the polygon
        moveTo(wasPolygonPoint(polygonPoints));
    }
    at_target(integer tnum, vector targetpos, vector ourpos) {
        if(tnum != _targetID) return;
        // now perform additional ray-cast
        moveTo(wasPolygonPath(llGetPos(), polygonPoints));
    }
}

fuss/algorithms/geometry/point_generation/polygon/generators/circle.txt ยท Last modified: 2022/04/19 08:28 by 127.0.0.1

Access website using Tor Access website using i2p Wizardry and Steamworks PGP Key


For the contact, copyright, license, warranty and privacy terms for the usage of this website please see the contact, license, privacy, copyright.