Товарищи!
Кто подскажет алгоритм пропорциональной разбивки плоского многоугольника (надеюсь, ясно выразился)?
Образец необходимого результата показан на картинке ниже.
Буду благодарен. Уже все сроки выходят , а сделать очень надо .
Здравствуйте, Lukashov, Вы писали:
L>Товарищи! L>Кто подскажет алгоритм пропорциональной разбивки плоского многоугольника (надеюсь, ясно выразился)? L>Образец необходимого результата показан на картинке ниже. L>Буду благодарен. Уже все сроки выходят , а сделать очень надо .
Лучше делай триангуляцию Делоне, а потом просто лишние рёбра удаляй
Здравствуйте, Lukashov, Вы писали:
L>Товарищи! L>Кто подскажет алгоритм пропорциональной разбивки плоского многоугольника (надеюсь, ясно выразился)? L>Образец необходимого результата показан на картинке ниже. L>Буду благодарен. Уже все сроки выходят , а сделать очень надо .
L> L>
А он всегда как скомканный прямоугольник и разбивается на четырехуголники? И как он задан? Непонятно.
Если он все-таки бывший прямоугольник, то приходит в голову такая мысль:
Разбей исходный прямоугольник прямоугольной сеткой. Привяжи каждый узел к четырем ( понятно каким ) точкам на границе с коэффициентами:
а) пропорциональными соотв. размер прямоугольника минус расстояние до точки
б) пропорциональными для вертикальных точек — расстоянию до ближайшей горизонтальной, а для горизонтальных — наоборот...
Тут есть некая закавыка, но времени ее выковыривать нет... Может попозже чего еще соображу...
Здравствуйте, Рома Мик, Вы писали:
РМ>Здравствуйте, Lukashov, Вы писали:
L>>Товарищи! L>>Кто подскажет алгоритм пропорциональной разбивки плоского многоугольника (надеюсь, ясно выразился)? L>>Образец необходимого результата показан на картинке ниже. L>>Буду благодарен. Уже все сроки выходят , а сделать очень надо .
L>> L>>
РМ>А он всегда как скомканный прямоугольник и разбивается на четырехуголники? И как он задан? Непонятно.
РМ>Если он все-таки бывший прямоугольник, то приходит в голову такая мысль: РМ>Разбей исходный прямоугольник прямоугольной сеткой. Привяжи каждый узел к четырем ( понятно каким ) точкам на границе с коэффициентами: РМ>а) пропорциональными соотв. размер прямоугольника минус расстояние до точки РМ>б) пропорциональными для вертикальных точек — расстоянию до ближайшей горизонтальной, а для горизонтальных — наоборот...
РМ>Тут есть некая закавыка, но времени ее выковыривать нет... Может попозже чего еще соображу...
Ну вот
Не четыре точки, а все точки на границе. Коэффициенты должны быть пропорциональны не расстояниям, а горизонтальной и вертикальной состовляющей расстояния для горизонтального и вертикального смещения соответственно.
Здравствуйте, Рома Мик, Вы писали:
РМ>>А он всегда как скомканный прямоугольник и разбивается на четырехуголники? И как он задан?
Прямоугольником фигура является не всегда, но все ребра этого многоугольника группируются в именно четыре последовательных стороны (т.е. смежными являются стороны (1,2), (2,3), (3,4) и (4,1)). Поэтому эту фигуру можно назвать "четырехугольник со сторонами в виде ломаных ". Следовательно на двух противоположных сторонах (1,3) и (2,4) вседа одинаковое количество точек разбиения.
РМ>>Коэффициенты должны быть пропорциональны не расстояниям, а горизонтальной и вертикальной состовляющей расстояния для горизонтального и вертикального смещения соответственно.
А если многоугольник еще и повёрнут?
Совсем не обязательно, что ребра одной стороны лежат "примерно" параллельно координатным осям. Но то, что прямоугольник не самопересекающийся — это точно .
Здравствуйте, Lukashov, Вы писали:
L>Товарищи! L>Кто подскажет алгоритм пропорциональной разбивки плоского многоугольника (надеюсь, ясно выразился)? L>Образец необходимого результата показан на картинке ниже. L>Буду благодарен. Уже все сроки выходят , а сделать очень надо .
L> L>
Элементарно Ватсон.
Возьмем элементарный квадрат (например -1..-1, -1..1) в системе координат (x,y)
Его делишь на четырехугольники как хочешь, равномерно, или по другому если надо. Т.е. получаешь набор координат точек (x, y) в некоторой канонической системе координат.
Теперь задача: Преобразовать точку с координатами (x,y) из канонической системы координат в точку (пусть будет X, Y) в исходной системе координат.
Дальше простейшие формулы из вузовского курса математики.
Здравствуйте, Lukashov, Вы писали:
L>Здравствуйте, Рома Мик, Вы писали:
РМ>>>А он всегда как скомканный прямоугольник и разбивается на четырехуголники? И как он задан?
L>Прямоугольником фигура является не всегда, но все ребра этого многоугольника группируются в именно четыре последовательных стороны (т.е. смежными являются стороны (1,2), (2,3), (3,4) и (4,1)). Поэтому эту фигуру можно назвать "четырехугольник со сторонами в виде ломаных ". Следовательно на двух противоположных сторонах (1,3) и (2,4) вседа одинаковое количество точек разбиения.
Это я и имел ввиду: "скомканный прямоугольник".
РМ>>>Коэффициенты должны быть пропорциональны не расстояниям, а горизонтальной и вертикальной состовляющей расстояния для горизонтального и вертикального смещения соответственно.
Это я опять наврал в спешке. Куда спешил?..
L>А если многоугольник еще и повёрнут?
А это нам все равно. Что значит повернут? Точки подальше уехали...
L>Совсем не обязательно, что ребра одной стороны лежат "примерно" параллельно координатным осям. Но то, что прямоугольник не самопересекающийся — это точно .
А даже если и самопересекающийся, то что?
Идея-то какая: был прямоугольник, потом все пространство взяли и как-то преобразовали так, что он стал таким какой у вас в задаче. Итого: надо найти преобразование пространства такое, что точки на границе прямоугольника переедут в точки на границе заданной фигуры. Останется применить преобразование к точкам сетки. ( Очевидно, что такое преобразование не единственное. Тут можно подумать и поэкспериментовать, какое лучше. )
Какое преобразование? Предположим, что это преобразование есть перемещение на величину равную сумме перемещений граничных точек умноженных на некие коэффициенты.
Какие коэффициенты? Такие, чтобы сами граничные точки уехали куда надо. Самое простое: каждый коэффициент обратно пропорционален расстоянию до точки, а сумма коэффициентов 1. Т.е.
A = 0;
for(i = 0; i < n; ++i)
{
c[i] = 1 / l[i];
A += c[i];
}
dx = 0;
dy = 0;
for(i = 0; i < n; ++i)
{
dx += dx[i] * c[i] / A;
dy += dy[i] * c[i] / A;
}
А исх. прямоугольник может быть любой, хоть квадрат (0, 0) — (1, 1).
Здравствуйте, Lukashov, Вы писали:
L>Товарищи! L>Кто подскажет алгоритм пропорциональной разбивки плоского многоугольника (надеюсь, ясно выразился)? L>Образец необходимого результата показан на картинке ниже. L>Буду благодарен. Уже все сроки выходят , а сделать очень надо .
Рискну высказать теоретическую идею без вывода конкретных формул и без проверки:
Пренбрежем "неактивными" точками по сторонам, т.е. сведем задачу к следующей:
Будем оперировать векторами.
Предположим. что искомый вектор X является линейной комбинацией векторов A, B, C, D, K, L, M, N.
Итого имеем 8 неизвестных коффициентов для каждого вектора.
Теперь потребуем, чтобы, когда N и L равны, соответсвенно, A и B, то X был равен K. И так для каждой стороны.
С учетом того, что вектор задается двумя координатами, имеем систему 8 линейных уравнений относительно 8 неизвестных. Решаем ее и находим X.
Если положить за начало координат точку A, то получится 6 уравнений, которые может быть можно решить аналитически.
Единственно боюсь, что уравнения могут оказаться линейно зависимыми .
Здравствуйте все,
кто ответил (или попытался ответить ) на мой вопрос!
Сделал я разбивку. Спасибо Роме Мик за подсказку с единичным прямоугольником . После неё я сразу допёр до решения. Нужно признать, что задачка-то элементарная оказалось. Действительно, какая разница, чего разбивать-то: крадрат 1х1 (или другой) или фигуру, представленную как "смятый" квадрат.
Количество точек разбиения известно, поэтому коэффициенты тоже известны:
kx = 1/(XPointCount + 1)
ky = 1/(YPointCount + 1)
Здесь XPointCount и YPointCount — это количество только точек разбиения (т.е. точки на границе не включаются).
При разбивке прямоугольника расстояние между точками противоположной стороны всегда постоянное, его мы умножаем на соответствующий коэффициент.
А при разбивке нашей "смятой бумажки" координату нужно вычислять по расстоянию между двумя соответствующими для данной итерации точками. И всё!
Для тех, кто столкнется с этой проблемой, покажу разбивку на примере картинки (с)MichaelP.
Вот картинка:
Точек разбиения у нас одна по X (XPointCount = 1) и одна по Y (YPointCount = 1), т.е. нужно найти координаты только одной точки в середине фигуры (точки X). Для этого вычисляем расстояние по Х между точками К и М и умножаем его на kx = 1/(1+1) = 0.5, получим координату х. Затем вычисляем расстояние между точками L и N и умножаем его на ky = 1/(1+1) = 0.5, получим координату y. Всё, точка Х известна.
Если бы точек разбиения было больше, то координаты точек X[i,j] вычислялись по соответствующим точкам L[i],N[i] и K[j],M[j].
А самый прикол в том, что я подобну задачу решал уже не раз, только немного в других контекстах. А здесь чё-то вдруг застопорился. Это потому что отдыхать чаще надо , а то так и с работы выгнать могут .
Здравствуйте, Lukashov, Вы писали:
L>Здравствуйте все, L>кто ответил (или попытался ответить ) на мой вопрос!
L>Сделал я разбивку. Спасибо Роме Мик за подсказку с единичным прямоугольником . После неё я сразу допёр до решения. Нужно признать, что задачка-то элементарная оказалось. Действительно, какая разница, чего разбивать-то: крадрат 1х1 (или другой) или фигуру, представленную как "смятый" квадрат.
L>Количество точек разбиения известно, поэтому коэффициенты тоже известны: L> kx = 1/(XPointCount + 1) L> ky = 1/(YPointCount + 1) L>Здесь XPointCount и YPointCount — это количество только точек разбиения (т.е. точки на границе не включаются).
Предупреждать надо, что точки на границе через равные промежутки заданы! Не решал бы более общей задачи...
, а сделать очень надо 
.
". Следовательно на двух противоположных сторонах (1,3) и (2,4) вседа одинаковое количество точек разбиения.
.
) на мой вопрос!
. После неё я сразу допёр до решения. Нужно признать, что задачка-то элементарная оказалось. Действительно, какая разница, чего разбивать-то: крадрат 1х1 (или другой) или фигуру, представленную как "смятый" квадрат.
, а то так и с работы выгнать могут 
, в следующий раз буду формулировать задачу точнее.
