merge.h

Go to the documentation of this file.

#ifndef TATOOINE_GEOMETRY_DETAIL_LINE_MERGE_H
#define TATOOINE_GEOMETRY_DETAIL_LINE_MERGE_H
//==============================================================================
#include <tatooine/line.h>
 
#include <vector>
//==============================================================================
namespace tatooine::detail::line {
//==============================================================================
enum class line_connection : std::uint8_t {
  no_connection             = 0,
  front_common_common_back  = 1,
  common_back_common_back   = 2,
  common_back_front_common  = 4,
  front_common_front_common = 8,
};
//==============================================================================
template <typename Real, std::size_t N>
auto determine_line_connection_cases(tatooine::line<Real, N> const &line0,
                                     tatooine::line<Real, N> const &line1,
                                     floating_point auto const      eps) {
  auto connection = line_connection::no_connection;
  if (approx_equal(line0.back_vertex(), line1.back_vertex(), eps)) {
    connection =
        static_cast<std::uint8_t>(connection) |
        static_cast<std::uint8_t>(line_connection::front_common_front_common);
  }
  if (approx_equal(line0.front_vertex(), line1.front_vertex(), eps)) {
    connection =
        static_cast<std::uint8_t>(connection) |
        static_cast<std::uint8_t>(line_connection::common_back_common_back);
  }
  if (approx_equal(line0.front_vertex(), line1.back_vertex(), eps)) {
    connection =
        static_cast<std::uint8_t>(connection) |
        static_cast<std::uint8_t>(line_connection::common_back_front_common);
  }
  if (approx_equal(line0.back_vertex(), line1.front_vertex(), eps)) {
    connection =
        static_cast<std::uint8_t>(connection) |
        static_cast<std::uint8_t>(line_connection::front_common_common_back);
  }
  return connection;
}
//------------------------------------------------------------------------------
template <typename Real, std::size_t N>
auto determine_any_line_connection(tatooine::line<Real, N> const &line0,
                                   tatooine::line<Real, N> const &line1,
                                   floating_point auto const      eps) {
  if (line0.empty() || line1.empty()) {
    return line_connection::no_connection;
  }
  if (approx_equal(line0.back_vertex(), line1.front_vertex(), eps)) {
    return line_connection::front_common_common_back;
  }
  if (approx_equal(line0.front_vertex(), line1.front_vertex(), eps)) {
    return line_connection::common_back_common_back;
  }
  if (approx_equal(line0.front_vertex(), line1.back_vertex(), eps)) {
    return line_connection::common_back_front_common;
  }
  if (approx_equal(line0.back_vertex(), line1.back_vertex(), eps)) {
    return line_connection::front_common_front_common;
  }
  return line_connection::no_connection;
}
//------------------------------------------------------------------------------
template <typename Real, std::size_t N>
auto connect_lines_if_possible(tatooine::line<Real, N> &line0,
                               tatooine::line<Real, N> &line1,
                               line_connection const    conn) -> bool {
  using std::ranges::copy;
  using std::ranges::subrange;
  using std::views::reverse;
 
  auto &data0     = line0.vertices().data_container();
  auto  data0_rev = data0 | reverse;
 
  switch (conn) {
    case line_connection::front_common_common_back: {
      auto line0_without_common_vertex =
          subrange{next(begin(data0_rev)), end(data0_rev)};
      copy(line0_without_common_vertex, std::front_inserter(line1));
      line0.clear();
      return true;
    }
    case line_connection::common_back_common_back: {
      auto line0_without_common_vertex =
          subrange{next(begin(data0)), end(data0)};
      copy(line0_without_common_vertex, std::front_inserter(line1));
      line0.clear();
      return true;
    }
    case line_connection::common_back_front_common: {
      auto line0_without_common_vertex =
          subrange{next(begin(data0)), end(data0)};
      copy(line0_without_common_vertex, std::back_inserter(line1));
      line0.clear();
      return true;
    }
    case line_connection::front_common_front_common: {
      auto line0_without_common_vertex =
          subrange{next(begin(data0_rev)), end(data0_rev)};
      copy(line0_without_common_vertex, std::back_inserter(line1));
      line0.clear();
      return true;
    }
    case line_connection::no_connection:
    default:
      return false;
  }
}
//------------------------------------------------------------------------------
template <floating_point Eps = real_number>
auto connect_lines_if_possible(std::forward_iterator auto line0,
                               std::forward_iterator auto line1,
                               line_connection const      conn) -> bool {
  using std::ranges::copy;
  using std::ranges::subrange;
  using std::views::reverse;
  if (line0 == line1 || line0->empty() || line1->empty()) {
    return false;
  }
 
  return connect_lines_if_possible(*line0, *line1, conn);
}
//------------------------------------------------------------------------------
auto connect_lines_if_possible(std::forward_iterator auto line0,
                               std::forward_iterator auto line1,
                               floating_point auto const  eps) {
  return connect_lines_if_possible(
      line0, line1, determine_any_line_connection(*line0, *line1, eps));
}
//------------------------------------------------------------------------------
template <typename Real, std::size_t N>
auto connect_lines_if_possible(tatooine::line<Real, N>  &line0,
                               tatooine::line<Real, N>  &line1,
                               floating_point auto const eps) {
  return connect_lines_if_possible(
      line0, line1, determine_any_line_connection(line0, line1, eps));
}
//------------------------------------------------------------------------------
template <range_of_lines Lines, floating_point Eps = real_number>
auto connect_lines_if_possible(Lines &lines, Eps const eps) -> void {
  for (auto line0 = begin(lines); line0 != end(lines); ++line0) {
    for (auto line1 = begin(lines); line1 != end(lines); ++line1) {
      connect_lines_if_possible(line0, line1, eps);
    }
  }
  auto const is_empty                 = [](auto const &l) { return l.empty(); };
  auto const [empty_begin, empty_end] = std::ranges::remove_if(lines, is_empty);
  lines.erase(empty_begin, empty_end);
}
//==============================================================================
}  // namespace tatooine::detail::line
//==============================================================================
namespace tatooine {
//==============================================================================
template <range_of_lines Lines, floating_point Eps = real_number>
auto merge(Lines const &unmerged_lines, Eps const eps = 1e-13) {
  using line_t      = std::ranges::range_value_t<Lines>;
  auto merged_lines = std::vector<std::vector<line_t>>(unmerged_lines.size());
 
  auto unmerged_it = begin(unmerged_lines);
  for (auto &merged_line : merged_lines) {
    merged_line.push_back({*unmerged_it});
    ++unmerged_it;
  }
 
  auto num_merge_steps =
      static_cast<std::size_t>(ceil(log2(unmerged_lines.size())));
 
  for (std::size_t i = 0; i < num_merge_steps; i++) {
    std::size_t offset = tatooine::pow(std::size_t(2), i);
 
#pragma omp parallel for
    for (std::size_t j = 0; j < unmerged_lines.size(); j += offset * 2) {
      auto left  = j;
      auto right = j + offset;
      if (right < unmerged_lines.size()) {
        // move lines from right to left
        merged_lines[left].reserve(size(merged_lines[left]) +
                                   size(merged_lines[right]));
        std::ranges::move(merged_lines[right],
                          std::back_inserter(merged_lines[left]));
        merged_lines[right].clear();
        merged_lines[right].shrink_to_fit();
        // merge lines
        detail::line::connect_lines_if_possible(merged_lines[left], eps);
      }
    }
  }
  return merged_lines.front();
}
//------------------------------------------------------------------------------
template <range_of_lines Lines, floating_point Eps = real_number,
          execution_policy_tag ExecutionPolicy>
auto merge(Lines &lines, std::ranges::range_value_t<Lines> line_to_merge,
           ExecutionPolicy const tag, Eps const eps = 1e-13) -> auto & {
  using namespace detail::line;
  auto inserted = std::atomic_bool{false};
  auto mutex    = std::mutex{};
  auto connections =
      std::vector<std::pair<std::ranges::iterator_t<Lines>, line_connection>>{};
  for_loop(
      [&](auto line_it) {
        auto connection =
            determine_any_line_connection(line_to_merge, *line_it, eps);
        if (connection != line_connection::no_connection) {
          if constexpr (is_same<ExecutionPolicy,
                                execution_policy::parallel_t>) {
            auto lock = std::lock_guard{mutex};
            connections.emplace_back(line_it, connection);
          } else {
            connections.emplace_back(line_it, connection);
          }
        }
      },
      lines, tag);
  if (connections.empty()) {
    lines.push_back(line_to_merge);
    return lines;
  }
  if (connections.size() == 1) {
    auto const [line_it, connection] = connections.front();
    connect_lines_if_possible(line_to_merge, *line_it, connection);
    return lines;
  }
  if (connections.size() == 2) {
    auto const [line0_it, connection0] = connections[0];
    auto const [line1_it, connection1] = connections[1];
    connect_lines_if_possible(line_to_merge, *line0_it, connection0);
    if (connect_lines_if_possible(*line1_it, *line0_it, eps)) {
      lines.erase(line1_it);
    }
    return lines;
  }
 
  return lines;
}
//==============================================================================
}  // namespace tatooine
//==============================================================================
#endif