khusamov
@khusamov
ReactJS, NodeJS, TypeScript, Sencha ExtJS

Как организовать структуру хранения данных делителей многоугольника?

Задача такая. Есть многоугольник (назову исходный). Координаты его узлов это абсолютные значения относительно координатной плоскости.

Нужно многоугольник делить делителями. Координаты делителей относительные. Например это может быть процент или расстояние от первой точки многоугольника. Пока это неважно. Но точно не относительно координатной плоскости.

Делители при делении делят многоугольник на подмногоугольники - Проемы. Координаты проемов должны быть вычисляемыми на основании делителей.

b28d759d13e84063ae258f915c431706.PNG

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

Хочу другую структуру. Где все на одном уровне.

Вопрос - как организовать такую структуру в памяти компа?
  • Вопрос задан
  • 203 просмотра
Пригласить эксперта
Ответы на вопрос 1
Mrrl
@Mrrl
Заводчик кардиганов
Нужно многоугольник делить делителями. Координаты делителей относительные. Например это может быть процент или расстояние от первой точки многоугольника. Пока это неважно.

На самом деле, это очень важно.
Если под "делителем" вы имеете в виду отрезок, каждый конец которого определяется как точка, делящая какой-то уже построенный отрезок в определённом (известном и неизменном) отношении, то задачу решить можно.
На примере вашего 5-угольника. Пусть его вершины - ABCDE, заданные по часовой стрелке, AB - верхняя сторона. Пусть первый (самый левый) делитель PQ, точка P делит отрезок AB в отношении 3:7, точка Q делит отрезок DE в отношении 6:4. Точка R (левый конец внутреннего делителя) делит отрезок PQ тоже в отношении 6:4.
Запишем:
P = 0.7*A + 0.3*B
Q = 0.4*D + 0.6*E
R = 0.4*P + 0.6*Q
Здесь сложение и умножение точек выполняется покоординатно, и если точка K делит отрезок MN в отношении m:n, то мы пишем K=M*(n/(m+n))+N*(m/(m+n)).
Подставив P и Q в последнее уравнение, получим R=0.28*A+0.12*B+0.24*D+0.36*E - выражение координат этой точки через координаты вершин исходного пятиугольника. Таким образом, для каждой точки достаточно хранить n чисел - коэффициенты в этом выражении.

При других определениях координат точек придётся хранить и обрабатывать всё дерево вычислений, там держать данные на одном уровне не получится.
Ответ написан
Ваш ответ на вопрос

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

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