Графический фитинг PolyPath в C #

Question

Мне нужно «вписать» GraphicsPath произвольной формы в определенное пространство (почти всегда прямоугольник или круг).

В настоящее время я масштабирую GraphicsPath с использованием объекта Matrix, и масштабирование работает нормально, но проблема заключается в получении коэффициентов масштабирования.

Лучшая техника, которую я могу придумать, - это преобразование GraphicsPath в область, преобразование прямоугольника или круга в область и выполнение:

rgnShape.Intersect(rgnCircle);

, а затем проверка:

rgnShape.IsEmpty()

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

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

Answer 1

См. http://en.wikipedia.org/wiki/Smallest_circle_problem для обсуждения этой проблемы в терминах точек, а не путей, найденных Симоном.

1. Итак, сделайте это, используйте rgnShape.Intersect(rgnCircle);, чтобы проверить, сработало ли это. Если это не удалось, возьмите каждую кривую и возьмите точки, наиболее удаленные от центра круга, который вы нашли (может быть более одной такой точки для любого заданного региона).

2. Добавьте их в свой список очков, примените алгоритм. Вам не нужно начинать с нуля; вам не нужно рассматривать точки, не находящиеся на границе (то есть игнорировать точки, не входящие в «Набор Q», который был найден при первоначальном вызове алгоритма).

Обратите внимание, что это больше не является линейным, поскольку вероятность создания рекурсивных вызовов больше не равна 1 / i для i-й точки.

У этого есть одно краевое условие, которое вы должны обработать явно. В случае, если одна из кривых, найденных за пределами области, найденной во время первой итерации шага 1, является совершенно круглой и касается внешнего круга, в «наборе Q» будут бесконечные точки, и этот алгоритм потерпит неудачу с треском. Итак, после применения rgnShape.Intersect(rgnCircle); в первый раз, вы должны явно проверить любые идеально круглые кривые для этого случая. Например, если ваша фигура (}, вам следует явно проверить () (для целей данного обсуждения притвориться () кружком), если ( лежит за пределами области, найденной во время первой итерации.

Это все еще довольно плохо, но лучше, чем менять каждую кривую на точки.

Answer 2

Не понимаю, зачем вам бинарный поиск.

Как только вы получите ограничительный прямоугольник для вашей фигуры и у вас будет целевой прямоугольник, в который вы хотите вписать фигуру, вы можете сравнить два соотношения targetHeight / shapeHeight и targetWidth / shapeWidth.

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

Если целью является круг, а не прямоугольник, вы можете использовать аналогичное решение, взяв соотношение targetCircleDiameter / boundingRectangleDiagonal и использовать его в качестве коэффициента масштабирования.

Answer 3

Как насчет того, чтобы пойти по другому пути, используя простую математику? А именно, получить ограничивающую рамку / окружность пути, рассчитать предварительно определенное прямоугольное соотношение высоты / ширины, сравнить это с тем же значением BB, соответственно растянуть BB (например, если предварительно определенный рацион меньше 1, BB растягивается горизонтально и по вертикали в противном случае, чтобы соответствовать тому же соотношению), наконец, масштабировать все это до заранее определенного прямоугольного размера. Коэффициент масштабирования теперь является просто минимумом между предварительно определенной высотой, деленной на высоту BB, и предварительно определенной шириной, деленной на ширину BB. (Для ограничивающего круга нет необходимости регулировать его размер.)

Answer 4

Не можете ли вы вычислить центр графического пути и радиус?

Вы можете либо вычислить центр тяжести (среднее значение по координатам) и добавить 2-кратное стандартное отклонение - это должно дать вам около 92% вашего графика - большую часть времени это будет хорошо, но не получится, если вашграфик имеет наибольший «вес» на одном конце.

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

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

Answer 5

Вы можете использовать GetBounds для GraphicsPath и Region, а затем сравнить размеры прямоугольников, чтобы хотя бы приблизить вас.

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

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