1

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).

Kenneth
  • 113
  • If you take the average of all the points in each group, you will get the center of that group. If you take the average over the centers, you will get the midpoint between them. Finding out whether they actually intersect is non-trivial for arbitrary shapes, but if you can approximate your shapes using circles or squares you can apply distance formulas and decide based on those. – abiessu Oct 15 '13 at 14:20
  • Actually there may be a simplicifcation: I want to know whether one shape is contained within another, intersection will never be possible, either it's in or it's out. When you say "take the average of the points in each group", to which points are you referring? The ones in the path, the ones in the group or all of them? – Kenneth Oct 15 '13 at 14:26
  • All of the points per group. To determine whether one is contained within another, there are a couple options: (i) determine the largest distance of all points in a group from its center, then determine whether this plus the offset distance between the group centers puts all points within the smallest distance from the other center; (ii) do a point-by point transition search (O($n^2$)) to see whether the curve joining any two consecutive points from one group crosses the curve joining any two consecutive points from the other group – abiessu Oct 15 '13 at 14:27

1 Answers1

2

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.

abiessu
  • 8,115