tilemaker/src/tile_sorting.cpp at master · cyclemap/tilemaker · GitHub

History

152 lines (135 loc) · 4.87 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

#include <string>

#include <vector>

#include <iostream>

#include "tile_data_base.h"

#include "append_vector.h"

#include <boost/sort/sort.hpp>

template<typename OO> void sortOutputObjects(

const unsigned int indexZoom,

const size_t threadNum,

typename AppendVectorNS::AppendVector<OO>::Iterator begin,

typename AppendVectorNS::AppendVector<OO>::Iterator end

)

{

// If the user is doing a a small extract, there are few populated

// entries in `object`.

// e.g. Colorado has ~9 z6 tiles, 1 of which has 95% of its output

// objects.

// This optimizes for the small extract case by doing:

// - for each vector in objects

// - do a multi-threaded sort of vector

// For small extracts, this ensures that all threads are used even if

// only a handful of entries in `objects` are non-empty.

// For a global extract, this will have some overhead of repeatedly

// setting up/tearing down threads. In that case, it would be

// better to assign chunks of `objects` to each thread.

// That's a future performance improvement, so deferring for now.

boost::sort::block_indirect_sort(

begin, end,

[indexZoom](const OO& a, const OO& b) {

// Cluster by parent zoom, so that a subsequent search

// can find a contiguous range of entries for any tile

// at zoom 6 or higher.

const size_t aX = a.x;

const size_t aY = a.y;

const size_t bX = b.x;

const size_t bY = b.y;

for (size_t z = CLUSTER_ZOOM; z <= indexZoom; z++) {

const auto aXz = aX / (1 << (indexZoom - z));

const auto bXz = bX / (1 << (indexZoom - z));

if (aXz != bXz)

return aXz < bXz;

const auto aYz = aY / (1 << (indexZoom - z));

const auto bYz = bY / (1 << (indexZoom - z));

if (aYz != bYz)

return aYz < bYz;

}

return false;

threadNum

);

}

template void sortOutputObjects<OutputObjectXY>(

const unsigned int indexZoom,

const size_t threadNum,

typename AppendVectorNS::AppendVector<OutputObjectXY>::Iterator begin,

typename AppendVectorNS::AppendVector<OutputObjectXY>::Iterator end

);

template void sortOutputObjects<OutputObjectXYID>(

const unsigned int indexZoom,

const size_t threadNum,

typename AppendVectorNS::AppendVector<OutputObjectXYID>::Iterator begin,

typename AppendVectorNS::AppendVector<OutputObjectXYID>::Iterator end

);

void sortOutputObjectIDs(

const std::vector<bool>& sortOrders,

std::vector<OutputObjectID>& data

) {

// Lexicographic comparison, with the order of: layer, geomType, attributes, and objectID.

// Note that attributes is preferred to objectID.

// It is to arrange objects with the identical attributes continuously.

// Such objects will be merged into one object, to reduce the size of output.

boost::sort::pdqsort(data.begin(), data.end(), [&sortOrders](const OutputObjectID& x, const OutputObjectID& y) -> bool {

if (x.oo.layer < y.oo.layer) return true;

if (x.oo.layer > y.oo.layer) return false;

if (x.oo.z_order < y.oo.z_order) return sortOrders[x.oo.layer];

if (x.oo.z_order > y.oo.z_order) return !sortOrders[x.oo.layer];

if (x.oo.geomType < y.oo.geomType) return true;

if (x.oo.geomType > y.oo.geomType) return false;

if (x.oo.attributes < y.oo.attributes) return true;

if (x.oo.attributes > y.oo.attributes) return false;

if (x.oo.objectID < y.oo.objectID) return true;

return false;

});

}

void sortTileCoordinates(

const size_t baseZoom,

const size_t threadNum,

std::deque<std::pair<unsigned int, TileCoordinates>>& tileCoordinates

)

{

boost::sort::block_indirect_sort(

tileCoordinates.begin(), tileCoordinates.end(),

[baseZoom](auto const &a, auto const &b) {

const auto aZoom = a.first;

const auto bZoom = b.first;

const auto aX = a.second.x;

const auto aY = a.second.y;

const auto bX = b.second.x;

const auto bY = b.second.y;

const bool aLowZoom = aZoom < CLUSTER_ZOOM;

const bool bLowZoom = bZoom < CLUSTER_ZOOM;

// Breadth-first for z0..5

if (aLowZoom != bLowZoom)

return aLowZoom;

if (aLowZoom && bLowZoom) {

if (aZoom != bZoom)

return aZoom < bZoom;

if (aX != bX)

return aX < bX;

return aY < bY;

}

for (size_t z = CLUSTER_ZOOM; z <= baseZoom; z++) {

// Translate both a and b to zoom z, compare.

// First, sanity check: can we translate it to this zoom?

if (aZoom < z || bZoom < z) {

return aZoom < bZoom;

}

const auto aXz = aX / (1 << (aZoom - z));

const auto aYz = aY / (1 << (aZoom - z));

const auto bXz = bX / (1 << (bZoom - z));

const auto bYz = bY / (1 << (bZoom - z));

if (aXz != bXz)

return aXz < bXz;

if (aYz != bYz)

return aYz < bYz;

}

return false;

threadNum);

}

tilemaker/src/tile_sorting.cpp at master · cyclemap/tilemaker · GitHub

Uh oh!

Expand file tree

Breadcrumbs

tile_sorting.cpp

Latest commit

History

Breadcrumbs

tile_sorting.cpp

File metadata and controls