<commit_before>/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2005-2006 Refractions Research Inc.
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation.
 * See the COPYING file for more information.
 *
 **********************************************************************
 *
 * Last port: operation/polygonize/EdgeRing.java rev. 974
 *
 **********************************************************************/

#include <geos/operation/polygonize/EdgeRing.h>
#include <geos/operation/polygonize/PolygonizeEdge.h>
#include <geos/planargraph/DirectedEdge.h>
#include <geos/geom/CoordinateSequence.h>
#include <geos/geom/LinearRing.h>
#include <geos/geom/Coordinate.h>
#include <geos/geom/Envelope.h>
#include <geos/geom/GeometryFactory.h>
#include <geos/geom/CoordinateSequenceFactory.h>
#include <geos/algorithm/PointLocation.h>
#include <geos/algorithm/Orientation.h>
#include <geos/util/IllegalArgumentException.h>
#include <geos/util.h> // TODO: drop this, includes too much

#include <vector>
#include <cassert>

//#define DEBUG_ALLOC 1
//#define GEOS_PARANOIA_LEVEL 2

using namespace std;
using namespace geos::planargraph;
using namespace geos::algorithm;
using namespace geos::geom;

namespace geos {
namespace operation { // geos.operation
namespace polygonize { // geos.operation.polygonize

/*public*/
EdgeRing*
EdgeRing::findEdgeRingContaining(EdgeRing* testEr,
                                 vector<EdgeRing*>* shellList)
{
    const LinearRing* testRing = testEr->getRingInternal();
    if(! testRing) {
        return nullptr;
    }
    const Envelope* testEnv = testRing->getEnvelopeInternal();
    EdgeRing* minShell = nullptr;
    const Envelope* minEnv = nullptr;

    for(EdgeRing* tryShell : *shellList) {
        LinearRing* tryRing = tryShell->getRingInternal();
        const Envelope* tryEnv = tryRing->getEnvelopeInternal();
        if(minShell != nullptr) {
            minEnv = minShell->getRingInternal()->getEnvelopeInternal();
        }
        bool isContained = false;

        // the hole envelope cannot equal the shell envelope

        if(tryEnv->equals(testEnv)) {
            continue;
        }

        const CoordinateSequence* tryCoords =
            tryRing->getCoordinatesRO();

        if(tryEnv->contains(testEnv)) {
            // TODO: don't copy testPt !
            Coordinate testPt = ptNotInList(testRing->getCoordinatesRO(), tryCoords);

            if(PointLocation::isInRing(testPt, tryCoords)) {
                isContained = true;
            }

        }

        // check if this new containing ring is smaller
        // than the current minimum ring
        if(isContained) {
            if(minShell == nullptr || minEnv->contains(tryEnv)) {
                minShell = tryShell;
            }
        }
    }
    return minShell;
}

std::vector<PolygonizeDirectedEdge*>
EdgeRing::findDirEdgesInRing(PolygonizeDirectedEdge* startDE) {
    auto de = startDE;
    std::vector<decltype(de)> edges;

    do {
        edges.push_back(de);
        de = de->getNext();
    } while (de != startDE);

    return edges;
}

/*public static*/
const Coordinate&
EdgeRing::ptNotInList(const CoordinateSequence* testPts,
                      const CoordinateSequence* pts)<commit_msg>Improve Polygonizer performance for cases with many potential holes<commit_after>/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2005-2006 Refractions Research Inc.
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation.
 * See the COPYING file for more information.
 *
 **********************************************************************
 *
 * Last port: operation/polygonize/EdgeRing.java rev. 974
 *
 **********************************************************************/

#include <geos/operation/polygonize/EdgeRing.h>
#include <geos/operation/polygonize/PolygonizeEdge.h>
#include <geos/planargraph/DirectedEdge.h>
#include <geos/geom/CoordinateSequence.h>
#include <geos/geom/LinearRing.h>
#include <geos/geom/Coordinate.h>
#include <geos/geom/Envelope.h>
#include <geos/geom/GeometryFactory.h>
#include <geos/geom/CoordinateSequenceFactory.h>
#include <geos/algorithm/PointLocation.h>
#include <geos/algorithm/Orientation.h>
#include <geos/util/IllegalArgumentException.h>
#include <geos/util.h> // TODO: drop this, includes too much

#include <vector>
#include <cassert>

//#define DEBUG_ALLOC 1
//#define GEOS_PARANOIA_LEVEL 2

using namespace std;
using namespace geos::planargraph;
using namespace geos::algorithm;
using namespace geos::geom;

namespace geos {
namespace operation { // geos.operation
namespace polygonize { // geos.operation.polygonize

/*public*/
EdgeRing*
EdgeRing::findEdgeRingContaining(EdgeRing* testEr,
                                 vector<EdgeRing*>* shellList)
{
    const LinearRing* testRing = testEr->getRingInternal();
    if(! testRing) {
        return nullptr;
    }
    const Envelope* testEnv = testRing->getEnvelopeInternal();
    EdgeRing* minShell = nullptr;
    const Envelope* minShellEnv = nullptr;

    for(EdgeRing* tryShell : *shellList) {
        auto tryShellRing = tryShell->getRingInternal();
        auto tryShellEnv = tryShellRing->getEnvelopeInternal();
        // the hole envelope cannot equal the shell envelope
        // (also guards against testing rings against themselves)
        if (tryShellEnv->equals(testEnv)) {
            continue;
        }
        // hole must be contained in shell
        if (!tryShellEnv->contains(testEnv)) {
            continue;
        }

        auto tryCoords = tryShellRing->getCoordinatesRO();
        Coordinate testPt = ptNotInList(testRing->getCoordinatesRO(), tryCoords); // TODO: don't copy testPt !

        bool isContained = PointLocation::isInRing(testPt, tryCoords);

        // check if this new containing ring is smaller than the current minimum ring
        if(isContained) {
            if(minShell == nullptr || minShellEnv->contains(tryShellEnv)) {
                minShell = tryShell;
                minShellEnv = minShell->getRingInternal()->getEnvelopeInternal();
            }
        }
    }
    return minShell;
}

std::vector<PolygonizeDirectedEdge*>
EdgeRing::findDirEdgesInRing(PolygonizeDirectedEdge* startDE) {
    auto de = startDE;
    std::vector<decltype(de)> edges;

    do {
        edges.push_back(de);
        de = de->getNext();
    } while (de != startDE);

    return edges;
}

/*public static*/
const Coordinate&
EdgeRing::ptNotInList(const CoordinateSequence* testPts,
                      const CoordinateSequence* pts)
{'fraction_non_alphanumeric': 0.161431805319751, 'fraction_numerical': 0.005942275042444821, 'mean_word_length': 3.377089783281734, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 63, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5276994', 'n_tokens_mistral': 2127, 'n_tokens_neox': 1980, 'n_words': 492}