Алгоритм сложения /двух произвольных контуров, образующих многосвязанные области

Основным концентратором селена, помимо м инерал ообразую;дих минералов, является блеклая руда. Согласно данным рентгеноспектрального анапиза селен присутствует во всех минеральных типах блеклых руд, без явного преобладания в каком-либо из них. Следует отметить, что в блеклых рудах переменного состава среднее содержание селена немного выше (1,05 мае. %), чем в теллуристых, сурьмянистых и мышьяковистых (0,73, 0,51 и 0,24 мае. % соответственно).

Значительно высокие концентрации селена отмечаются в теллуридах месторождения. Так, гессит содержит до 5,86 мае. % селена, петцит до 5,84 мае. %, курилит до 7,47 мае. %. сильванит до 0,51 мс. %. Особое место в рудах Прасоловского месторождения занимают селенсодержащие теллуриды. Среди теллуридов месторождения установлен селенистый теллур, содержания теллура и селена которого, согласно данным микрозондового анализа, соответственно 53, i 6 и 45,74 мае. %. Расчет состава этого селенистого теллура на 7 атомов в формуле соответствует формуле Te^Se^. Селенистый теллур присутствует в виде редких мелких включений в кварце. Их размер в среднем составляет 0,005 мм. Кроме того, он образует мало мощные прожилки (0,002 мм) в клаусталите и самородном теллуре. , "*

В рудах месторождения обнаружен теллурид висмута, содержащий более 8 мае. % селена. Следует отметить, что сведения о подобных селенсодержащих практически бессернистых теллуридах висмута на сегодняшний день в литературе отсутствуют, Теллурид висмута образует мелкие (до 0,015 мм и менее) удлиненные, изометричные близкие к идиоморфным зерна, находящиеся в тесном срастании с самородным теллуром, алтаитом и гесситом, и также локализуется в кварцевых прожилках и краевых частях теллуристой блеклой руды.

Селен в значительных количествах присутствует в прустите, где его значения колеблется в интервале величин от 2,49 до 7,49 мае. %. Незначительные содержания селена отмечены в витгихените (0,11 мае. %), акантите (1.32 мае. %), борните (0,84 мае. %), ковеллине (0,92 мае. %), рокезите (0,25 мае. %).

Таким образом, селен присутствует во всех минеральных классах, где его количества варьируют. Так, в самородных элементах его содержание изменяется от 0,19-1,16 мае. %, в сульфидах - 0,01-5,58 мае. %, в селенидах - 19,85-50,04 мае. %, теллуридах - 0,20-7,47 мае. %, сульфосолях -0,12-7,49 мае. %.

Широкое распространение селена в рудах Прасоловского месторождения видимо связано с тем, что в заключительные стадии минералообразования активность селена была настолько высокой, что селенидизации подверглись и большинство ранее отложенных минералов. ? • ;

: ^ ? В.А. Смолин

АЛГОРИТМ СЛОЖЕНИЯ ДВУХ ПРОИЗВОЛЬНЫХ КОНТУРОВ, ОБРАЗУЮЩИХ

МНОГОСВЯЗАННЫЕ ОБЛАСТИ

Во многих задачах компьютерной графики требуется объединить два произвольных полигона и получить новый полигон. Например, при объединении данных нескольких экспедиций разных лет требуется провести наложение полигонов съемок с целью получения общей картины данных.

В большинстве случаев подобного рода используют объединение выпуклых многоугольников. Для такого рода задач, существует множество алгоритмов. Однако, после первого объединения мы можем получить область сложной, чаще всего не выпукл ой формы. А это требу ет использования алгоритмов, решающих задачу объединения произвольных полигонов. Ранее [1] эта проблема была рассмотрена для случая односвязанных произвольных многоугольников.

Формулировка задачи

На плоскости заданы два полигона Р{ = {р},/?„} и Р2 = {р},р2*—>Рк I состоящие из п> 2 и к > 2 точек соответственно (рис. 1). Д™ замыкания границ полигонов последняя точка должна совпадать с первой. Требуется построить объединенный полигон Ра - \рх ,р2,...,рт}

Рис. 1. Объединение полигонов

Как видно (рис. 1) все узловые точки можно разделить на категории: узловые точки, принадлежащие только одному полигону и лежащие вне границ другого, узловые точки, лежащие на границах обеих полигонов и узловые точки являющиеся внутренними для другого полигона.

Алгоритм

Выберем направление координатных осей: X направо, У вверх. Обход контура полигонов будем совершать по часовой стрелке.

Основная идея алгоритма основана на топологических свойствах массива точек. На рис. { хорошо видно, что все точки, окрашенные синим цветом, образуют узлы енешней границы объединенного полигона. Помимо этого узловыми точками границы объединенного полигона могут быть точки лежащие на границах обеих полигонов (красные), а также точки пересечения ребер обеих полигонов.

1. Создаем два вектора целых чисел и /2 размерностью пик соответственно (размерность соответствует числу узловых граничных точек полигонов Р, и Рг соответственно).

2. Решаем задачу принадлежности точек полигона Р2 полигону Рх . Для решения используем алгоритм, изложенный в [2]. Каждую точку заносим в вектор /2, маркируя значением:

-1 - точка не принадлежит Р, (внешняя);

О - точка лежит на границе Р{; ^ •

] - точке лежит внутри Р{.

3. Если среди элементов вектора /2 нет ни одного равного -1, то полигон Р2 целиком лежит в полигоне Р], а искомая граница-точки полигона Р,, вычисления заканчиваются.

*1 ' 4 Решаем задачу принадлежности точек полигона Р} полигону Р2. Каждую точку заносим в вектор Д, маркируя значением: • ^^ /

-1 - точка не принадлежит Р-, (внешняя);

О - точка лежит на границе Р2; ^ - ъуа

: 1 — точке лежит внутри Р2. (

5. Создаем два вектора и Ь2 для хранения логического признака использования внешних точек при формировании границы объединенного полигона. Размерности векторов совпадают с размерностью векторов /, и /, соответственно.

6. Для отслеживания отрезков, принадлежащим полигонам Р1 и Р2 вводим переменные

п\, п2 и £1, к2 в которых будут храниться текущие индексы начальной и конечной точек

соответствующих ребер полигонов (индексы точек полигонов изменяются от 0 до и — 1 и £ — 1 соответственно).

7. Создаем вектора D\ и D2 размерностью пик для Рх и Р2 соответственно, в которых будут храниться специальные структуры данных о пересечениях сторон:

Record /У — данные о пересечении i-ro ребра полигона j-ьш ребром другого vn // — вектор индексов начальных точек i-ro ребра пересечения (целые числа) vt // — вектор типов пересечений (целые числа) Р //— вектор координат точек пересечения end;

8. Организуем цикл формирования вектора структуры DI, для чего каждое ребро из Л проверяется на пересечение со всеми ребрами из Р2. Для ускорения вычислений считаем, что если обе точки текущего ребра из Рх внешние, то у этого ребра пересечений нет. Соответственно размерности векторов vn, vt и Р остаются равными 0. Если концы текущего ребра из Р2 состоят из внешних точек, то оно при вычислениях пропускается. Если отрезки пересекаются, используется следующая система кодировок типов пересечения: . , ,

0 - отрезки пересекаются

1 - отрезки совпадают П '

2 - начало 2-го отрезка принадлежит 1-му отрезку -

3 - конец 2-го отрезка принадлежит 1-му отрезку

4 - 2-й отрезок лежит внутри 1-го отрезка • j

5 - 1-й отрезок лежит внутри 2-го отрезка

9. Формируем вектор D2 . Для исключения лишних вычислений можно организовать пересылку данных из D1 в D2.

10. Полигон Рх считаем основным и ищем начальный индекс п\ , который соответствует точке внешней по отношению к полигону Р->. Найденную точку заносим в результирующий массив объединенной границы для полигонов и помечаем ее как использованную..

11. Вычисляем п2 ~ п\ +1, если значение п2 > п -1, го полагаем его равным 0.

12. Если обе точки текущего отрезка Рх являются внешними, то концевую точку отрезка

заносим в результирующий массив, помечая ее как используемую. Полагаем п\ = п2 . За начальную точку нового отрезка принимаем конец текущего отрезка. Если есть пересечение переходим к п. 14.

13. Если начальная точка текущего отрезка из Р] > соответствующая индексу п\ совпадает с первой найденной точкой общей границы, то внешний контур найден и переходим к п. 19 . В Противном случае переходим к п.11.

14. Используя, D1 ищем все точки пересечения с текущим отрезком. Из всех точек пересечения выбираем ближайшую к началу отрезка, но не совпадающую с началом отрезка. (Примечание текущий отрезок может составлять только часть текущего ребра, поэтому часть точек пересечения с ребром может не являться точками пересечения с текущим отрезком).

15. Если ребро из Р2 пересекающее текущий отрезок Р{ имеет внешнюю или лежащую на границе точку, то за текущий отрезок принимается отрезок от точки пересечения до внешней (граничной) точки, а текущими индексами для ребра из Р2 становятся соответственные индексы к\ и *2, которые берутся из структуры DI. Заносим найденную точку пересечения в итоговый вектор границ объединенного полигона. Если конец ребра из Р2 пересекающее текущую сторону Рх оканчивается во внутренней точке, то за текущий отрезок принимается отрезок от точки пересечения до точки соответствующей концу текущего отрезка из Л и переходим к п. 14 .

16. Найденный текущий отрезок из Р2 проверяется на пересечение с ребрами Р} (используется структура D2 ) если пересечений нет, то концевая точка заносится в результирующий

массив и помечается как использованная. Устанавливается новое значение текущих индексов к\~к2. Вычисляем к2 ~ к\ +1, если значение к2 > к -1, то полагаем его равным 0.

17. Используя, 02 ищем все точки пересечения ребер Г\ с текущим отрезком. Из всех точек пересечения выбираем ближайшую к началу отрезка, ко не совпадающую с началом отрезка. (Примечание текущий отрезок может составлять только часть текущего ребра, поэтому часть точек пересечения с ребром может не являться точками пересечения с текущим отрезком).

) 8. Если ребро из Р] пересекающее текущий отрезок из Р2 имеет внешнюю или лежащую на границе точку, то за текущий отрезок принимается отрезок от точки пересечения до внешней (граничной) точки, а текущими индексами для ребра из Рх становятся соответственные индексы п\ и п2 , которые берутся из структуры П2 (для проверки на завершение проверяется условие совпадения начальной точки объединенного контура с текущей начальной точкой отрезка, если это условие выполняется, то переход к п. 19). Заносим найденную точку пересечения в итоговый вектор границ объединенного полигона. Если конец ребра из Рх пересекающее текущую сторону Р2 оканчивается во внутренней точке, то за текущий отрезок принимается отрезок от точки пересечения до точки соответствующей концу текущего отрезка из Р2 и переходим к п. 17 .

19. Проводится операция по устранению лишних точек лежащих на ребрах объединенного полигона.

20. Проводится операция по циклической перестановке результирующего вектора с целью выхода на самую крайнюю левую нижнюю точку. (точка соответствует условиям обхода полигона).

21. Проверяется все ли внешние точки полигонов использованы, если таковые имеются, то это означает, что при сложении полигонов были образованы многосвязанные области. Мы повторяем все операции по созданию нового контура по приведенному алгоритму используя только те внешние точки, которые ранее не принимали участие в расчетах. Число связанных областей будут определяться числом циклов, поиска дополнительных контуров, пока весь список внешних точек не будет использован.

Заметим, что приведенный алгоритм позволяет последовательно проводить сложение нескольких произвольных контуров. Подводя итоги, можно сказать, что сложность алгоритма пропорциональна произведению числа узлов обеих полигонов, т.е. условно алгоритм относится к классу ()(пк).

. ЛИТЕРАТУРА -V .; ..  '

1. Смолин В. А. Сложение сопряженных или пересекающихся многоугольников. // В сб. Материалы н-т конференции Вологдинские чтения.- Владивосток, изд-во ДВТГУ, 2005. -

2. Смолин В.А. Принадлежность точки произвольному многоугольнику. // В сб. Материалы н-т конференции Вологдинские чтения.- Владивосток, изд-во ДВТГУ, 2005. - с. 92-94.

: А.В.Зиньков, С.А.Шорохова, Е.Б. Волынец

НЕКОТОРЫЕ РЕЗУЛЬТАТЫ ПОЛЕВЫХ ИССЛЕДОВАНИЙ ИМАЛИНОВСКОГО ФЛОРИСТИЧЕСКОГО КОМПЛЕКСА

Ималиновский флористический комплекс нижнего нория верхнего триаса установлен в разрезе на правобережье среднего течения р. Партизанская у с.Водопадное, где флороносные слои переслаиваются с морскими отложениями, включающими двустворки нижнего нория. Здесь у ж.д. ст. Водопадная развита толща алевропесчаников с остатками растений и двустворчатых моллюсков, свидетельствующих о прибрежно-морских условиях осадконакопления. Ранее эта толща относилась к ястребовской свите верхней Перми. Однако находки фаунисгических остатков позволили отнести данные отложения к нижненорийскому подъярусу верхнего триаса.