предисловие
Неудивительно, что это последняя статья во всей серии Google S2. В этой статье будет ясно объяснен алгоритм regionCoverer. Что касается библиотеки Google S2, то там есть много других мелких алгоритмов, и код тоже стоит читать и изучать, поэтому я не буду их здесь раскрывать, заинтересованные читатели могут прочитать всю библиотеку.
При написании этой статьи я обнаружил несколько новых коммитов, сделанных автором библиотеки, таких как коммит f9610db2b871b54b17d36d4da6a4d6a2aab6018d от 4 декабря 2017 г. Представленные на этот раз изменения изменили README. , в нем много контента.
-For an analogous library in C++, see
-https://code.google.com/archive/p/s2-geometry-library/, and in Java, see
-https://github.com/google/s2-geometry-library-java
------------------------------------------------------------------------------------
+For an analogous library in C++, see https://github.com/google/s2geometry, in
+Java, see https://github.com/google/s2-geometry-library-java, and Python, see
+https://github.com/google/s2geometry/tree/master/src/python
Вы можете видеть, что они разместили код, который изначально существовал в официальном закрытом репозитории кода Google на github. Раньше вы могли просматривать код C++ только в архиве кода, но теперь вы можете просматривать его прямо на github. Гораздо удобнее.
+More details about S2 in general are available on the S2 Geometry Website
+[s2geometry.io](https://s2geometry.io/).
В этой фиксации также упоминается новый веб-сайт, который, как я обнаружил, был выпущен совсем недавно. Потому что за каждым коммитом S2 автор следил почти полгода. Отслеживается каждый ресурс в Интернете о S2, и этот сайт очень новый. Статья об этом сайте будет упомянута в конце, поэтому я не буду вдаваться в подробности.
С самого начала этого представления я считаю, что Google S2 может обратить на него внимание, и также может быть предназначен для продвижения.
Ну, официально вошел в тему.
1. Тип помещения
В Google S2 существуют следующие типы RegionCovering. В принципе, региональный интерфейс должен быть удовлетворен.
1. Крышка
Шапка представляет собой дискообразную область, ограниченную центром и радиусом. Технически эта форма называется «сферической крышкой» (а не диском), потому что она не плоская. Шляпка представляет собой часть сферы, отрезанную плоскостью. Границей шапки является окружность, определяемая пересечением сферы и плоскости. Шляпа – замкнутая композиция, т.е. содержит свои границы. В большинстве случаев сферические колпачки можно использовать независимо от того, используются ли диски в плоской геометрии. Радиус колпачка измеряется по поверхности сферы (а не по прямой линии внутри). Итак, шапка радиуса π/2 — это полусфера, а шапка радиуса π покрывает всю сферу. Центр — это точка на единичной сфере. (следовательно, она должна быть единичной длины). Шляпа также может быть определена по ее центральной точке и высоте. Высота — это расстояние от центральной точки до плоскости отсечки. Существуют также шапки, поддерживающие «пусто» и «полно», которые не содержат ни одной точки соответственно. Ниже приведены некоторые полезные зависимости между высотой крышки (h), радиусом крышки (r), максимальной длиной хорды в центре крышки (d) и радиусом дна крышки (a).
h = 1 - cos(r)
= 2 * sin^2(r/2)
d^2 = 2 * h
= a^2 + h^2
2. Петля
Петля представляет собой простой сферический многоугольник. Он состоит из последовательности вершин, где первая вершина неявно считается соединенной с последней вершиной. Все петли имеют ориентацию против часовой стрелки, т. е. внутренняя часть петли находится слева от края. Это означает, что петля по часовой стрелке, охватывающая небольшую область, интерпретируется как петля против часовой стрелки, охватывающая очень большую площадь. loop не допускает дублирования вершин (соседних или нет). Смежные ребра не могут пересекаться, а ребра длиной 180 градусов не допускаются (т. е. соседние вершины не могут быть противоположными). петля должна иметь не менее 3 вершин (за исключением «пустой» и «полной» петлей, обсуждаемых ниже). Есть два специальных цикла: EmptyLoop не содержит точек, а FullLoop содержит все точки. Эти петли не имеют ребер, но для того, чтобы сохранить инвариант, согласно которому каждую петлю можно представить как цепочку вершин, каждая из них определена так, чтобы иметь только одну вершину.
3. Полигон
Многоугольник представляет собой последовательность из нуля или более петель; аналогично, левое направление петли определяется как ее внутренняя часть. Данный цикл автоматически преобразуется в каноническую форму композиции «дырок» при инициализации полигона. Циклы переупорядочиваются, чтобы соответствовать заранее определенному способу прохождения уровня вложенности. Многоугольник может представлять собой любую область сферы с многоугольными границами, включая всю сферу (называемую «полным» многоугольником). Полный полигон состоит из полного цикла, а пустой полигон вообще не имеет цикла. Используйте FullPolygon() для построения полного многоугольника. Нулевое значение Polygon рассматривается как пустой многоугольник.
Если вы хотите, чтобы несколько контуров образовывали многоугольник Polygon, должны быть выполнены следующие 4 условия:
- петли не могут пересекаться, т. е. границы петли не могут пересекать внутреннюю и внешнюю части любой другой петли.
- Петли не имеют общих ребер, т. е. если петля содержит ребро AB, другие петли могут не содержать AB или BA.
- Циклы могут иметь общие вершины, но вершины не появляются дважды в одном цикле (см. S2Loop).
- Там не может быть пустой петлей. Полный цикл может появиться только в полном полигоне.
4. Прямоугольник
Rect представляет замкнутый прямоугольник широты и долготы. Он также относится к типу Region. Он способен представлять пустые и полные прямоугольники, а также отдельные точки. Он имеет метод AddPoint, который удобно строит ограничивающий прямоугольник для набора точек, в том числе наборов точек, охватывающих 180-градусный меридиан.
5. Регион
Регион представляет собой двумерную область на единичной сфере. Цель этого интерфейса — приблизить сложные области к более простым. Этот интерфейс ограничен методами, вычисляющими приблизительные значения.
Площадь S2 представляет собой двумерную область на единичной сфере. Это абстрактный интерфейс с различными конкретными подтипами, такими как диски, прямоугольники, полилинии, многоугольники, геометрические коллекции, формы буферов и т. д. Основной целью этого интерфейса является аппроксимация сложных областей более простыми областями. Таким образом, вместо широкого спектра виртуальных методов, реализованных всеми подтипами, интерфейсы можно использовать только для методов, вычисляющих приближения.
6. Форма
Форма считается «базового класса» шаблон или форму всех. Это может быть наиболее гибким способом представления геометрического многоугольника. Она состоит из множества ребер, внутренние необязательно определены. Все представленное данной геометрии Shape должен иметь тот же размер, что означает, что множество точек может быть представлена форма, набор полигонов или набор полигонов. Форма определяется как интерфейс, чтобы позволить клиенту более удобное управление лежащего в основе представления данных. Иногда форма не имеют свои собственные данные, но упаковка других типов данных. Форма операция обычно определяется на ShapeIndex, а не индивидуальная формы. Формы ShapeIndex просто набор может иметь различные размеры (например, 10 очков и три многоугольников), организованные в структуру данных, для эффективного доступа. Форма ребер индекса ID с начала непрерывного диапазона 0. Она подразделяется на краевые цепи, в которой ряд сторон (ломаные линии), соединенный с каждым концом компонентов цепи. Так, например, АВ представляет собой две линии сгиба и CDE в форме, имеющей две нити (AB) и (CD, DE) с трех сторон (АВ, CD, DE). Кроме того, представители пяти точек, имеющий форму, состоящую из пяти один край цепи. Форма того, чтобы использовать глобальный идентификатор (ID) края или боковую цепь доступа в конкретном методе. Глобальный номер достаточно для большей части, но цепи были очень полезны для некоторых алгоритмов (например, пересечение (См BooleanOperation)).
Всего в S2 определены два расширяемых интерфейса для представления геометрии: S2Shape и S2Region.
Разница между ними заключается в следующем: Целью S2Shape является гибкое представление полигональной геометрии. (Сюда входят не только полигоны, но и точки и полилинии). Большинство основных операций S2 будут работать с любым классом, реализующим интерфейс S2Shape.
Целью S2Region является приблизительное вычисление геометрии. Например, существуют методы вычисления ограничивающих прямоугольников и дисков, а S2RegionCoverer можно использовать для аппроксимации области с любой желаемой точностью в виде набора ячеек. В отличие от S2Shape, S2Region может представлять неполигональные геометрические фигуры, такие как сферические колпачки (S2Cap).
В дополнение к упомянутым выше общим типам существуют также следующие промежуточные типы или типы более низкого уровня, которые могут использоваться разработчиками.
- S2LatLngRect — прямоугольник в системе координат широты и долготы.
- S2POLYLINE - Пассажирский.
- S2CellUnion — регион, который приближается к набору идентификаторов S2CellId. RegionCoverer относится к этому типу после преобразования.
- S2ShapeIndexRegion — Произвольный набор точек, полилиний и полигонов.
- S2ShapeIndexBufferedRegion — определяется так же, как S2ShapeIndexRegion, но расширяется на заданный радиус.
- S2RegionUnion — набор произвольных регионов.
- S2RegionIntersection — пересечение любого другого региона.
Наконец, дополнительный момент, тип S2RegionTermIndexer поддерживает индексацию и запросы любого типа S2Region, то есть всех упомянутых выше типов. Вы можете использовать S2RegionTermIndexer для индексации набора полилиний, а затем запрашивать, какие полилинии пересекают заданный полигон.
2. Пример RegionCoverer
RegionCoverer в основном предназначен для поиска приблизительного оптимального решения, которое может покрыть текущий регион (почему не оптимальное решение?)
Есть три основных условия преобразования: MaxLevel, MaxCells, MinLevel. MaxCells определяет максимальное количество ячеек, но если оно слишком близко к максимальному значению, это приведет к тому, что зона покрытия будет слишком большой и неточной. Таким образом, максимальное число ограничено только тем, чтобы не превышать это число при условии, что соблюдается максимальная точность. Из-за этого это не оптимальное решение, удовлетворяющее MaxCells.
Приведу несколько примеров:
Ниже представлена шапка радиусом 10 километров, и расположена эта шапка по углам 3 граней.Мы предполагаем, что для ее покрытия необходимо максимальное количество 10 ячеек. Результат выглядит следующим образом:
Те же настройки, мы меняем число на 20, следующим образом:
Все та же конфигурация, измените число на 50:
До настоящего времени достоверность так-такового края охвата сектора или больше, чем оригинальная крышка, и мы продолжаем улучшать точность, отрегулируйте номер до 200.
200 кажется более точным, давайте увеличим его до 1000 и посмотрим, что получится.
Хотя в конфигурации кода установлено 1000 ячеек, на самом деле их всего 706. Причина в том, что, хотя код рассчитывается в соответствии с 1000, фактическая обработка алгоритма также будет объединена после сокращения ячеек. Таким образом, окончательное число будет меньше 1000.
В качестве другого примера прямоугольник ниже представляет прямоугольник широты/долготы, простирающийся от 60 градусов северной широты до 80 градусов северной широты и от -170 градусов долготы до +170 градусов. Покрытие ограничено 8 единицами. Обратите внимание, что отверстие в середине полностью закрыто. Это явно не то, что мы планировали.
Увеличиваем количество ячеек до 20. Отверстие в середине все еще заполнено.
Мы установили параметры на 100, и другие конфигурации были точно такими же. Отверстие в середине теперь имеет определенную форму. Но пустое место возле линии даты все равно не выходит.
Наконец, настройте параметры на 500. Отверстие посередине теперь отображается более полно.
Вот несколько примеров, используемых в наших фактических проектах. Ниже приведен край сетки в Шанхае. Сначала мы используем
defaultCoverer := &s2.RegionCoverer{MaxLevel: 16, MaxCells: 100, MinLevel: 13}
Для преобразования результат выглядит следующим образом:
defaultCoverer := &s2.RegionCoverer{MaxLevel: 30, MaxCells: 1000, MinLevel: 1}
Увеличьте точность до 1000, и результат будет следующим:
Есть также некоторые более крупные области, такие как провинция Хубэй:
Или озеро, Тайху:
Наконец, приведен пример полигона. Мы знаем, что многоугольник состоит из нескольких циклов:
loops := []*s2.Loop{}
loops = append(loops, loop1)
loops = append(loops, loop2)
polygon := s2.PolygonFromLoops(loops)
defaultCoverer := &s2.RegionCoverer{MaxLevel: 16, MaxCells: 100, MinLevel: 8}
fmt.Println("---- polygon-----")
cvr = defaultCoverer.Covering(polygon)
for i := 0; i < len(cvr); i++ {
fmt.Printf("%d,\n", cvr[i])
}
fmt.Printf("------------\n")
Ниже показано, как две петли выглядят на карте один раз.
Наконец, Polygon, который содержит 2 LOOP выше.
3. Реализация основного алгоритма покрытия RegionCoverer
В этой главе подробно анализируется, как реализуется покрытие.
Чаще всего используются следующие строки:
rc := &s2.RegionCoverer{MaxLevel: 30, MaxCells: 5}
r := s2.Region(CapFromCenterArea(center, area))
covering := rc.Covering(r)
В приведенном выше примере показано, что после преобразования в CellUnion осталось не более 5 идентификаторов CellID. Область, охваченная тремя линиями выше, является кепкой.
type RegionCoverer struct {
MinLevel int // the minimum cell level to be used.
MaxLevel int // the maximum cell level to be used.
LevelMod int // the LevelMod to be used.
MaxCells int // the maximum desired number of cells in the approximation.
}
RegionCoverer — это структура, которая на самом деле содержит 4 элемента. MinLevel, MaxLevel, MaxCells, эти три не нужно объяснять, они используются очень часто. Ключ в том, чтобы объяснить LevelMod.
После установки значения LevelMod при выполнении преобразования RegionCover выбранный уровень ячейки может быть только (уровень - MinLevel) % LevelMod = 0, то есть (уровень - MinLevel) может быть только кратным LevelMod, а уровень ячейки уровень, удовлетворяющий этому условию, будет выбран. Это эффективно позволяет увеличивать фактор ветвления на уровне S2 CellID. Текущие значения параметров могут быть только 0, 1, 2, 3, а соответствующие коэффициенты ветвления равны 0, 4, 16, 64.
Поговорим об основной идее алгоритма.
RegionCover можно абстрагироваться в такой задаче, задан регион, покрыть его максимально точными Cells, но количество не должно превышать количество MaxCells, спросите, как найти эти Cells?
Эта проблема является недальновидной задачей оптимального решения. Если вам нужна максимальная точность, конечно, решение состоит в том, чтобы использовать MaxLevel для всех краевых частей (чем больше уровень, тем меньше сетка), что является наиболее точным. Но это приведет к резкому увеличению количества ячеек, намного превышающему MaxCells, поэтому оно не соответствует требованиям. Итак, как можно обеспечить наиболее точное покрытие заданной области с помощью
Несколько вещей, которые следует отметить заранее:
-
- MinLevel имеет более высокий приоритет, чем MaxCells (обратите внимание, что здесь не MaxLevel), то есть ячейки ниже заданного уровня никогда не будут использоваться, даже если можно заменить множество ячеек небольшими областями (большими уровнями).
-
- Для минимального диапазона MaxCells может быть возвращено до 6 ячеек, если ситуация требует минимально необходимого количества ячеек (например, если область пересекает все шесть ячеек грани). Если он окажется на пересечении трех граней куба, может быть возвращено до 3 ячеек даже для очень маленьких приподнятых областей.
-
- Если MinLevel слишком велик для приблизительной области, то MaxCells выходит за границы и может возвращать любое количество ячеек.
-
- Если MaxCells меньше 4, даже если область выпуклая, например, колпачок или прямоугольник, конечная покрытая область будет больше исходной области. Так что разработчики должны быть в курсе этой ситуации.
Что ж, начнем с исходного кода. Это основная функция преобразования RegionCoverer.
func (rc *RegionCoverer) Covering(region Region) CellUnion {
covering := rc.CellUnion(region)
covering.Denormalize(maxInt(0, minInt(maxLevel, rc.MinLevel)), maxInt(1, minInt(3, rc.LevelMod)))
return covering
}
Из реализации этой функции мы видим, что преобразование на самом деле разделено на 2 шага, один — «Нормализовать ячейку + преобразование», а другой — «Денормализовать ячейку».
(1).
Конкретная реализация метода CellUnion:
func (rc *RegionCoverer) CellUnion(region Region) CellUnion {
c := rc.newCoverer()
c.coveringInternal(region)
cu := c.result
cu.Normalize()
return cu
}
Этот метод также можно разбить на три части: новый newCoverer, CoverInternal, Normalize.
1. newCoverer()
func (rc *RegionCoverer) newCoverer() *coverer {
return &coverer{
minLevel: maxInt(0, minInt(maxLevel, rc.MinLevel)),
maxLevel: maxInt(0, minInt(maxLevel, rc.MaxLevel)),
levelMod: maxInt(1, minInt(3, rc.LevelMod)),
maxCells: rc.MaxCells,
}
}
Метод newCoverer() предназначен для инициализации структуры покровителя. maxLevel — ранее определенная константа, maxLevel = 30. Все параметры инициализации покровителя исходят из параметров RegionCoverer. Мы инициализировали RegionCoverer извне, и здесь будут переданы его основные четыре параметра: MinLevel, MaxLevel, LevelMod и MaxCells. maxInt и minInt, используемые в приведенной выше функции инициализации, в основном используются для обработки недопустимых значений.
На самом деле конструкция крышки содержит 8 элементов.
type coverer struct {
minLevel int // the minimum cell level to be used.
maxLevel int // the maximum cell level to be used.
levelMod int // the LevelMod to be used.
maxCells int // the maximum desired number of cells in the approximation.
region Region
result CellUnion
pq priorityQueue
interiorCovering bool
}
В дополнение к 4 элементам, инициализированным выше, он фактически содержит 4 других важных элемента, которые будут использоваться ниже. регион Область покрытия. result — результат окончательного преобразования, result — массив CellUnion, pq — PriorityQueue, а interiorCovering — логическая переменная, указывающая, является ли текущее преобразование внутренним преобразованием.
2. coveringInternal()
Далее посмотрите на метод coverInternal.
func (c *coverer) coveringInternal(region Region) {
c.region = region
c.initialCandidates()
for c.pq.Len() > 0 && (!c.interiorCovering || len(c.result) < c.maxCells) {
cand := heap.Pop(&c.pq).(*candidate)
if c.interiorCovering || int(cand.cell.level) < c.minLevel || cand.numChildren == 1 || len(c.result)+c.pq.Len()+cand.numChildren <= c.maxCells {
for _, child := range cand.children {
if !c.interiorCovering || len(c.result) < c.maxCells {
c.addCandidate(child)
}
}
} else {
cand.terminal = true
c.addCandidate(cand)
}
}
c.pq.Reset()
c.region = nil
}
Метод coverInternal генерирует схему покрытия и сохраняет результат в result. Общая стратегия переопределения преобразований:
Начните с 6 граней куба. Любые фигуры, которые не пересекают область, отбрасываются. Затем несколько раз выберите самую большую ячейку, которая пересекает фигуру, и разделите ее..
Из 8 элементов в структуре покровителя первые 4 передаются и инициализируются извне, а здесь используются последние 4 элемента. первый
c.region = region
Инициализируйте область покрытия. Остальные три элемента — result, pq и interiorCovering — используются ниже.
Результат содержит только подходящие ячейки, которые будут частью окончательного вывода, в то время как приоритетная очередь pq содержит ячейки, которые, возможно, все еще необходимо разделить.
Если ячейка на 100 % полностью содержится в области покрытия, она немедленно добавляется к выходным данным, а ячейки, вообще не имеющие никакого пересечения с областью, немедленно отбрасываются. Таким образом, очередь с приоритетом pq будет содержать только те ячейки, которые пересекаются с этой областью.
Стратегия исключения из очереди приоритетной очереди pq:
1. Расставьте приоритеты кандидатов в зависимости от размера ячейки (сначала большие ячейки)
2. Затем в соответствии с количеством пересекающихся детей (наименьший ребенок имеет более высокий приоритет и первым удаляется из очереди)
3. Наконец, по количеству полностью размещенных детей (наименее ребенок имеет более высокий приоритет и указывается первым)
После отсеивания очереди с приоритетом pq последняя оставшаяся Ячейка должна иметь самый низкий приоритет, то есть площадь ячейки относительно мала, а та часть, которая пересекается с областью, больше и полностью вмещает наибольшее количество детей. То есть ячейка, ближайшая к краю области (область, покрываемая ячейкой, наименее избыточна, чем область, подлежащая преобразованию), в конечном итоге будет оставлена.
if c.interiorCovering || int(cand.cell.level) < c.minLevel || cand.numChildren == 1 || len(c.result)+c.pq.Len()+cand.numChildren <= c.maxCells {
}
Назначение этого предикатного условия в реализации функции coverInternal:
Что касается конверсий внутреннего охвата, мы продолжаем непрерывно сегментировать их, независимо от того, сколько детей у кандидата. Если мы доберемся до MaxCells до расширения всех дочерних элементов, мы будем использовать только некоторые из них. Для внешнего покрытия мы не можем этого сделать, потому что результат должен покрывать всю область, поэтому все дочерние элементы должны использоваться.
candidate.numChildren == 1
В приведенном выше случае у нас уже есть больше результатов MaxCells (minLevel слишком высок), чтобы позаботиться о ситуации. Даже дальнейшее разделение кандидатов с одним ребенком в этом случае мало повлияет на окончательный результат.
3. initialCandidates()
Далее посмотрим, как инициализировать кандидатов:
func (c *coverer) initialCandidates() {
// Optimization: start with a small (usually 4 cell) covering of the region's bounding cap.
temp := &RegionCoverer{MaxLevel: c.maxLevel, LevelMod: 1, MaxCells: min(4, c.maxCells)}
cells := temp.FastCovering(c.region)
c.adjustCellLevels(&cells)
for _, ci := range cells {
c.addCandidate(c.newCandidate(CellFromCellID(ci)))
}
}
В этой функции есть небольшая оптимизация, которая преобразует покрытие первого шага области в 4 ячейки, которые покрывают край области. Двумя наиболее важными методами в реализации метода initialCandidates являются FastCovering и AdjustCellLevels.
4. FastCovering()
func (rc *RegionCoverer) FastCovering(region Region) CellUnion {
c := rc.newCoverer()
cu := CellUnion(region.CellUnionBound())
c.normalizeCovering(&cu)
return cu
}
Функция FastCovering вернет коллекцию CellUnion, ячейки в этой коллекции покрывают заданную область, но отличие этого метода в том, что этот метод быстрый, а результат относительно грубый. Разумеется, получившийся набор CellUnion также соответствует требованиям MaxCells, MinLevel, MaxLevel и LevelMod. Просто оказалось, что он не пытается использовать большое значение MaxCells. Как правило, возвращается небольшое количество ячеек, поэтому результаты приблизительны.
Таким образом, использование функции FastCovering в качестве отправной точки для рекурсивного разделения ячейки очень полезно.
В этом методе вызывается метод region.CellUnionBound(). Это зависит от того, как каждый регион реализует этот интерфейс.
Взяв в качестве примера цикл, цикл реализует CellUnionBound() следующим образом:
func (l *Loop) CellUnionBound() []CellID {
return l.CapBound().CellUnionBound()
}
Вышеупомянутый метод является конкретной реализацией быстрого расчета граничного преобразования. Это также является основной частью реализации космического охвата.
CellUnionBound возвращает массив CellID для зоны покрытия. Ячейки не сортируются, могут иметь избыточность (например, ячейки, содержащие другие ячейки), могут занимать большую площадь, чем необходимо.
Также по вышеуказанной причине этот метод не подходит для прямого использования клиентским кодом. Обычно клиентам следует использовать метод Region.Covering, который можно использовать для управления размером и точностью покрытия. В качестве альтернативы, если вы хотите быстрое покрытие и не заботитесь о точности, рассмотрите возможность вызова FastCovering (который возвращает очищенную версию покрытия, вычисленного этим методом).
Реализация CellUnionBound должна попытаться вернуть небольшое покрытие зоны покрытия (в идеале 4 или меньше) и быть быстрой для вычислений. Таким образом, метод CellUnionBound используется RegionCoverer в качестве отправной точки для дальнейших улучшений.
func (l *Loop) CapBound() Cap {
return l.bound.CapBound()
}
CapBound возвращает ограничивающий колпачок, который может иметь больше отступов, чем соответствующий RectBound. Его границы консервативны, и если петля содержит точку P, то границы также должны содержать эту точку.
func (c Cap) CellUnionBound() []CellID {
level := MinWidthMetric.MaxLevel(c.Radius().Radians()) - 1
// If level < 0, more than three face cells are required.
if level < 0 {
cellIDs := make([]CellID, 6)
for face := 0; face < 6; face++ {
cellIDs[face] = CellIDFromFace(face)
}
return cellIDs
}
return cellIDFromPoint(c.center).VertexNeighbors(level)
}
Приведенный выше код является самой грубой версией основного алгоритма преобразования. Основным шагом в этом алгоритме является вычисление уровня, который необходимо найти.
level := MinWidthMetric.MaxLevel(c.Radius().Radians()) - 1
Уровень, найденный здесь, является самой большой ячейкой, которую может содержать крышка.
return cellIDFromPoint(c.center).VertexNeighbors(level)
Приведенное выше предложение возвращает 4 ячейки, ближайшие к центру шапки. Конечно, если Шапка очень большая, можно вернуть 6 ячеек. Разумеется, возвращаемые ячейки никак не сортируются.
5. normalizeCovering()
Последним шагом FastCovering является нормализация покрытия.
func (c *coverer) normalizeCovering(covering *CellUnion) {
// 1
//
if c.maxLevel < maxLevel || c.levelMod > 1 {
for i, ci := range *covering {
level := ci.Level()
newLevel := c.adjustLevel(minInt(level, c.maxLevel))
if newLevel != level {
(*covering)[i] = ci.Parent(newLevel)
}
}
}
// 2
//
covering.Normalize()
// 3
//
for len(*covering) > c.maxCells {
bestIndex := -1
bestLevel := -1
for i := 0; i+1 < len(*covering); i++ {
level, ok := (*covering)[i].CommonAncestorLevel((*covering)[i+1])
if !ok {
continue
}
level = c.adjustLevel(level)
if level > bestLevel {
bestLevel = level
bestIndex = i
}
}
if bestLevel < c.minLevel {
break
}
(*covering)[bestIndex] = (*covering)[bestIndex].Parent(bestLevel)
covering.Normalize()
}
// 4
//
if c.minLevel > 0 || c.levelMod > 1 {
covering.Denormalize(c.minLevel, c.levelMod)
}
}
normalizeCovering дополнительно нормализует результат преобразования покрытия на предыдущем шаге, чтобы он соответствовал текущим параметрам покрытия (MaxCells, minLevel, maxLevel и levelMod). Этот метод не будет пытаться получить наилучшие результаты. В частности, если minLevel > 0 или levelMod > 1, он может вернуть больше значений, чем ожидается для Cell, хотя это и не требуется.
В приведенной выше реализации кода есть 4 места, которые требуют внимания.
Первый, оцененный, заключается в том, что если ячейки слишком малы или не соответствуют условиям levelMod, заменить их их предками.
Второй — отсортировать и упростить результаты предыдущего шага.
В-третьих, если ячеек все еще слишком много и ячеек слишком много, используйте цикл for, чтобы найти ближайшего общего предка LCA двух соседних ячеек и заменить их.Порядок цикла for соответствует циклу CellID в последовательности.
Используемая здесь конкретная реализация LCA подробно описана в предыдущей статье.Ссылка на статью, и здесь повторяться не будем.
В-четвертых, окончательно убедитесь, что полученный результат соответствует minLevel и levelMod, желательно MaxCells.
Следующее, что требует дальнейшего анализа, — это реализация двух функций Normalize() и Denormalize().
6. Normalize()
Сначала посмотрите на Normalize().
func (cu *CellUnion) Normalize() {
sortCellIDs(*cu)
output := make([]CellID, 0, len(*cu)) // the list of accepted cells
for _, ci := range *cu {
// 1
if len(output) > 0 && output[len(output)-1].Contains(ci) {
continue
}
// 2
j := len(output) - 1 // last index to keep
for j >= 0 {
if !ci.Contains(output[j]) {
break
}
j--
}
output = output[:j+1]
// 3
for len(output) >= 3 && areSiblings(output[len(output)-3], output[len(output)-2], output[len(output)-1], ci) {
output = output[:len(output)-3]
ci = ci.immediateParent() // checked !ci.isFace above
}
output = append(output, ci)
}
*cu = output
}
Основная цель метода Normalize — отсортировать CellID в CellUnion и вывести CellUnion без избыточности после сортировки.
Сортировка — это первый шаг.
Далее, отбраковка лишних ячеек — это второй шаг, и это также ключевой шаг в реализации этой функции. Избыточность делится на 2 вида, один — полное включение, а другой — 4 маленькие ячейки можно объединить в одну большую.
Во-первых, проверьте, есть ли ячейка, которая полностью содержит другую ячейку.В этом случае включенная ячейка является избыточной ячейкой и должна быть отброшена. Он соответствует месту, отмеченному цифрой 1 в приведенном выше коде.
С точки зрения реализации нам нужно проверить только последнюю принятую ячейку. Если после первой сортировки ячеек текущая ячейка-кандидат не содержится в последней принятой ячейке, то она не может содержаться ни в каких ранее принятых ячейках.
Точно так же, если текущая ячейка-кандидат содержит ячейки, которые были проверены ранее, ячейки, которые ранее были в выходных данных, также должны быть отброшены. Поскольку вывод поддерживает непрерывную хвостовую последовательность, как упоминалось ранее, ячейка S2 сортируется, поэтому ее непрерывность здесь не может быть нарушена. Это соответствует месту, отмеченному цифрой 2 в приведенном выше коде.
Место, отмеченное цифрой 3 в окончательном коде, предназначено для того, чтобы посмотреть, можно ли объединить последние три ячейки с этим дополнением. Если 3 последовательные ячейки плюс текущая ячейка могут быть каскадированы до ближайшего родительского узла, мы заменяем все три из них ячейкой большего размера.
После «форматирования» шага «Нормализация» все выходные ячейки являются упорядоченными и неизбыточными ячейками.
7. Denormalize()
func (cu *CellUnion) Denormalize(minLevel, levelMod int) {
var denorm CellUnion
for _, id := range *cu {
level := id.Level()
newLevel := level
if newLevel < minLevel {
newLevel = minLevel
}
if levelMod > 1 {
newLevel += (maxLevel - (newLevel - minLevel)) % levelMod
if newLevel > maxLevel {
newLevel = maxLevel
}
}
if newLevel == level {
denorm = append(denorm, id)
} else {
end := id.ChildEndAtLevel(newLevel)
for ci := id.ChildBeginAtLevel(newLevel); ci != end; ci = ci.Next() {
denorm = append(denorm, ci)
}
}
}
*cu = denorm
}
Denormalize Эту функцию очень просто реализовать, это обратная сторона normalize (хотя название не имеет смысла). Эта функция предназначена для «регулирования» того, удовлетворяет ли ячейка нескольким предопределенным условиям перед переходом наложения: MinLevel, MaxLevel, LevelMOD, MaxCell.
Любая ячейка, уровень которой меньше minLevel или (level-minLevel) не кратен levelMod, будет заменена ее дочерними элементами до тех пор, пока не будут выполнены оба условия или не будет достигнут maxLevel.
Назначение функции Denormalize — гарантировать, что результирующие результаты удовлетворяют требованиям minLevel и levelMod, а предпочтительно — MaxCells.
На данный момент читатель должен также знать, почему функция называется денормализом. Для того, чтобы соответствовать условиям, он заменяет большую клетку со своим собственным ребенком, небольшую ячейку, в то время как нормализуется только наоборот.
На данный момент функция FastCovering() была проанализирована.
8. adjustCellLevels()
В функции initialCandidates() есть еще один шаг после FastCovering() в этой функции, AdjustCellLevels.
c.adjustCellLevels(&cells)
Далее давайте взглянем на конкретную реализацию AdjustCellLevels.
func (c *coverer) adjustCellLevels(cells *CellUnion) {
if c.levelMod == 1 {
return
}
var out int
for _, ci := range *cells {
level := ci.Level()
newLevel := c.adjustLevel(level)
if newLevel != level {
ci = ci.Parent(newLevel)
}
if out > 0 && (*cells)[out-1].Contains(ci) {
continue
}
for out > 0 && ci.Contains((*cells)[out-1]) {
out--
}
(*cells)[out] = ci
out++
}
*cells = (*cells)[:out]
}
AdjustCellLevels используется для обеспечения того, чтобы все ячейки с уровнем > minLevel также удовлетворяли levelMod, при необходимости заменяя их предками. Для тех ячеек, которые меньше minLevel, их уровни не будут изменены (см. Настройка уровней). Конечным результатом является нормализованный CellUnion, чтобы гарантировать отсутствие избыточных ячеек.
AdjustCellLevels похож на Denormalize, оба настраивают CellUnion в соответствии с условиями. Однако направления корректировки у них разные: Denormalize — заменить ячейку в направлении дочернего узла, а AdjustCellLevels — заменить ячейку в направлении родительского узла.
func (c *coverer) adjustLevel(level int) int {
if c.levelMod > 1 && level > c.minLevel {
level -= (level - c.minLevel) % c.levelMod
}
return level
}
Назначение AdjustLevel состоит в том, чтобы вернуть более низкий уровень, чтобы он удовлетворял условию levelMod. Уровни ниже minLevel не затрагиваются (поскольку ячейки на этих уровнях в конечном итоге будут обработаны функцией Denormalize).
(2) Денормализация
Реализация Denormalize была проанализирована выше. Тут уже не до анализа.
(3) Резюме
Используйте изображение, чтобы представить весь процесс Google S2, охватывающий всю пространственную область:
Каждая ключевая реализация на приведенном выше рисунке была проанализирована, и учащиеся, которые до сих пор не понимают, какой узел могут повернуть назад и посмотреть вверх.
Этот алгоритм аппроксимации не оптимален, но хорошо работает на практике. В выходном результате не всегда используется максимальное количество ячеек, соответствующих условиям, потому что это не всегда дает лучший приблизительный результат (например, в приведенном выше примере покрываемая область находится на пересечении трех граней , полученный результат намного больше, чем исходная площадь) и MaxCells является пределом рабочей нагрузки поиска и количества окончательно выводимых ячеек.
Поскольку это приблизительный алгоритм, нельзя полагаться на стабильность его вывода. В частности, выходные данные алгоритма наложения будут различаться в разных версиях библиотеки.
Этот алгоритм также может генерировать внутренние покрывающие ячейки, т. е. ячейки, полностью содержащиеся в области. Если нет ячейки, удовлетворяющей условию, внутренняя покрывающая ячейка может быть пустой даже для непустых областей.
Обратите внимание, что по соображениям производительности целесообразно указывать MaxLevel при расчете внутренней ячейки покрытия. В противном случае для небольших областей или областей с нулевой площадью алгоритм может потратить много времени на разделение ячеек до листового уровня в попытке найти ячейки, удовлетворяющие условиям внутреннего покрытия.
4. Наконец
На этом цикл статей о космическом поиске подошёл к концу, ну и конечно же в конце я расскажу о некоторых впечатлениях.
Изучая и отрабатывая знания о космическом поиске, мы с автором проверяли три аспекта физики, математики и алгоритмов и совершенствовали познание всего пространства и времени с двух уровней физики и математики. Хотя нынешнее личное познание в этом отношении все еще может быть очень поверхностным, оно действительно значительно улучшилось по сравнению с предыдущим. Цель также достигнута.
Последнее — порекомендовать 2 веб-сайта, которые также являются наиболее часто задаваемыми вопросами на Weibo.
Первый вопрос: какая из серий S2 Cell насколько вытянута?
На самом деле это сайт человека с открытым исходным кодом,s2map.com/, автор заполняет здесь рассчитанный программой CellID, а затем отображает его. Это эквивалентно инструменту визуального отображения исследований S2.
Второй вопрос: почему некоторый код не находит соответствующей реализации в версии Go?
Ответ заключается в том, что версия Go еще не завершена на 100%, и каждому необходимо обратиться к полной версии C++ и Java. Что касается исходного кода C++ и Java, Google несколько дней назад переместил код из частных репозиториев на Github. Легче учиться и просматривать. Чиновник также организовал некоторые документы вs2geometry.io/на этом сайте. Новичкам рекомендуется сначала прочитать официальную документацию по API. После прочтения документа все еще остаются некоторые сомнения в принципе.Вы можете прочитать серию статей автора о космическом поиске, надеясь помочь читателям.
Статьи из серии «Пространственный поиск»:
Как понять n-мерное пространство и n-мерное пространство-время
Эффективные алгоритмы индексации многомерных пространственных точек — Geohash и Google S2
Как генерируется CellID в Google S2?
Quadtree в Google S2 для поиска ближайшего общего предка LCA
Волшебная последовательность де Брюйне
Как найти соседей кривой Гильберта на дереве квадрантов?
Как Google S2 решает оптимальное решение пространственного охвата?
Репозиторий GitHub:Halfrost-Field
Follow: halfrost · GitHub
Source: HAL frost.com/go_is 2_reg IO…