I am trying to find out whether to geometrical shapes overlap. This is based on an SVG-file. The following is an example:
Group 1:
<g transform="matrix(1.0 0.0 0.0 1.0 257.0 124.95)">
<g transform="matrix(1.7880859 0.0 0.0 0.9476929 -0.05 0.0)">
<path d="M 18.9 8.15 L -18.85 8.15 L -18.85 -8.1 L 18.9 -8.1 L 18.9 8.15 Z"/>
</g>
</g>
Group 2:
<g transform="matrix(1.0 0.0 0.0 1.0 244.05 85.95)">
<path transform="matrix(0.009765625 0.0 0.0 0.009765625 64.3499984741211 9.0)" d="M 328.0 0.0 L 328.0 -176.0 L 12.0 -176.0 L 12.0 -260.0 L 348.0 -728.0 L 420.0 -728.0 L 420.0 -260.0 L 520.0 -260.0 L 520.0 -176.0 L 420.0 -176.0 L 420.0 0.0 L 328.0 0.0 Z M 420.0 0.0 L 420.0 0.0 Z M 328.0 -260.0 L 328.0 -576.0 L 101.0 -260.0 L 328.0 -260.0 Z M 101.0 -260.0 L 101.0 -260.0 Z"/>
</g>
These items are in svg format. What it means is the following:
- The outer element (
g)is a group which contains some shapes. - A group can contain other groups (such as in the first example
- a group has a matrix transformation which consists of 6 values: 1: x scale 2: y skew 3: x skew 4: y scale 5: x translate 6: y translate
So, for the first item that means that x is scaled by 1.0, y is scaled by one, x is translated by 257 and y is translated by 124.95
- a path also has a matrix transform which abides to the same rules
- a path has a value (d) which defines how it's drawn. It works by drawing the line following the instructions (shown by a letter). The following instructions are provided:
L: Line to
M: Move to
C: curve to
Z: close path
Now, given these two groups, how can I find out whether they overlap or not?
What I have tried so far is establishing the left most point and the top most point of each group. I did this by taking the total translation and then looking for the left most point in the path and adding these together. However, I don't know how to take the curve into consideration and the results are incorrect (based on manual inspection).
Also, once I have these, how would I go checking whether they overlap?
I'm sorry if this question is a bit unclear (or not fit for math.stackexchange).
Let two groups of points plus the curves or lines connecting them be labeled $A$ and $B$. Calculate the center of each by taking the arithmetic mean of all the points (including the points of the curves/lines) and label these $A_c,B_c$. Find the largest and smallest radius of any point within each group, and label these $A_{r_{max}},A_{r_{min}},B_{r_{max}},B_{r_{min}}$. Finally, let $d$ be the distance between $A_c$ and $B_c$. Then you have some guaranteed conditions and some uncertain conditions for whether one group is contained within the other:
$(1)$ If $A_{r_{max}}\lt B_{r_{min}}-d$, then $A$ is definitely contained within $B$. (Reversing the labeling of $A$ and $B$ has no effect on the truth of this.) Note that the distances here are all positive real numbers.
$(2)$ If $A_{r_{max}}\gt B_{r_{max}}$ and $A_{r_{min}}\lt B_{r_{min}}-d$, then neither shape is contained within the other.
$(3)$ If $d\gt A_{r_{max}}+B_{r_{max}}$ then the two shapes have no common area, i.e., they do not intersect.
Other conditions of the above inequalities would require deeper analysis of the shapes and their points to determine whether there is any common ground.
Note that unless $A$ or $B$ is transformed in a way that changes the shape, the arithmetic mean of the points of that shape does not change.