PolyDetector

Detect all closed polygons given a set of line segments

Update

Repeat poly detection by cutting the detected polygon/cycle ears (free point connected to two lines), eliminating the detected lines picked two times and collinear remaining lines until no cycle is detected.

Speed

See how fast it is:

$ time ./app

nPolys:241 dissolveSteps:2 lines:514

real 0m0.080s

user 0m0.063s

sys 0m0.016s

#

Motivation

Originally I tried the approach of Alfredo Ferreira (https://web.ist.utl.pt/alfredo.ferreira/publications/12EPCG-PolygonDetection.pdf) and for the lines from main.cpp it took more than 15 minutes! Plus that it uses a few matrixes with the size of the number of vertives squared!

While it is impossible to use, I began simplifying the algorithm using a recursion algorightm (see function BuildCycle() ).

I kept the original idea of breaking the line segments by their intersections, but without the sweep line method.

It makes sure that no line segments are crossed (collinear) and that the polygon is convex. Plus that each line segment point is taken maximum 2 times (it is connected to another line segment).

With a bit of care, the algo can be optimized at least ten times (remove recursion, precompute similar points using indices, we already know the intersections (optimize AddLineId), ...), but I leave that as a homework ;) Right now the detector has no limitation and by optimizing it, it could be used for very large line sets.

PolyDetector can be reused by taking advantage of the caching previously done (processed set, neighbors graph ...).

bool PolyCycle::AddLineId(PolyDetector &pd, uint32_t id)
{
    auto l = pd.findLine(id);
    if (!l) return false;

    l->test0 = 0; // a cnt
    l->test1 = 0; // b cnt

    for (auto &id1 : idx)
    {
        auto l1 = pd.findLine(id1);
        if (!l1) continue;

        if (!pointsDiffer(l->a, l1->a) || !pointsDiffer(l->a, l1->b))
        {
            if (Collinear(l->a, l1->a, l1->b) && Collinear(l->b, l1->a, l1->b)) // collinear points
                return false;
            l->test0++;
        }
        if (!pointsDiffer(l->b, l1->a) || !pointsDiffer(l->b, l1->b))
        {
            if (Collinear(l->a, l1->a, l1->b) && Collinear(l->b, l1->a, l1->b)) // collinear points
                return false;
            l->test1++;
        }

        if (l->test0 >= 2 || l->test1 >= 2)
        {
            //logoutf("line %u can't be added to cycle! ta:%d tb:%d ids: [%s]", id, l->test0, l->test1, idxToString().c_str());
            return false;
        }

        PolyLine ls(l->center, l1->center);
        for (auto &id2 : idx)
        {
            if (id2 != id && id2 != id1)
            {
                auto l2 = pd.findLine(id2);
                if (l2 && ls.PolyIntersects(*l2))
                {
                    return false;
                }
            }
        }
    }
    idx.insert(id);
    return true;
}

bool PolyDetector::BuildCycle(uint32_t id, PolyCycle cycle) // as value!
{
    //if (cycle.idx.size() >= 15) // limit the number of poly edges? maybe someone needs that
    //    return true;

    auto l = findLine(id);
    if (!l)
        return true;

    if (_neighbors[id].size() < 4) // connected / line splitted
    {
        return true;
    }

    if (!silent)
        cycle.print((std::string("[PROC:") + std::to_string(id) + std::string("]")).c_str());

    // cycle closed! -> cache it
    if (cycle.canBeClosed(id))
    {
        cycle.isClosed = true;

        if (!silent)
            cycle.print("[CLOSED] ");

        if (!similarCycle(_cycles, cycle))
        {
            _cycles.push_back(cycle);
            if (!silent)
                cycle.print("[ACCEPTED] ");
            //logoutf("nCycles:%u", uint32_t(_cycles.size()));
        }
        else
        {
            if (!silent)
                cycle.print("[CYCLE_EXISTS] ");
        }

        return true;
    }

    // the cycle should be discarded
    if (!cycle.AddLineId(*this, l->id))
    {
        return true;
    }

    // don't return to the same path again
    if (CycleProcessed(cycle.idx))
    {
        if (!silent)
            cycle.print("[PROCESSED!] ");
        return true;
    }
    processed.insert(cycle.idx);

    // recur neighbors
    for (auto &nid : _neighbors[id])
    {
        if (_neighbors[nid].size() < 4) continue;
        if (cycle.canBeClosed(nid) || !cycle.contains(nid))
        {
            if (!silent)
                cycle.print((std::string("[NEIGN:") + std::to_string(nid) + std::string("]")).c_str());
            BuildCycle(nid, cycle); // recur
        }
    }

    return true;
}

Very simple line neighbor graph, where the key is [line id] and the value is a [list of neighbors], sorted by the line segment center distance!

// Build neighbors
    std::vector<uint32_t> neigh;
    _neighbors.clear();
    for (uint32_t i = 0; i < lines.size(); ++i)
    {
        auto &l1 = lines[i];
        neigh.clear();
        for (uint32_t j = i + 1; j < lines.size(); ++j)
        {
            auto &l2 = lines[j];
            if (l1.HasCommonPoints(l2))
            {
                neigh.push_back(j);
            }
        }
        if (!neigh.empty())
        {
            std::sort(neigh.begin(), neigh.end(), [this, &i, &l1](const uint32_t &a, const uint32_t &b) {
                auto da = lines[a].center.squaredist(l1.center);
                auto db = lines[b].center.squaredist(l1.center);
                return da < db;
            });
            for (auto &n : neigh)
            {
                _neighbors[i].push_back(n);
                _neighbors[n].push_back(i);
            }
        }
    }

And now start the algo:

for (auto &kv : _neighbors) // point by point
    {
        if (_neighbors[kv.first].size() < 4) continue; // connected
        PolyCycle cycle;
        cycle.startIdx = kv.first;
        BuildCycle(kv.first, cycle);
    }

Usage

Very simple: pass the list of line segments in 2D, detect and process the detected polygons.

    std::vector<PolyLine> lines = {
        { { 0.481273, 19.263916 }, { 2.672669, -20.676010 } },
    ....
    };
    PolyDetector pd; // can be reused
    for (auto &l : lines)
        pd.AddLine(l);

    if (!pd.DetectPolygons()) // can be reused
    {
        logoutf("%s", "WARN: cannot detect polys!");
        return -1;
    }

    for (auto &poly : pd.polys) // here are the detected polys
    {
        for (auto &p : poly.p)
        {
            logoutf("[%u] p:{%f %f}", poly.id, p.x, p.y);
        }
    }

Results:

[100] p:{-5.966534 -16.157389} [100] p:{-5.985141 -16.163368} [100] p:{-6.596913 -14.281137} [104] p:{-5.753591 -16.088951} [104] p:{-5.921042 -16.142767} [104] p:{-7.055668 -11.525142} [106] p:{-4.095016 -15.555901} [106] p:{-5.739954 -16.136740} [106] p:{-5.753591 -16.088951} [110] p:{-1.943092 -14.864294} [110] p:{-1.957186 -14.801019} [110] p:{-4.095016 -15.555901} [112] p:{-6.583131 -15.457682} [112] p:{-7.130582 -13.257606} [112] p:{-8.761721 -8.122437} [114] p:{-1.003788 -14.845609} [114] p:{-1.850288 -15.280960} [114] p:{-1.884779 -15.126103} [116] p:{0.464259 -14.090594} [116] p:{-1.003788 -14.845609} [116] p:{-1.884779 -15.126103} [116] p:{-1.943092 -14.864294} [120] p:{0.464259 -14.090594} [120] p:{0.845067 -14.256959} [120] p:{0.995011 -13.920016} [120] p:{-1.003788 -14.845609} [124] p:{-6.596913 -14.281137} [124] p:{-7.672495 -11.079787} [124] p:{-7.787011 -10.619578} [126] p:{0.845067 -14.256959} [126] p:{0.995011 -13.920016} [126] p:{2.279338 -13.507246} [126] p:{2.295142 -13.795278} [128] p:{0.464259 -14.090594} [128] p:{0.995011 -13.920016} [128] p:{1.054096 -13.787243} [131] p:{0.995011 -13.920016} [131] p:{1.054096 -13.787243} [131] p:{1.361359 -13.629218} [131] p:{2.268456 -13.308915} [131] p:{2.279338 -13.507246} [133] p:{2.279338 -13.507246} [133] p:{2.295142 -13.795278} [133] p:{3.840607 -13.005469} [133] p:{3.898518 -13.284785} [135] p:{1.054096 -13.787243} [135] p:{1.080247 -13.728479} [135] p:{1.361359 -13.629218} [139] p:{1.361359 -13.629218} [139] p:{2.260654 -13.166713} [139] p:{2.268456 -13.308915} [141] p:{2.268456 -13.308915} [141] p:{2.279338 -13.507246} [141] p:{3.791984 -12.770947} [141] p:{3.840607 -13.005469} [143] p:{2.260654 -13.166713} [143] p:{2.268456 -13.308915} [143] p:{3.718580 -12.416905} [143] p:{3.791984 -12.770947} [145] p:{23.993586 -6.528498} [145] p:{24.577854 -6.700784} [145] p:{3.840607 -13.005469} [145] p:{3.898518 -13.284785} [147] p:{-7.130582 -13.257606} [147] p:{-7.672495 -11.079787} [147] p:{-8.761721 -8.122437} [147] p:{-9.490391 -5.669026} [149] p:{2.158531 -11.305436} [149] p:{2.260654 -13.166713} [149] p:{3.065557 -9.267232} [149] p:{3.718580 -12.416905} [14] p:{-3.623546 -24.298502} [14] p:{-3.812639 -24.723419} [14] p:{-4.919745 -20.217789} [151] p:{22.618740 -6.123089} [151] p:{23.993586 -6.528498} [151] p:{3.791984 -12.770947} [151] p:{3.840607 -13.005469} [153] p:{18.384180 -4.874419} [153] p:{22.618740 -6.123089} [153] p:{3.718580 -12.416905} [153] p:{3.791984 -12.770947} [155] p:{18.384180 -4.874419} [155] p:{3.065557 -9.267232} [155] p:{3.718580 -12.416905} [155] p:{6.570628 -1.390888} [157] p:{-7.055668 -11.525142} [157] p:{-8.794989 -4.446561} [157] p:{-9.039429 -4.572016} [159] p:{1.680041 -2.584581} [159] p:{2.158531 -11.305436} [159] p:{3.065557 -9.267232} [161] p:{-7.672495 -11.079787} [161] p:{-7.787011 -10.619578} [161] p:{-9.490391 -5.669026} [161] p:{-9.650656 -4.885727} [161] p:{-9.713459 -4.917960} [163] p:{-7.787011 -10.619578} [163] p:{-9.263258 -4.686897} [163] p:{-9.650656 -4.885727} [166] p:{1.623343 -1.551223} [166] p:{1.680041 -2.584581} [166] p:{3.065557 -9.267232} [166] p:{4.469060 -0.771186} [166] p:{6.570628 -1.390888} [170] p:{-8.761721 -8.122437} [170] p:{-9.490391 -5.669026} [170] p:{-9.738426 -4.930776} [170] p:{-9.770322 -4.947144} [178] p:{-9.490391 -5.669026} [178] p:{-9.713459 -4.917960} [178] p:{-9.738426 -4.930776} [183] p:{-9.770322 -4.947144} [183] p:{-9.850037 -4.696186} [183] p:{-9.917417 -5.022640} [183] p:{-9.975594 -4.730603} [185] p:{-9.738426 -4.930776} [185] p:{-9.770322 -4.947144} [185] p:{-9.820008 -4.687955} [185] p:{-9.850037 -4.696186} [187] p:{-9.713459 -4.917960} [187] p:{-9.738426 -4.930776} [187] p:{-9.784650 -4.678263} [187] p:{-9.820008 -4.687955} [189] p:{-9.650656 -4.885727} [189] p:{-9.713459 -4.917960} [189] p:{-9.723531 -4.661512} [189] p:{-9.784650 -4.678263} [191] p:{-9.263258 -4.686897} [191] p:{-9.298562 -4.545022} [191] p:{-9.650656 -4.885727} [191] p:{-9.723531 -4.661512} [194] p:{-10.205222 -3.577986} [194] p:{-9.850037 -4.696186} [194] p:{-9.975594 -4.730603} [196] p:{-10.205222 -3.577986} [196] p:{-10.223121 -3.488138} [196] p:{-9.820008 -4.687955} [196] p:{-9.850037 -4.696186} [198] p:{-10.223121 -3.488138} [198] p:{-10.396303 -2.618845} [198] p:{-9.784650 -4.678263} [198] p:{-9.820008 -4.687955} [19] p:{-3.460271 -23.931604} [19] p:{-3.494256 -24.007971} [19] p:{-3.916646 -22.527483} [200] p:{-9.039429 -4.572016} [200] p:{-9.065367 -4.481102} [200] p:{-9.263258 -4.686897} [200] p:{-9.298562 -4.545022} [202] p:{-10.396303 -2.618845} [202] p:{-10.410321 -2.548471} [202] p:{-9.723531 -4.661512} [202] p:{-9.784650 -4.678263} [204] p:{-10.410321 -2.548471} [204] p:{-10.446211 -2.368323} [204] p:{-9.298562 -4.545022} [204] p:{-9.723531 -4.661512} [204] p:{-9.893959 -2.152269} [206] p:{-8.794989 -4.446561} [206] p:{-8.804099 -4.409484} [206] p:{-9.039429 -4.572016} [206] p:{-9.065367 -4.481102} [208] p:{-9.065367 -4.481102} [208] p:{-9.298562 -4.545022} [208] p:{-9.746279 -2.094493} [208] p:{-9.893959 -2.152269} [210] p:{-8.804099 -4.409484} [210] p:{-9.065367 -4.481102} [210] p:{-9.405672 -1.961240} [210] p:{-9.746279 -2.094493} [212] p:{-8.629501 -4.361626} [212] p:{-8.794989 -4.446561} [212] p:{-8.804099 -4.409484} [216] p:{-4.532474 -3.238592} [216] p:{-4.728305 -2.359363} [216] p:{-8.629501 -4.361626} [219] p:{-10.205222 -3.577986} [219] p:{-10.223121 -3.488138} [219] p:{-10.418082 -2.907860} [227] p:{-15.334239 -1.867071} [227] p:{-17.146812 -2.402270} [227] p:{-20.989971 -2.829295} [227] p:{-22.073826 -3.120804} [229] p:{-10.418082 -2.907860} [229] p:{-10.573626 -2.418170} [229] p:{-10.581562 -2.421275} [22] p:{-3.400043 -23.796263} [22] p:{-3.460271 -23.931604} [22] p:{-3.916646 -22.527483} [22] p:{-4.425184 -20.745045} [232] p:{-14.743880 -1.692756} [232] p:{-15.334239 -1.867071} [232] p:{-18.325047 -2.112545} [232] p:{-20.989971 -2.829295} [236] p:{1.474267 -1.592087} [236] p:{1.623343 -1.551223} [236] p:{1.680041 -2.584581} [238] p:{-10.410321 -2.548471} [238] p:{-10.446211 -2.368323} [238] p:{-10.466318 -2.376189} [240] p:{-10.573626 -2.418170} [240] p:{-10.581562 -2.421275} [240] p:{-10.869467 -1.486810} [240] p:{-10.894306 -1.490433} [244] p:{-10.894306 -1.490433} [244] p:{-10.974771 -1.250936} [244] p:{-13.347639 -1.529087} [244] p:{-15.334239 -1.867071} [244] p:{-17.146812 -2.402270} [250] p:{-10.087907 -1.372831} [250] p:{-10.446211 -2.368323} [250] p:{-10.628818 -1.451715} [250] p:{-9.893959 -2.152269} [252] p:{-0.080468 0.026109} [252] p:{-2.194826 -0.221739} [252] p:{-4.728305 -2.359363} [252] p:{-5.109735 -0.646837} [255] p:{-16.738022 -1.685705} [255] p:{-18.102158 -1.849558} [255] p:{-18.325047 -2.112545} [255] p:{-20.006651 -2.309665} [257] p:{-10.490153 -2.302852} [257] p:{-10.738206 -1.467668} [257] p:{-10.760550 -1.470926} [259] p:{-10.087907 -1.372831} [259] p:{-9.746279 -2.094493} [259] p:{-9.893959 -2.152269} [259] p:{-9.957594 -1.353827} [261] p:{-13.336119 -1.277086} [261] p:{-14.743880 -1.692756} [261] p:{-16.738022 -1.685705} [261] p:{-18.325047 -2.112545} [263] p:{-9.405672 -1.961240} [263] p:{-9.568854 -1.297135} [263] p:{-9.746279 -2.094493} [263] p:{-9.957594 -1.353827} [266] p:{-6.602332 -0.864510} [266] p:{-9.405672 -1.961240} [266] p:{-9.568854 -1.297135} [268] p:{-13.347639 -1.529087} [268] p:{-14.743880 -1.692756} [268] p:{-15.334239 -1.867071} [26] p:{-3.916646 -22.527483} [26] p:{-4.425184 -20.745045} [26] p:{-5.611146 -17.215162} [26] p:{-5.638680 -17.229322} [278] p:{1.533043 0.094574} [278] p:{1.623343 -1.551223} [278] p:{4.469060 -0.771186} [280] p:{-10.974771 -1.250936} [280] p:{-11.014673 -1.132173} [280] p:{-13.347639 -1.529087} [282] p:{-10.869467 -1.486810} [282] p:{-10.894306 -1.490433} [282] p:{-10.945479 -1.247502} [282] p:{-10.974771 -1.250936} [284] p:{-10.760550 -1.470926} [284] p:{-10.837291 -1.234820} [284] p:{-10.869467 -1.486810} [284] p:{-10.945479 -1.247502} [286] p:{-10.738206 -1.467668} [286] p:{-10.760550 -1.470926} [286] p:{-10.808368 -1.231430} [286] p:{-10.837291 -1.234820} [288] p:{-10.628818 -1.451715} [288] p:{-10.675800 -1.215890} [288] p:{-10.738206 -1.467668} [288] p:{-10.808368 -1.231430} [290] p:{-10.087907 -1.372831} [290] p:{-10.142514 -1.153378} [290] p:{-10.628818 -1.451715} [290] p:{-10.675800 -1.215890} [292] p:{4.469060 -0.771186} [292] p:{6.570628 -1.390888} [292] p:{7.176688 -0.028999} [294] p:{-10.018917 -1.138890} [294] p:{-10.087907 -1.372831} [294] p:{-10.142514 -1.153378} [294] p:{-9.957594 -1.353827} [296] p:{-10.018917 -1.138890} [296] p:{-9.568854 -1.297135} [296] p:{-9.619247 -1.092040} [296] p:{-9.957594 -1.353827} [298] p:{-6.142051 -0.684438} [298] p:{-6.602332 -0.864510} [298] p:{-9.568854 -1.297135} [298] p:{-9.619247 -1.092040} [300] p:{-11.057925 -1.003441} [300] p:{-11.179892 -0.640415} [300] p:{-13.336119 -1.277086} [302] p:{-10.945479 -1.247502} [302] p:{-10.974771 -1.250936} [302] p:{-10.983782 -1.126917} [302] p:{-11.014673 -1.132173} [304] p:{-10.837291 -1.234820} [304] p:{-10.878201 -1.108955} [304] p:{-10.945479 -1.247502} [304] p:{-10.983782 -1.126917} [306] p:{-10.808368 -1.231430} [306] p:{-10.837291 -1.234820} [306] p:{-10.846354 -1.103537} [306] p:{-10.878201 -1.108955} [308] p:{-10.675800 -1.215890} [308] p:{-10.703040 -1.079154} [308] p:{-10.808368 -1.231430} [308] p:{-10.846354 -1.103537} [310] p:{-10.142514 -1.153378} [310] p:{-10.183002 -0.990679} [310] p:{-10.675800 -1.215890} [310] p:{-10.703040 -1.079154} [312] p:{-10.018917 -1.138890} [312] p:{-10.066840 -0.970916} [312] p:{-10.142514 -1.153378} [312] p:{-10.183002 -0.990679} [314] p:{-10.018917 -1.138890} [314] p:{-10.066840 -0.970916} [314] p:{-9.619247 -1.092040} [314] p:{-9.665776 -0.902682} [316] p:{-10.983782 -1.126917} [316] p:{-11.014673 -1.132173} [316] p:{-11.024285 -0.999400} [316] p:{-11.057925 -1.003441} [318] p:{-10.878201 -1.108955} [318] p:{-10.917961 -0.986629} [318] p:{-10.983782 -1.126917} [318] p:{-11.024285 -0.999400} [31] p:{-4.425184 -20.745045} [31] p:{-5.455165 -17.134941} [31] p:{-5.611146 -17.215162} [320] p:{-10.846354 -1.103537} [320] p:{-10.878201 -1.108955} [320] p:{-10.882347 -0.982351} [320] p:{-10.917961 -0.986629} [322] p:{-10.703040 -1.079154} [322] p:{-10.726068 -0.963580} [322] p:{-10.846354 -1.103537} [322] p:{-10.882347 -0.982351} [326] p:{-10.183002 -0.990679} [326] p:{-10.205308 -0.901029} [326] p:{-10.703040 -1.079154} [326] p:{-10.726068 -0.963580} [328] p:{-11.024285 -0.999400} [328] p:{-11.057925 -1.003441} [328] p:{-11.141879 -0.629192} [328] p:{-11.179892 -0.640415} [330] p:{-10.917961 -0.986629} [330] p:{-11.024285 -0.999400} [330] p:{-11.043571 -0.600162} [330] p:{-11.141879 -0.629192} [332] p:{-10.066840 -0.970916} [332] p:{-10.090707 -0.887264} [332] p:{-10.183002 -0.990679} [332] p:{-10.205308 -0.901029} [334] p:{-10.882347 -0.982351} [334] p:{-10.917961 -0.986629} [334] p:{-10.999704 -0.587211} [334] p:{-11.043571 -0.600162} [336] p:{-10.726068 -0.963580} [336] p:{-10.812082 -0.531814} [336] p:{-10.882347 -0.982351} [336] p:{-10.999704 -0.587211} [338] p:{-10.066840 -0.970916} [338] p:{-10.090707 -0.887264} [338] p:{-9.665776 -0.902682} [338] p:{-9.681639 -0.838129} [340] p:{-10.205308 -0.901029} [340] p:{-10.332423 -0.390181} [340] p:{-10.726068 -0.963580} [340] p:{-10.812082 -0.531814} [342] p:{-8.337063 -0.676625} [342] p:{-9.665776 -0.902682} [342] p:{-9.681639 -0.838129} [344] p:{-10.090707 -0.887264} [344] p:{-10.205308 -0.901029} [344] p:{-10.240288 -0.362978} [344] p:{-10.332423 -0.390181} [346] p:{-10.090707 -0.887264} [346] p:{-10.240288 -0.362978} [346] p:{-9.681639 -0.838129} [346] p:{-9.828282 -0.241326} [348] p:{-5.109735 -0.646837} [348] p:{-5.127840 -0.565551} [348] p:{-6.142051 -0.684438} [348] p:{-6.602332 -0.864510} [352] p:{1.526464 0.214475} [352] p:{1.533043 0.094574} [352] p:{4.469060 -0.771186} [352] p:{7.176688 -0.028999} [352] p:{7.601967 0.926654} [354] p:{-5.127840 -0.565551} [354] p:{-5.184774 -0.309929} [354] p:{-6.142051 -0.684438} [356] p:{-5.187364 -0.298299} [356] p:{-5.221174 -0.146511} [356] p:{-8.337063 -0.676625} [358] p:{-2.194826 -0.221739} [358] p:{-5.109735 -0.646837} [358] p:{-5.127840 -0.565551} [35] p:{-4.919745 -20.217789} [35] p:{-5.652333 -17.236343} [35] p:{-5.836662 -17.331144} [360] p:{-11.141879 -0.629192} [360] p:{-11.179892 -0.640415} [360] p:{-11.273158 -0.215897} [360] p:{-11.318431 -0.228069} [362] p:{-11.043571 -0.600162} [362] p:{-11.141879 -0.629192} [362] p:{-11.176883 -0.190000} [362] p:{-11.273158 -0.215897} [364] p:{-10.999704 -0.587211} [364] p:{-11.043571 -0.600162} [364] p:{-11.122056 -0.175255} [364] p:{-11.176883 -0.190000} [366] p:{-10.812082 -0.531814} [366] p:{-10.895268 -0.114257} [366] p:{-10.999704 -0.587211} [366] p:{-11.122056 -0.175255} [372] p:{-10.240288 -0.362978} [372] p:{-10.332423 -0.390181} [372] p:{-10.350459 0.023174} [372] p:{-10.430470 0.003846} [374] p:{-10.240288 -0.362978} [374] p:{-10.350459 0.023174} [374] p:{-9.828282 -0.241326} [374] p:{-9.918893 0.127437} [378] p:{-4.417622 -0.009801} [378] p:{-5.140727 -0.292697} [378] p:{-5.187364 -0.298299} [378] p:{-5.221174 -0.146511} [380] p:{-0.419664 0.670381} [380] p:{0.534594 0.388993} [380] p:{-4.417622 -0.009801} [380] p:{-5.140727 -0.292697} [382] p:{-5.485649 1.040924} [382] p:{-5.486086 1.042883} [382] p:{-7.542738 0.701493} [382] p:{-9.828282 -0.241326} [382] p:{-9.918893 0.127437} [386] p:{-0.080468 0.026109} [386] p:{0.084199 0.110624} [386] p:{-2.194826 -0.221739} [38] p:{0.845067 -14.256959} [38] p:{-1.003788 -14.845609} [38] p:{-1.103235 -18.635042} [38] p:{-1.850288 -15.280960} [390] p:{-11.277925 -0.200891} [390] p:{-11.323836 -0.211982} [390] p:{-11.363124 0.067332} [390] p:{-11.414798 0.058757} [392] p:{-11.180958 -0.177465} [392] p:{-11.265776 0.083493} [392] p:{-11.277925 -0.200891} [392] p:{-11.363124 0.067332} [396] p:{-11.125387 -0.164041} [396] p:{-11.180958 -0.177465} [396] p:{-11.202047 0.094074} [396] p:{-11.265776 0.083493} [400] p:{-10.896373 -0.108713} [400] p:{-10.945263 0.136696} [400] p:{-11.125387 -0.164041} [400] p:{-11.202047 0.094074} [40] p:{-11.983779 -18.341478} [40] p:{-7.545540 -16.928408} [40] p:{-7.574223 -16.784433} [412] p:{-0.419664 0.670381} [412] p:{-1.707977 1.050273} [412] p:{-4.417622 -0.009801} [416] p:{-10.352868 0.031620} [416] p:{-10.408278 0.225834} [416] p:{-10.432080 0.010316} [416] p:{-10.482636 0.213490} [418] p:{-10.350459 0.023174} [418] p:{-10.352868 0.031620} [418] p:{-9.918893 0.127437} [418] p:{-9.923712 0.147048} [422] p:{-10.352868 0.031620} [422] p:{-10.408278 0.225834} [422] p:{-9.923712 0.147048} [422] p:{-9.961301 0.300028} [42] p:{-6.085153 -17.458942} [42] p:{-6.314682 -16.536520} [42] p:{-7.313945 -18.090906} [42] p:{-7.545540 -16.928408} [432] p:{1.240220 0.180921} [432] p:{1.526464 0.214475} [432] p:{1.533043 0.094574} [434] p:{0.084199 0.110624} [434] p:{0.593009 0.371768} [434] p:{1.017191 0.246687} [436] p:{-7.542738 0.701493} [436] p:{-8.377337 0.562955} [436] p:{-9.918893 0.127437} [436] p:{-9.923712 0.147048} [440] p:{-8.377337 0.562955} [440] p:{-9.923712 0.147048} [440] p:{-9.961301 0.300028} [442] p:{1.097972 0.222867} [442] p:{1.109837 0.165637} [442] p:{1.240220 0.180921} [444] p:{1.090807 0.257423} [444] p:{1.097972 0.222867} [444] p:{1.240220 0.180921} [444] p:{1.520668 0.320111} [444] p:{1.526464 0.214475} [446] p:{-10.408278 0.225834} [446] p:{-10.482636 0.213490} [446] p:{-11.013975 2.348814} [448] p:{1.520668 0.320111} [448] p:{1.526464 0.214475} [448] p:{7.601967 0.926654} [448] p:{7.735373 1.226437} [44] p:{-6.001524 -17.415932} [44] p:{-6.085153 -17.458942} [44] p:{-6.267202 -16.521402} [44] p:{-6.314682 -16.536520} [450] p:{1.017191 0.246687} [450] p:{1.090807 0.257423} [450] p:{1.097972 0.222867} [454] p:{0.593009 0.371768} [454] p:{0.654676 0.403417} [454] p:{1.017191 0.246687} [454] p:{1.050677 0.450981} [454] p:{1.090807 0.257423} [456] p:{1.050677 0.450981} [456] p:{1.090807 0.257423} [456] p:{1.510458 0.506211} [456] p:{1.520668 0.320111} [460] p:{1.510458 0.506211} [460] p:{1.520668 0.320111} [460] p:{7.735373 1.226437} [460] p:{7.748293 1.255466} [462] p:{0.534594 0.388993} [462] p:{0.593009 0.371768} [462] p:{0.654676 0.403417} [466] p:{0.654676 0.403417} [466] p:{1.021504 0.591689} [466] p:{1.050677 0.450981} [468] p:{1.021504 0.591689} [468] p:{1.050677 0.450981} [468] p:{1.492504 0.833427} [468] p:{1.510458 0.506211} [46] p:{-5.836662 -17.331144} [46] p:{-6.001524 -17.415932} [46] p:{-6.109787 -16.471285} [46] p:{-6.267202 -16.521402} [470] p:{1.492504 0.833427} [470] p:{1.510458 0.506211} [470] p:{1.965458 1.076168} [470] p:{7.748293 1.255466} [470] p:{8.135650 2.125918} [474] p:{0.956641 0.904536} [474] p:{1.021504 0.591689} [474] p:{1.483683 0.994202} [474] p:{1.492504 0.833427} [476] p:{-0.419664 0.670381} [476] p:{0.728775 2.003585} [476] p:{0.956641 0.904536} [476] p:{-1.707977 1.050273} [478] p:{-5.486086 1.042883} [478] p:{-5.518944 1.190421} [478] p:{-7.542738 0.701493} [480] p:{1.483683 0.994202} [480] p:{1.492504 0.833427} [480] p:{1.965458 1.076168} [482] p:{0.728775 2.003585} [482] p:{0.956641 0.904536} [482] p:{1.043654 2.126774} [482] p:{1.418131 2.188938} [482] p:{1.483683 0.994202} [486] p:{1.418131 2.188938} [486] p:{1.483683 0.994202} [486] p:{1.965458 1.076168} [486] p:{5.431595 2.855140} [492] p:{-3.052717 1.446805} [492] p:{-3.582232 1.602946} [492] p:{-5.469936 1.045564} [494] p:{0.714560 2.072145} [494] p:{0.728775 2.003585} [494] p:{-1.707977 1.050273} [494] p:{-3.052717 1.446805} [496] p:{1.965458 1.076168} [496] p:{5.431595 2.855140} [496] p:{8.135650 2.125918} [496] p:{8.701728 3.397961} [498] p:{-3.685437 1.633378} [498] p:{-4.025065 1.733527} [498] p:{-5.518944 1.190421} [498] p:{-5.548642 1.323751} [4] p:{-4.110793 -25.393408} [4] p:{-5.318483 -28.107243} [4] p:{-6.085153 -17.458942} [4] p:{-7.313945 -18.090906} [500] p:{7.735373 1.226437} [500] p:{7.748293 1.255466} [500] p:{8.803667 1.382232} [504] p:{-4.025065 1.733527} [504] p:{-5.548642 1.323751} [504] p:{-5.753428 2.243179} [50] p:{-5.638680 -17.229322} [50] p:{-5.652333 -17.236343} [50] p:{-5.701707 -17.035408} [510] p:{-2.550820 1.907491} [510] p:{-3.582232 1.602946} [510] p:{-3.685437 1.633378} [516] p:{0.558359 2.825541} [516] p:{0.591312 2.666598} [516] p:{-2.550820 1.907491} [518] p:{0.714560 2.072145} [518] p:{0.728775 2.003585} [518] p:{1.043654 2.126774} [524] p:{1.043654 2.126774} [524] p:{1.413601 2.271505} [524] p:{1.418131 2.188938} [52] p:{-5.611146 -17.215162} [52] p:{-5.638680 -17.229322} [52] p:{-5.701707 -17.035408} [52] p:{-5.783833 -16.701180} [530] p:{1.381449 2.857487} [530] p:{1.413601 2.271505} [530] p:{5.381651 3.823897} [532] p:{-11.013975 2.348814} [532] p:{-11.402166 3.908856} [532] p:{-11.464286 3.927173} [534] p:{0.558359 2.825541} [534] p:{0.591312 2.666598} [534] p:{1.370052 3.065207} [534] p:{1.381449 2.857487} [536] p:{0.530723 2.958835} [536] p:{0.558359 2.825541} [536] p:{1.363598 3.182841} [536] p:{1.370052 3.065207} [544] p:{1.363598 3.182841} [544] p:{1.370052 3.065207} [544] p:{5.906488 4.404682} [54] p:{-5.455165 -17.134941} [54] p:{-5.611146 -17.215162} [54] p:{-5.683255 -16.335482} [54] p:{-5.783833 -16.701180} [54] p:{-5.859871 -16.391714} [554] p:{-11.402166 3.908856} [554] p:{-11.464286 3.927173} [554] p:{-12.246842 6.670040} [554] p:{-12.879696 9.846691} [556] p:{-11.464286 3.927173} [556] p:{-11.715145 4.001146} [556] p:{-12.246842 6.670040} [562] p:{-12.626447 4.269866} [562] p:{-12.705410 4.293151} [562] p:{-15.776628 13.961980} [568] p:{5.906488 4.404682} [568] p:{8.977301 5.230597} [568] p:{9.819422 5.560055} [56] p:{-1.850288 -15.280960} [56] p:{-1.884779 -15.126103} [56] p:{-5.455165 -17.134941} [56] p:{-5.683255 -16.335482} [58] p:{-5.701707 -17.035408} [58] p:{-5.783833 -16.701180} [58] p:{-5.885106 -16.399750} [58] p:{-5.906137 -16.406445} [60] p:{-6.314682 -16.536520} [60] p:{-6.359704 -16.355577} [60] p:{-7.545540 -16.928408} [60] p:{-7.574223 -16.784433} [62] p:{-6.359704 -16.355577} [62] p:{-6.376254 -16.289068} [62] p:{-7.574223 -16.784433} [62] p:{-7.594884 -16.680725} [64] p:{-5.783833 -16.701180} [64] p:{-5.859871 -16.391714} [64] p:{-5.885106 -16.399750} [68] p:{-6.267202 -16.521402} [68] p:{-6.314682 -16.536520} [68] p:{-6.320560 -16.341757} [68] p:{-6.359704 -16.355577} [70] p:{-6.109787 -16.471285} [70] p:{-6.168038 -16.287899} [70] p:{-6.267202 -16.521402} [70] p:{-6.320560 -16.341757} [72] p:{-5.906137 -16.406445} [72] p:{-5.967664 -16.217146} [72] p:{-6.109787 -16.471285} [72] p:{-6.168038 -16.287899} [74] p:{-5.885106 -16.399750} [74] p:{-5.906137 -16.406445} [74] p:{-5.948709 -16.210453} [74] p:{-5.967664 -16.217146} [76] p:{-5.859871 -16.391714} [76] p:{-5.885106 -16.399750} [76] p:{-5.907947 -16.196060} [76] p:{-5.948709 -16.210453} [78] p:{-5.683255 -16.335482} [78] p:{-5.739954 -16.136740} [78] p:{-5.859871 -16.391714} [78] p:{-5.907947 -16.196060} [80] p:{-6.320560 -16.341757} [80] p:{-6.339695 -16.277319} [80] p:{-6.359704 -16.355577} [80] p:{-6.376254 -16.289068} [82] p:{-6.168038 -16.287899} [82] p:{-6.186986 -16.228239} [82] p:{-6.320560 -16.341757} [82] p:{-6.339695 -16.277319} [86] p:{-6.339695 -16.277319} [86] p:{-6.376254 -16.289068} [86] p:{-6.583131 -15.457682} [88] p:{-5.967664 -16.217146} [88] p:{-5.985141 -16.163368} [88] p:{-6.168038 -16.287899} [88] p:{-6.186986 -16.228239} [8] p:{-3.823758 -24.748405} [8] p:{-4.110793 -25.393408} [8] p:{-6.001524 -17.415932} [8] p:{-6.085153 -17.458942} [90] p:{-6.186986 -16.228239} [90] p:{-6.339695 -16.277319} [90] p:{-6.583131 -15.457682} [90] p:{-7.130582 -13.257606} [96] p:{-5.907947 -16.196060} [96] p:{-5.921042 -16.142767} [96] p:{-5.948709 -16.210453} [96] p:{-5.966534 -16.157389} [98] p:{-5.739954 -16.136740} [98] p:{-5.753591 -16.088951} [98] p:{-5.907947 -16.196060} [98] p:{-5.921042 -16.142767}