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

Question

[Вячеслав Кузнецов]

Добрый день!
Имеется следующая задача:
В программе отображается область (по координатам), то есть даны точки границ ее, и можно отрисовать, выглядит примерно так:

Эту область нужно покрыть прямыми так, например так:

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

Работаю в Windows Forms, C#. Буду рад любой помощи!

Comments

[res2001]

С какой плоскостью вы пересекаете прямые? И куда вы их поворачиваете?

[Вячеслав Кузнецов]

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

[heartdevil]

Я не математик, просто интересно. А как вы считаете пересечение с покрытием прямой? Вот вы сто прямых нарисовали, и для каждой прямой посчитали в каких точках она пересекает полигон, потом все эти пересечения для ста прямых суммируете и вычисляете минимум для этих же ста но повернутых на угол?

[Вячеслав Кузнецов]

heartdevil, я же говорил, что пишу костыли)
на данный момент это выглядит так:
1)я рисую прямые от минимальной точки полигона до максимальной
2)считаю сколько раз они пересекли полигон (это число важно для меня)
3)нужно как-то повернуть прямые и посчитать сколько этот вариант будет пересекать
4)после всех вариантов выбрать оптимальный
Я, на самом деле, не говорю, что это правльное решение, просто я вроде и книги посмотрел по выч. геометрии, алгоритмах, не нашел решение данной задачи. Ну и так как я студент, не исключаю, что я просто безграмотный, и не могу правильно написать запрос в гугле :)

Answer 1

[tsarevfs]

Предлагаю вращать не прямые, а фигуру. Для этого достаточно домножить координаты каждой вершины на матрицу поворота. Ну, а прямые можно взять горизонтальные (y=c1, y=c2, ...). Так будет значительно проще искать пересечения сторон с этими прямыми.

Comments

[Вячеслав Кузнецов]

Идея крутая, а при повороте фигуры можно же просто пользоваться формулами:
х = х * cos(a) - y * sin(a)
y = x * sin(a) + y * cos(a)
Почему про матрицу разговор?

[Ocelot]

Это оно и есть. Матрица поворота состоит из этих синусов и косинусов:
| cos(a) -sin(a) |
| sin(a) cos(a) |

[tsarevfs]

Учтите, что бывают пересечения разных видов.
*пересечение через сторону
*пересечение через вершину
*касание стороны
*касание вершины

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

Answer 2

[Griboks]

Уравнение прямой y=kx+b. За поворот отвечает k. k=tg A, где A - угол места.

Answer 3

[Павло Пономаренко]

Как альтернатива - отрисовать линии по BoundingBox, а ограничить их при помощи Clipping:
https://docs.microsoft.com/en-us/dotnet/framework/...

Answer 4

[Александр Скуснов]

Зачем рисовать прямые? Сделайте закраску кистью (brush).

Comments

[Вячеслав Кузнецов]

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

Answer 5

[Руслан .]

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

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

Answer 6

[Сергей Соколов]

Два параметра можно варьировать: угол решетки и её фазу, смещение линий параллельно самим себе в рамках одного шага решётки.

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

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

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

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

Расстояние между параллельными прямыми = |C₁ - C₂| / sqrt( A² + B²)

Расстояние от точки (X,Y) до прямой |AX + BY + C| / sqrt(A² + B²)