@slavenski
Android developer

Как покрыть полигон прямыми?

Добрый день!
Имеется следующая задача:
В программе отображается область (по координатам), то есть даны точки границ ее, и можно отрисовать, выглядит примерно так:
5ace065a3824c245911707.png
Эту область нужно покрыть прямыми так, например так:
5ace06b4e70bf789479611.png
Эти прямые пересекают область в некоторых точках, и за пределами области не рисуются.
Далее нужно повернуть эти прямые, и посчитать сколько раз пересекаются прямые с областью, и так несколько раз, и из всех вариантов выбрать то покрытие, где пересечений минимальное количество.
Не могу реализовать поворот, пишу огромные костыли... :(
ПОМОГИТЕ)

Работаю в Windows Forms, C#. Буду рад любой помощи!
  • Вопрос задан
  • 505 просмотров
Решения вопроса 1
tsarevfs
@tsarevfs
C++ developer
Предлагаю вращать не прямые, а фигуру. Для этого достаточно домножить координаты каждой вершины на матрицу поворота. Ну, а прямые можно взять горизонтальные (y=c1, y=c2, ...). Так будет значительно проще искать пересечения сторон с этими прямыми.
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
Griboks
@Griboks Куратор тега C#
Уравнение прямой y=kx+b. За поворот отвечает k. k=tg A, где A - угол места.
Ответ написан
Комментировать
Как альтернатива - отрисовать линии по BoundingBox, а ограничить их при помощи Clipping:
https://docs.microsoft.com/en-us/dotnet/framework/...
Ответ написан
Комментировать
@AlexSku
не буду отвечать из-за модератора
Зачем рисовать прямые? Сделайте закраску кистью (brush).
Ответ написан
LaRN
@LaRN
Senior Developer
Не нужно рисовать сразу все прямые.
Нужно найти на указанном контуре две точки, наиболее удаленные друг от друга.
Далее рисовать линии разметки перпендикулярно линии проведенной через найденные выше две точки.
Так как точки наиболее удаленные (условно самая длинная хорда), количество линий разметки будет максимальным.

Для поиска наиболее удаленных точек, можно по координатам точек образующих контур вычислить геометрический центр масс фигуры и затем найти точки контура наиболее удаленные от нет по формуле Евклида.
Далее для каждой найденной точки строим луч из текущей точки через геометрический центр масс и ищем точку пересечения этого луча с контуром.
Исходная точка контура и найденная путем трассировки луча образуют отрезок, нужно найти и запомнить длину отрезка.
После этого имеем массив отрезков с длина, нужно выбрать самый длинный (или один из самых длинных, если есть несколько равных по длине).
Найденный отрезок и будет проходить через наиболее удаленные точки контура и перпендикулярно ему нужно строить линии разметки.
Ответ написан
Комментировать
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Два параметра можно варьировать: угол решетки и её фазу, смещение линий параллельно самим себе в рамках одного шага решётки.

При относительно сложной форме фигуры остаётся только перебор вариантов. Сначала с большим шагом, затем уменьшая шаг и уточняя.

Не совсем понятно, как задана фигура?
«даны точки границ ее» – это массив точек с небольшим шагом, т.е. контур задан пунктиром, или «углы» прямых отрезков (вся фигура составлена из множества прямых отрезков разной длины).

Алгоритм примерно такой. Пара (угол, фаза) задаёт множество прямых. Надо пройтись по контуру фигуры, считая пересечения или близость очередной точки контура к одной из прямых. Если контур задан прямыми отрезками ещё проще: для каждого отрезка посчитать число пересечений, исходя только из расстояния краевых точек от одной master-прямой. Например, расстояния 5.2 и 7.3 при шаге решетки 3. 0 не пересекает, 3 пересекает, 6 пересекает, 9 уже нет. Итого 2 пересечения.

Прямая задаётся уравнением Ax + By + C = 0 Или с угловым коэффициентом y = x(-A/B) - (C/B) Параллельные прямые отличаются значением C.

Расстояние между параллельными прямыми = |C1 - C2| / sqrt( A2 + B2)

Расстояние от точки (X,Y) до прямой |AX + BY + C| / sqrt(A2 + B2)
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы