Выпуклая полигонизация спрайта

Question

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

Мой последний вопрос будет: знаете ли вы способ сделать это, который будет более легким, чем мой или способ заставить мою работу?

Теперь вот детали того, что я сейчас сделал:

Я реализовал алгоритм разделения осей, чтобы обнаружить пересечения между моими полигонами.

Для создания полигонов я сначала реализовал алгоритм квадрата, чтобы получить контур внутренней фигуры, а затем преобразовал его в сегменты.

Теперь у меня есть многоугольник, но он может быть вогнутым, поэтому мне нужно найти способ разбить его на несколько выпуклых многоугольников.

Я попытался реализовать алгоритм обрезания ушей, но в некоторых случаях это не удается. Также я где-то читал, что это не работает, когда само полигон пересекается.

Ниже некоторые плохие визуальные эффекты моей проблемы:

Кроме того, ниже приведен скелет, который я сгенерировал для этого спрайта, извините, это ничья, но это просто для того, чтобы дать вам больше визуальной информации:

Как вы видите, я также "обрезаю" углы (не знаю, как это сказать).

Итак, должен ли алгоритм срезания ушей работать на этом многоугольнике, и проблема исходит из моей реализации или он не должен работать?

Также моей следующей целью было объединить треугольники, пока они еще образовывали выпуклый многоугольник. Я также ищу более простой способ сделать это, если вы знаете один.

Заранее спасибо.

EDIT-1

Код моей реализации триангуляции:

#include "Triangulation.hh"

bool Triangulation::isConvex(const Position &a, const Position &b,
                             const Position &c) const {
  float crossp = (c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x);
  return (crossp >= 0 ? true : false);
}

bool Triangulation::inTriangle(const Position &a, const Position &b,
                               const Position &c, const Position &x) const {
  std::array<float, 3> barCoef = {0, 0, 0};

  barCoef[0] = ((b.y - c.y) * (x.x - c.x) + (c.x - b.x) * (x.y - c.y)) /
               (((b.y - c.y) * (a.x - c.x) + (c.x - b.x) * (a.y - c.y)));
  barCoef[1] = ((c.y - a.y) * (x.x - c.x) + (a.x - c.x) * (x.y - c.y)) /
               (((b.y - c.y) * (a.x - c.x) + (c.x - b.x) * (a.y - c.y)));
  barCoef[2] = 1.f - barCoef[0] - barCoef[1];

  for (float coef : barCoef) {
    if (coef >= 1 || coef <= 0)
      return false;
  }
  return true;
}

std::pair<bool, std::array<Position, 3>>
Triangulation::getEar(std::vector<Position> &polygon) const {
  int size = polygon.size();
  bool triTest = false;
  std::array<Position, 3> triangle;

  if (size < 3)
    return {false, triangle};
  else if (size == 3) {
    triangle = {polygon[0], polygon[1], polygon[2]};
    polygon.clear();
    return {true, triangle};
  } else {
    for (int i = 0; i < size; ++i) {
      triTest = false;
      triangle[0] = polygon[(i + size - 1) % size];
      triangle[1] = polygon[i];
      triangle[2] = polygon[(i + 1) % size];
      if (this->isConvex(triangle[0], triangle[1], triangle[2])) {
        for (const Position &point : polygon) {
          auto it = std::find(triangle.begin(), triangle.end(), point);

          if (it != triangle.end())
            continue;
          if (this->inTriangle(triangle[0], triangle[1], triangle[2], point)) {
            triTest = true;
            break;
          }
        }
        if (triTest == false) {
          polygon.erase(polygon.begin() + i);
          return {true, triangle};
        }
      }
    }
  }
  return {false, {}};
}

Мои точки расположены в порядке против часовой стрелки, проблема связана с методом isConvex, где для моего первого изображения он вернет true.

РЕДАКТИРОВАТЬ 2

Спасибо @svs за заметки, я обновил код в EDIT 1, чтобы другие увидели, ниже мой плохой рисунок полученного результата:

Answer 1

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

• убедитесь, что вы вводите вершины многоугольника согласованным образом - по часовой стрелке или против часовой стрелки. Например, если у вас есть квадрат с вершинами (0, 0), (1, 1), (1, 0), (0, 1) Вы должны ввести многоугольник как вершины (0, 0), (0, 1), (1, 1), (1, 0) если вы используете способ против часовой стрелки

• проверьте свой алгоритм для проверки, является ли вершина снова ухом. Если вы используете по часовой стрелке вершину v[i]=(x[i], y[i]) это ухо, если подписанная область вершин v[i-1]=(x[i-1], y[i-1])), v[i], v[i+1]=(x[i+1], y[i+1])) положительный, и нет точки многоугольника внутри v[i-1], v[i], v[i+1], Вот формула для подписанной области.

Видя ваш код, вы должны переместить оператор удаления вершины за пределы вершинного цикла многоугольника. Пседокод алгоритма:

for each vertex v[i] of the polygon:
    if v[i] is an ear:
        if there is no polygon vertex in triangle v[i-1], v[i], v[i+1]:
            delete vertex v[i] from the polygon

Проблема в том, что вы удаляете вершину, когда проверяете, существует ли вершина многоугольника в треугольнике. Обновите свой код до:

if (this->isConvex(triangle[0], triangle[1], triangle[2])) {
    for (const Position &point : polygon) {
        auto it = std::find(triangle.begin(), triangle.end(), point);

        if (it == triangle.end())
            continue;
        if (this->inTriangle(triangle[0], triangle[1], triangle[2], point)) {
            triTest = true;
            break;
        }
    }
    if (triTest == false) {
        polygon.erase(polygon.begin() + i);
        return {true, triangle};
    }
}