В дальнейшем я предполагаю, что треугольники с их базовой линией внизу.Я также предполагаю, что все треугольники таковы, что верхний угол находится выше базовой линии (т.е. если вы идете прямо вниз от верхнего угла, вы попадаете внутрь треугольника, а не снаружи).Однако я не , предполагая, что разрешены только симметричные треугольники.
На самом деле слияние треугольников даст горизонт, где просто точки соединены линиями.таким образом, представление горизонта треугольника могло быть просто упорядоченным списком точек (x_i, y_i) с ограничением, что y_0 = 0 и y_N = 0, где N - индекс последней точки.Один треугольник будет представлен трехэлементным списком (x_0, 0), (x_1, h), (x2,0), где x_0 и x_2 - левая и правая конечная точка (две точки, где треугольник достигает 0)x_1 задает горизонтальное положение верхнего угла, а h - высоту.
Объединение двух линий горизонта может, например, быть сделано следующим образом:
Шаг 1: Для каждого отрезка линии(x_i, y_i) - (x_ {i + 1}, y_ {i + 1}) от горизонта 1 и каждого отрезка линии (x_j, y_j) - (x_ {j + 1}, y_ {j + 1}) рассчитать, пересекаются ли они, и если да, то где (это означает решение простой системы из двух линейных уравнений).Соберите точки пересечения в новый список, пересечения.Итак, теперь у вас есть три списка точек: skyline1, skyline2 и пересечения.Поскольку все пересечения будут частью горизонта, используйте его в качестве основы для нового горизонта.(особый случай, когда обе линии горизонта совпадают на некотором интервале, но в таких интервалах объединенная линия горизонта в любом случае совпадает с каждой отдельной, поэтому просто используйте начальную и конечную точки этих интервалов в качестве точек пересечения)
Теперь для каждой пары точек пересечения (а также слева от первого пересечения и справа от последнего пересечения) всегда будет ровно одна линия горизонта, которая находится над другой (если они не согласны, но тогда не имеет значения, какой вы выберете).Добавьте точки в интервале от этого горизонта до вашего объединенного горизонта.Вы можете найти более крупную, просто выбрав произвольную точку одной линии горизонта (за исключением случаев, когда точка пересечения также является точкой горизонта, которую не следует выбирать), и определите высоту другой линии горизонта по ее значению х (если другаягоризонт также имеет точку с тем же значением x, это простое сравнение значения y, в противном случае вам нужно интерполировать значения y предыдущей и последующих точек.
После этого вы должны получитьправильный комбинированный горизонт.