Эффективно удалять точки с одинаковым наклоном

Question

В одном из моих приложений я имею дело с графическими объектами. Я использую библиотеку GPC с открытым исходным кодом , чтобы обрезать / объединить две фигуры. Для повышения точности я выполняю выборку (добавляя несколько точек между двумя краями) существующих фигур. Но прежде чем отобразить объединенную фигуру, мне нужно удалить все точки между двумя ребрами.

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

PointF 

Я вычисляю наклон, используя следующую функцию

  private float Slope(PointF point1, PointF point2)
  {
     return (point2.Y - point1.Y) / (point2.X - point1.X);
  }

Любой указатель на это очень поможет.

Answer 1

Какой алгоритм вы сейчас используете? Я могу думать только о прохождении всей точки и о том, чтобы каждые 3 проверяли, находится ли средняя точка на векторе (или близко к), определяемому двумя другими точками. Вам нужна математика для этой операции?

Answer 2

Хорошо .. Я нашел решение для моего вопроса. Вместо использования метода выборки, предоставленного SDK, я создал собственный метод выборки, который вставляет точку между двумя точками на фиксированном расстоянии. Это уменьшает количество точек, которые мне нужно обработать, и, в свою очередь, уменьшает использование процессора.

Answer 3

Просто чтобы прояснить, у вас есть три точки A = (a, b), C = (c, d) и E = (e, f), и вам интересно, проходит ли отрезок AE через C, и таким образом Можно ли заменить пару сегментов AC и CE на один сегмент AE?

наклон AC = (d-b) / (c-a) = наклон CE = (f-d) / (e-c)

умножив на знаменатели, вы получите (d-b) (e-c) = (f-d) (c-a)

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