Calculate if two lines are symmetrical

Question

I'm developing an app to check if a draw is symmetric or not. All the users line are stored into an ArrayList composed by a list of points, structured as well:

private ArrayList<ArrayList<Pair<Float,Float>>> segments = new ArrayList<>();

This is how I build the drawing area:

The black shape is part of the background and I don't need to consider it when I have to check the symmetry. I only need its center (which I store as a single coordinate) since I need to consider checking the symmetry by it. Since the draws are made by children, I also need to consider a bit of flexibility since the lines will never be exactly symmetric. I implemented a method which divides each segments in 10 parts and then check if the coordinates of each part have a similare increase/decrease:

private boolean checkShape (int z, ArrayList<Pair<Float,Float>> points) {
    ArrayList<Pair<Float,Float>> copia = segments.get(z);
    int nGroupsFirstShape = (segments.get(z).size()*10)/100;
    int nValuesFirstShape[] = new int[10];
    for (int j=0, j2=0; j<10; j++, j2+=nGroupsFirstShape) {
        int sumValues=0;
        sumValues+=copia.get(j2).first-copia.get(j2+nGroupsFirstShape-1).first;
        sumValues+=copia.get(j2).second-copia.get(j2+nGroupsFirstShape-1).second;
        nValuesFirstShape[j] = sumValues;
    }
    ArrayList<Pair<Float,Float>> copia2 = points;
    int nGroupSecondShape = (copia2.size()*10)/100;
    int nValuesSecondShape[] = new int[10];
    for (int j=0, j2=0; j<10; j++, j2+=nGroupSecondShape) {
        int sumValues=0;
        sumValues+=copia2.get(j2).first-copia2.get(j2+nGroupSecondShape-1).first;
        sumValues+=copia2.get(j2).second-copia2.get(j2+nGroupSecondShape-1).second;
        nValuesSecondShape[j] = sumValues;
    }
    int differences[] = new int[10];
    int numberOf = 0;
    for (int index=0; index<10; index++) {
        differences[index] = nValuesFirstShape[index] - nValuesSecondShape[index];
        if (differences[index]<0) differences[index] = -differences[index];
        if (differences[index]<nGroupsFirstShape*2.5) numberOf++;
    }
    if (numberOf>=6) return true; else return false;
}

If this is verified for at least 6 parts, then I can considerer the segments symmetric. The huge problem of this method is that the lines can have different sizes. Do you know any methods to calculate the symmetry of a drawing area? Since I save the image as a bitmap, I also tried to find a method to calculate it directly on the image file, but I didn't find anything

Answer 1

I did not code Java for years and do not have that much time right now. Because of that this answer does not contain running Java code, but only the ideas and some pseudo-code. I hope this helps you, anyway.

One has given two curves curve1 and curve2, and a center of reflection c. You want to compute if the one curve is a point reflection of the other within a given threshold maxDist.

The function to compute this could look like that:

function checkSymmetry(Curve curve1, Curve curve2, Vector c, float maxDist) {
    // reflect one curve
    Curve curve2refl = reflect(curve2, c);
    // compute curve distance
    float d = dist(curve1, curve2refl);
    // check if distance is below threshold
    return d < maxDist;

(I did introduce some classes instead of your ArrayLists of ArrayLists of Pairs of … for better readability. I would recommend you to do the same in your code.)

Point Reflection

The formula of a point reflection can be found on Wikipedia: the reflection of a point p with reflection center c is: 2*c - p.

To reflect a curve you have to reflect all its vertices.

Distance Curve–Curve

When the two red curves are (almost) symmetrical then after the reflection of one of them they should be (almost) identical, i.e. have a distance of (almost) zero. But what is the distance of two curves?

In mathematical set theory there exists a Hausdorff distance. It is a little bit complicated for Non-Mathematicians. But it gives the idea to define the distance of your curves: the maximum distance of a vertex of one curve to the other curve:

function dist(Curve curve1, Curve curve2) {
    d = 0;
    for (Vector p : curve1.vertices) {
        d = max(d, dist(curve2, p));
    }
    for (Vector p : curve2.vertices) {
        d = max(d, dist(curve1, p));
    }
    return d;
}

Distance Point–Curve

So we did reduce the problem to compute the distance of a point to a curve. This is the minimum distance of the point to any of the curve segments:

function dist(Curve curve, Vector p) {
    d = dist(p, curve.vertices.get(0));
    for (int i = 1, n = curve.vertices.size(); i < n; ++i) {
        Vector p1 = curve.vertices.get(i-1);
        Vector p2 = curve.vertices.get(i);
        d = min(d, dist(new Segment(p1, p2), p));
    }
    return d;
}

Distance Point–Segment

For the distance of a point to a segment you find lots of questions with good answers on stackoverflow, e.g. here.

Answer 2

I think this is good mathematical algorithm:

step 1: divide each line into N parts. (squares in the diagram) the number of points on the lines may vary, but the number of parts will now be the same.

for example, 1 line was 100 points, divide it into 10 parts, 10 points will fall into each. the second of 90 points, it will get 10 parts of 9 points.

Calculate the midpoint of each part. fig1

step 2: between each midpoint of both lines we find the middle. (black dots in the diagram) fig2

step 3: we build a line with a minimum deviation from these points. (red line in the diagram) fig3

step 4: estimation of deviation of midpoints from the line. by the average and maximum deviation it will be possible to measure how similar the lines are.

good luck