/src/gdal/alg/marching_squares/segment_merger.h

Source (jump to first uncovered line)
/******************************************************************************
 *
 * Project:  Marching square algorithm
 * Purpose:  Core algorithm implementation for contour line generation.
 * Author:   Oslandia <infos at oslandia dot com>
 *
 ******************************************************************************
 * Copyright (c) 2018, Oslandia <infos at oslandia dot com>
 *
 * SPDX-License-Identifier: MIT
 ****************************************************************************/
#ifndef MARCHING_SQUARES_SEGMENT_MERGER_H
#define MARCHING_SQUARES_SEGMENT_MERGER_H

#include "cpl_error.h"
#include "point.h"

#include <list>
#include <map>

#include <iostream>

namespace marching_squares
{

// SegmentMerger: join segments into linestrings and possibly into rings of
// polygons
template <typename LineWriter, typename LevelGenerator> struct SegmentMerger
{
    struct LineStringEx
    {
        LineString ls = LineString();
        bool isMerged = false;
    };

    // a collection of unmerged linestrings
    typedef std::list<LineStringEx> Lines;

    SegmentMerger(LineWriter &lineWriter, const LevelGenerator &levelGenerator,
                  bool polygonize_)
        : polygonize(polygonize_), lineWriter_(lineWriter), lines_(),
          levelGenerator_(levelGenerator), m_anSkipLevels()
    {
    }

    ~SegmentMerger()
    {
        if (polygonize)
        {
            for (auto it = lines_.begin(); it != lines_.end(); ++it)
            {
                if (!it->second.empty())
                    debug("remaining unclosed contour");
            }
        }
        // write all remaining (non-closed) lines
        for (auto it = lines_.begin(); it != lines_.end(); ++it)
        {
            const int levelIdx = it->first;

            // Skip levels that should be skipped
            if (std::find(m_anSkipLevels.begin(), m_anSkipLevels.end(),
                          levelIdx) != m_anSkipLevels.end())
            {
                continue;
            }
            while (it->second.begin() != it->second.end())
            {
                lineWriter_.addLine(levelGenerator_.level(levelIdx),
                                    it->second.begin()->ls, /* closed */ false);
                it->second.pop_front();
            }
        }
    }

    void addSegment(int levelIdx, const Point &start, const Point &end)
    {
        addSegment_(levelIdx, start, end);
    }

    void addBorderSegment(int levelIdx, const Point &start, const Point &end)
    {
        addSegment_(levelIdx, start, end);
    }

    void beginningOfLine()
    {
        if (polygonize)
            return;

        // mark lines as non merged
        for (auto &l : lines_)
        {
            for (auto &ls : l.second)
            {
                ls.isMerged = false;
            }
        }
    }

    void endOfLine()
    {
        if (polygonize)
            return;

        // At the end of the line, we know that if no segment has been merged to
        // an existing line, it means there won't be anything more in the
        // future, we can then emit the line (this both speeds up and saves
        // memory)

        for (auto &l : lines_)
        {
            const int levelIdx = l.first;
            auto it = l.second.begin();
            while (it != l.second.end())
            {
                if (!it->isMerged)
                {
                    // Note that emitLine_ erases `it` and returns an iterator
                    // advanced to the next element.
                    it = emitLine_(levelIdx, it, /* closed */ false);
                }
                else
                {
                    ++it;
                }
            }
        }
    }

    // non copyable
    SegmentMerger(const SegmentMerger<LineWriter, LevelGenerator> &) = delete;
    SegmentMerger<LineWriter, LevelGenerator> &
    operator=(const SegmentMerger<LineWriter, LevelGenerator> &) = delete;

    /**
     * @brief setSkipLevels sets the levels that should be skipped
     *        when polygonize option is set.
     * @param anSkipLevels integer 0-based levels to skip.
     */
    void setSkipLevels(const std::vector<int> &anSkipLevels)
    {
        // Warn if polygonize is not set
        if (!polygonize)
        {
            CPLError(
                CE_Warning, CPLE_NotSupported,
                "setSkipLevels is ignored when polygonize option is not set");
        }
        m_anSkipLevels = anSkipLevels;
    }

    const bool polygonize;

  private:
    LineWriter &lineWriter_;
    // lines of each level
    std::map<int, Lines> lines_;
    const LevelGenerator &levelGenerator_;

    // Store 0-indexed levels to skip when polygonize option is set
    std::vector<int> m_anSkipLevels;

    void addSegment_(int levelIdx, const Point &start, const Point &end)
    {

        Lines &lines = lines_[levelIdx];

        if (start == end)
        {
            debug("degenerate segment (%f %f)", start.x, start.y);
            return;
        }
        // attempt to merge segment with existing line
        auto it = lines.begin();
        for (; it != lines.end(); ++it)
        {
            if (it->ls.back() == end)
            {
                it->ls.push_back(start);
                it->isMerged = true;
                break;
            }
            if (it->ls.front() == end)
            {
                it->ls.push_front(start);
                it->isMerged = true;
                break;
            }
            if (it->ls.back() == start)
            {
                it->ls.push_back(end);
                it->isMerged = true;
                break;
            }
            if (it->ls.front() == start)
            {
                it->ls.push_front(end);
                it->isMerged = true;
                break;
            }
        }

        if (it == lines.end())
        {
            // new line
            lines.push_back(LineStringEx());
            lines.back().ls.push_back(start);
            lines.back().ls.push_back(end);
            lines.back().isMerged = true;
        }
        else if (polygonize && (it->ls.front() == it->ls.back()))
        {
            // ring closed
            emitLine_(levelIdx, it, /* closed */ true);
            return;
        }
        else
        {
            // try to perform linemerge with another line
            // since we got out of the previous loop on the first match
            // there is no need to test previous elements
            // also: a segment merges at most two lines, no need to stall here
            // ;)
            auto other = it;
            ++other;
            for (; other != lines.end(); ++other)
            {
                if (it->ls.back() == other->ls.front())
                {
                    it->ls.pop_back();
                    it->ls.splice(it->ls.end(), other->ls);
                    it->isMerged = true;
                    lines.erase(other);
                    // if that makes a closed ring, returns it
                    if (it->ls.front() == it->ls.back())
                        emitLine_(levelIdx, it, /* closed */ true);
                    break;
                }
                else if (other->ls.back() == it->ls.front())
                {
                    it->ls.pop_front();
                    other->ls.splice(other->ls.end(), it->ls);
                    other->isMerged = true;
                    lines.erase(it);
                    // if that makes a closed ring, returns it
                    if (other->ls.front() == other->ls.back())
                        emitLine_(levelIdx, other, /* closed */ true);
                    break;
                }
                // two lists must be merged but one is in the opposite direction
                else if (it->ls.back() == other->ls.back())
                {
                    it->ls.pop_back();
                    for (auto rit = other->ls.rbegin(); rit != other->ls.rend();
                         ++rit)
                    {
                        it->ls.push_back(*rit);
                    }
                    it->isMerged = true;
                    lines.erase(other);
                    // if that makes a closed ring, returns it
                    if (it->ls.front() == it->ls.back())
                        emitLine_(levelIdx, it, /* closed */ true);
                    break;
                }
                else if (it->ls.front() == other->ls.front())
                {
                    it->ls.pop_front();
                    for (auto rit = other->ls.begin(); rit != other->ls.end();
                         ++rit)
                    {
                        it->ls.push_front(*rit);
                    }
                    it->isMerged = true;
                    lines.erase(other);
                    // if that makes a closed ring, returns it
                    if (it->ls.front() == it->ls.back())
                        emitLine_(levelIdx, it, /* closed */ true);
                    break;
                }
            }
        }
    }

    typename Lines::iterator emitLine_(int levelIdx,
                                       typename Lines::iterator it, bool closed)
    {

        Lines &lines = lines_[levelIdx];
        if (lines.empty())
            lines_.erase(levelIdx);

        // consume "it" and remove it from the list
        // but clear the line if the level should be skipped
        if (std::find(m_anSkipLevels.begin(), m_anSkipLevels.end(), levelIdx) !=
            m_anSkipLevels.end())
        {
            it->ls.clear();
        }
        lineWriter_.addLine(levelGenerator_.level(levelIdx), it->ls, closed);
        return lines.erase(it);
    }
};

}  // namespace marching_squares
#endif

Coverage Report

Created: 2025-06-13 06:29

Line	Count	Source (jump to first uncovered line)
1		/******************************************************************************
2		*
3		* Project: Marching square algorithm
4		* Purpose: Core algorithm implementation for contour line generation.
5		* Author: Oslandia <infos at oslandia dot com>
6		*
7		******************************************************************************
8		* Copyright (c) 2018, Oslandia <infos at oslandia dot com>
9		*
10		* SPDX-License-Identifier: MIT
11		****************************************************************************/
12		#ifndef MARCHING_SQUARES_SEGMENT_MERGER_H
13		#define MARCHING_SQUARES_SEGMENT_MERGER_H
14
15		#include "cpl_error.h"
16		#include "point.h"
17
18		#include <list>
19		#include <map>
20
21		#include <iostream>
22
23		namespace marching_squares
24		{
25
26		// SegmentMerger: join segments into linestrings and possibly into rings of
27		// polygons
28		template <typename LineWriter, typename LevelGenerator> struct SegmentMerger
29		{
30		struct LineStringEx
31		{
32		LineString ls = LineString();
33		bool isMerged = false;
34		};
35
36		// a collection of unmerged linestrings
37		typedef std::list<LineStringEx> Lines;
38
39		SegmentMerger(LineWriter &lineWriter, const LevelGenerator &levelGenerator,
40		bool polygonize_)
41	0	: polygonize(polygonize_), lineWriter_(lineWriter), lines_(),
42	0	levelGenerator_(levelGenerator), m_anSkipLevels()
43	0	{
44	0	} Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::IntervalLevelRangeIterator>::SegmentMerger(GDALRingAppender&, marching_squares::IntervalLevelRangeIterator const&, bool) Unexecuted instantiation: marching_squares::SegmentMerger<marching_squares::PolygonRingAppender<PolygonContourWriter>, marching_squares::FixedLevelRangeIterator>::SegmentMerger(marching_squares::PolygonRingAppender<PolygonContourWriter>&, marching_squares::FixedLevelRangeIterator const&, bool) Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::FixedLevelRangeIterator>::SegmentMerger(GDALRingAppender&, marching_squares::FixedLevelRangeIterator const&, bool)
45
46		~SegmentMerger()
47	0	{
48	0	if (polygonize)
49	0	{
50	0	for (auto it = lines_.begin(); it != lines_.end(); ++it)
51	0	{
52	0	if (!it->second.empty())
53	0	debug("remaining unclosed contour");
54	0	}
55	0	}
56		// write all remaining (non-closed) lines
57	0	for (auto it = lines_.begin(); it != lines_.end(); ++it)
58	0	{
59	0	const int levelIdx = it->first;
60
61		// Skip levels that should be skipped
62	0	if (std::find(m_anSkipLevels.begin(), m_anSkipLevels.end(),
63	0	levelIdx) != m_anSkipLevels.end())
64	0	{
65	0	continue;
66	0	}
67	0	while (it->second.begin() != it->second.end())
68	0	{
69	0	lineWriter_.addLine(levelGenerator_.level(levelIdx),
70	0	it->second.begin()->ls, /* closed */ false);
71	0	it->second.pop_front();
72	0	}
73	0	}
74	0	} Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::IntervalLevelRangeIterator>::~SegmentMerger() Unexecuted instantiation: marching_squares::SegmentMerger<marching_squares::PolygonRingAppender<PolygonContourWriter>, marching_squares::FixedLevelRangeIterator>::~SegmentMerger() Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::FixedLevelRangeIterator>::~SegmentMerger()
75
76		void addSegment(int levelIdx, const Point &start, const Point &end)
77	0	{
78	0	addSegment_(levelIdx, start, end);
79	0	} Unexecuted instantiation: marching_squares::SegmentMerger<marching_squares::PolygonRingAppender<PolygonContourWriter>, marching_squares::FixedLevelRangeIterator>::addSegment(int, marching_squares::Point const&, marching_squares::Point const&) Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::FixedLevelRangeIterator>::addSegment(int, marching_squares::Point const&, marching_squares::Point const&) Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::IntervalLevelRangeIterator>::addSegment(int, marching_squares::Point const&, marching_squares::Point const&)
80
81		void addBorderSegment(int levelIdx, const Point &start, const Point &end)
82	0	{
83	0	addSegment_(levelIdx, start, end);
84	0	} Unexecuted instantiation: marching_squares::SegmentMerger<marching_squares::PolygonRingAppender<PolygonContourWriter>, marching_squares::FixedLevelRangeIterator>::addBorderSegment(int, marching_squares::Point const&, marching_squares::Point const&) Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::FixedLevelRangeIterator>::addBorderSegment(int, marching_squares::Point const&, marching_squares::Point const&) Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::IntervalLevelRangeIterator>::addBorderSegment(int, marching_squares::Point const&, marching_squares::Point const&)
85
86		void beginningOfLine()
87	0	{
88	0	if (polygonize)
89	0	return;
90
91		// mark lines as non merged
92	0	for (auto &l : lines_)
93	0	{
94	0	for (auto &ls : l.second)
95	0	{
96	0	ls.isMerged = false;
97	0	}
98	0	}
99	0	} Unexecuted instantiation: marching_squares::SegmentMerger<marching_squares::PolygonRingAppender<PolygonContourWriter>, marching_squares::FixedLevelRangeIterator>::beginningOfLine() Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::FixedLevelRangeIterator>::beginningOfLine() Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::IntervalLevelRangeIterator>::beginningOfLine()
100
101		void endOfLine()
102	0	{
103	0	if (polygonize)
104	0	return;
105
106		// At the end of the line, we know that if no segment has been merged to
107		// an existing line, it means there won't be anything more in the
108		// future, we can then emit the line (this both speeds up and saves
109		// memory)
110
111	0	for (auto &l : lines_)
112	0	{
113	0	const int levelIdx = l.first;
114	0	auto it = l.second.begin();
115	0	while (it != l.second.end())
116	0	{
117	0	if (!it->isMerged)
118	0	{
119		// Note that emitLine_ erases `it` and returns an iterator
120		// advanced to the next element.
121	0	it = emitLine_(levelIdx, it, /* closed */ false);
122	0	}
123	0	else
124	0	{
125	0	++it;
126	0	}
127	0	}
128	0	}
129	0	} Unexecuted instantiation: marching_squares::SegmentMerger<marching_squares::PolygonRingAppender<PolygonContourWriter>, marching_squares::FixedLevelRangeIterator>::endOfLine() Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::FixedLevelRangeIterator>::endOfLine() Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::IntervalLevelRangeIterator>::endOfLine()
130
131		// non copyable
132		SegmentMerger(const SegmentMerger<LineWriter, LevelGenerator> &) = delete;
133		SegmentMerger<LineWriter, LevelGenerator> &
134		operator=(const SegmentMerger<LineWriter, LevelGenerator> &) = delete;
135
136		/**
137		* @brief setSkipLevels sets the levels that should be skipped
138		* when polygonize option is set.
139		* @param anSkipLevels integer 0-based levels to skip.
140		*/
141		void setSkipLevels(const std::vector<int> &anSkipLevels)
142	0	{
143		// Warn if polygonize is not set
144	0	if (!polygonize)
145	0	{
146	0	CPLError(
147	0	CE_Warning, CPLE_NotSupported,
148	0	"setSkipLevels is ignored when polygonize option is not set");
149	0	}
150	0	m_anSkipLevels = anSkipLevels;
151	0	}
152
153		const bool polygonize;
154
155		private:
156		LineWriter &lineWriter_;
157		// lines of each level
158		std::map<int, Lines> lines_;
159		const LevelGenerator &levelGenerator_;
160
161		// Store 0-indexed levels to skip when polygonize option is set
162		std::vector<int> m_anSkipLevels;
163
164		void addSegment_(int levelIdx, const Point &start, const Point &end)
165	0	{
166
167	0	Lines &lines = lines_[levelIdx];
168
169	0	if (start == end)
170	0	{
171	0	debug("degenerate segment (%f %f)", start.x, start.y);
172	0	return;
173	0	}
174		// attempt to merge segment with existing line
175	0	auto it = lines.begin();
176	0	for (; it != lines.end(); ++it)
177	0	{
178	0	if (it->ls.back() == end)
179	0	{
180	0	it->ls.push_back(start);
181	0	it->isMerged = true;
182	0	break;
183	0	}
184	0	if (it->ls.front() == end)
185	0	{
186	0	it->ls.push_front(start);
187	0	it->isMerged = true;
188	0	break;
189	0	}
190	0	if (it->ls.back() == start)
191	0	{
192	0	it->ls.push_back(end);
193	0	it->isMerged = true;
194	0	break;
195	0	}
196	0	if (it->ls.front() == start)
197	0	{
198	0	it->ls.push_front(end);
199	0	it->isMerged = true;
200	0	break;
201	0	}
202	0	}
203
204	0	if (it == lines.end())
205	0	{
206		// new line
207	0	lines.push_back(LineStringEx());
208	0	lines.back().ls.push_back(start);
209	0	lines.back().ls.push_back(end);
210	0	lines.back().isMerged = true;
211	0	}
212	0	else if (polygonize && (it->ls.front() == it->ls.back()))
213	0	{
214		// ring closed
215	0	emitLine_(levelIdx, it, /* closed */ true);
216	0	return;
217	0	}
218	0	else
219	0	{
220		// try to perform linemerge with another line
221		// since we got out of the previous loop on the first match
222		// there is no need to test previous elements
223		// also: a segment merges at most two lines, no need to stall here
224		// ;)
225	0	auto other = it;
226	0	++other;
227	0	for (; other != lines.end(); ++other)
228	0	{
229	0	if (it->ls.back() == other->ls.front())
230	0	{
231	0	it->ls.pop_back();
232	0	it->ls.splice(it->ls.end(), other->ls);
233	0	it->isMerged = true;
234	0	lines.erase(other);
235		// if that makes a closed ring, returns it
236	0	if (it->ls.front() == it->ls.back())
237	0	emitLine_(levelIdx, it, /* closed */ true);
238	0	break;
239	0	}
240	0	else if (other->ls.back() == it->ls.front())
241	0	{
242	0	it->ls.pop_front();
243	0	other->ls.splice(other->ls.end(), it->ls);
244	0	other->isMerged = true;
245	0	lines.erase(it);
246		// if that makes a closed ring, returns it
247	0	if (other->ls.front() == other->ls.back())
248	0	emitLine_(levelIdx, other, /* closed */ true);
249	0	break;
250	0	}
251		// two lists must be merged but one is in the opposite direction
252	0	else if (it->ls.back() == other->ls.back())
253	0	{
254	0	it->ls.pop_back();
255	0	for (auto rit = other->ls.rbegin(); rit != other->ls.rend();
256	0	++rit)
257	0	{
258	0	it->ls.push_back(*rit);
259	0	}
260	0	it->isMerged = true;
261	0	lines.erase(other);
262		// if that makes a closed ring, returns it
263	0	if (it->ls.front() == it->ls.back())
264	0	emitLine_(levelIdx, it, /* closed */ true);
265	0	break;
266	0	}
267	0	else if (it->ls.front() == other->ls.front())
268	0	{
269	0	it->ls.pop_front();
270	0	for (auto rit = other->ls.begin(); rit != other->ls.end();
271	0	++rit)
272	0	{
273	0	it->ls.push_front(*rit);
274	0	}
275	0	it->isMerged = true;
276	0	lines.erase(other);
277		// if that makes a closed ring, returns it
278	0	if (it->ls.front() == it->ls.back())
279	0	emitLine_(levelIdx, it, /* closed */ true);
280	0	break;
281	0	}
282	0	}
283	0	}
284	0	} Unexecuted instantiation: marching_squares::SegmentMerger<marching_squares::PolygonRingAppender<PolygonContourWriter>, marching_squares::FixedLevelRangeIterator>::addSegment_(int, marching_squares::Point const&, marching_squares::Point const&) Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::FixedLevelRangeIterator>::addSegment_(int, marching_squares::Point const&, marching_squares::Point const&) Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::IntervalLevelRangeIterator>::addSegment_(int, marching_squares::Point const&, marching_squares::Point const&)
285
286		typename Lines::iterator emitLine_(int levelIdx,
287		typename Lines::iterator it, bool closed)
288	0	{
289
290	0	Lines &lines = lines_[levelIdx];
291	0	if (lines.empty())
292	0	lines_.erase(levelIdx);
293
294		// consume "it" and remove it from the list
295		// but clear the line if the level should be skipped
296	0	if (std::find(m_anSkipLevels.begin(), m_anSkipLevels.end(), levelIdx) !=
297	0	m_anSkipLevels.end())
298	0	{
299	0	it->ls.clear();
300	0	}
301	0	lineWriter_.addLine(levelGenerator_.level(levelIdx), it->ls, closed);
302	0	return lines.erase(it);
303	0	} Unexecuted instantiation: marching_squares::SegmentMerger<marching_squares::PolygonRingAppender<PolygonContourWriter>, marching_squares::FixedLevelRangeIterator>::emitLine_(int, std::__1::__list_iterator<marching_squares::SegmentMerger<marching_squares::PolygonRingAppender<PolygonContourWriter>, marching_squares::FixedLevelRangeIterator>::LineStringEx, void>, bool) Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::FixedLevelRangeIterator>::emitLine_(int, std::__1::__list_iterator<marching_squares::SegmentMerger<GDALRingAppender, marching_squares::FixedLevelRangeIterator>::LineStringEx, void>, bool) Unexecuted instantiation: marching_squares::SegmentMerger<GDALRingAppender, marching_squares::IntervalLevelRangeIterator>::emitLine_(int, std::__1::__list_iterator<marching_squares::SegmentMerger<GDALRingAppender, marching_squares::IntervalLevelRangeIterator>::LineStringEx, void*>, bool)
304		};
305
306		} // namespace marching_squares
307		#endif