S
S
Svyatoslav Khusamov2015-11-23 15:45:02
Algorithms
Svyatoslav Khusamov, 2015-11-23 15:45:02

How to organize the storage structure of polygon divisors data?

The task is this. There is a polygon (I'll call the original one). The coordinates of its nodes are absolute values ​​relative to the coordinate plane.
You need to divide the polygon by divisors. The coordinates of the divisors are relative. For example, it could be a percentage or a distance from the first point of the polygon. As long as it doesn't matter. But definitely not relative to the coordinate plane.
Dividers during division divide the polygon into subpolygons - Openings. Opening coordinates must be calculated based on divisors.
b28d759d13e84063ae258f915c431706.PNG
I know how to store this structure as a tree. For example, a divider divides an opening into two openings, each opening can be divided by another divider into openings, and so on, as a result, an opening or divider refers to a parent opening, each opening can have two child openings and one divider. But in such a structure, the problem of deleting dividers is that you can delete a divider if there are no child openings. If so, then the operation is undefined.
I want a different structure. Where everything is on the same level.
Question - how to organize such a structure in the computer's memory?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
M
Mrrl, 2015-11-23
@Mrl

You need to divide the polygon by divisors. The coordinates of the divisors are relative. For example, it could be a percentage or a distance from the first point of the polygon. As long as it doesn't matter.

Actually, this is very important.
If by "divider" you mean a segment, each end of which is defined as a point that divides some already constructed segment in a certain (known and unchanged) ratio, then the problem can be solved.
On the example of your 5-gon. Let its vertices be ABCDE given clockwise, AB the top side. Let the first (leftmost) divider be PQ, point P divides segment AB in the ratio 3:7, point Q divides segment DE in ratio 6:4. Point R (the left end of the internal divider) also divides the segment PQ in a ratio of 6:4.
Let's write:
P = 0.7*A + 0.3*B
Q = 0.4*D + 0.6*E
R = 0.4*P + 0.6*Q
Here, the addition and multiplication of points is performed coordinate-wise, and if the point K divides the segment MN with respect to m:n, then we write K=M*(n/(m+n))+N*(m/(m+n)).
Substituting P and Q into the last equation, we get R=0.28*A+0.12*B+0.24*D+0.36*E - the expression of the coordinates of this point in terms of the coordinates of the vertices of the original pentagon. Thus, for each point, it is enough to store n numbers - the coefficients in this expression.
With other definitions of point coordinates, you will have to store and process the entire calculation tree, it will not work to keep the data at the same level.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question