Finding a square in a group of coordinates

Question

Ok, I'm having a bit of trouble finding a solution for this that seems to be a simple geometry problem.

I have a list of triple coordinates that form a square angle.

Between all these triple-coordinates I want to find a pair that forms up a square.

I believe the best I can do to exemplify is show an image:

1. and 2. are irrelevant. 3. and 4. are what I'm looking for.

For each triple coordinate I have the midle point, where the angle is, and two other points that describe the two segments that form the angle.

Summing it up, given six points, 2 for the diagonal + 4 other points, how can I find if these make a square?

obs: the two lines that make the angle are consistent but don't have the same size.

obs2:the lines from different triples may not intersect

Thank you for time and any help and insight provided.

If any term I used is incorrect or just plain hard to understand let me know, I'm not a native english speaker.

Edit: The code as it stands.

//for all triples
for (size_t i = 0; i < toTry.size() - 1; i++) {

            Vec2i center_i = toTry[i].avg;
            //NormalizedDiagonal = ((Side1 - Center) + (Side2 - Center)); 
            Vec2i a = toTry[i].p, b = toTry[i].q;
            Vec2f normalized_i = normalizedDiagonal(center_i, toTry[i].p, toTry[i].q);

            for (size_t j = i + 1; j < toTry.size(); j++) {

                Vec2i center_j = toTry[j].avg;
                //Se os pontos sao proximos, nao importam
                if (areClose(center_i, center_j, 25))
                    continue;

                Vec2f normalized_j = normalizedDiagonal(center_j, toTry[j].p, toTry[j].q);
                line(src, Point(center_i[0], center_i[1]), Point(center_i[0] + 1 * normalized_i[0], center_i[1] + 1 * normalized_i[1]), Scalar(255, 255, 255), 1);

                //test if antiparallel
                if (abs(normalized_i[0] - normalized_j[0]) > 0.1 || abs(normalized_i[1] - normalized_j[1] > 0.1))
                    continue;

                Vec2f delta;
                delta[0] = center_j[0] - center_i[0]; delta[1] = center_j[1] - center_i[1];
                double dd = sqrt(pow((center_i[0] - center_j[0]), 2) + pow((center_i[1] - center_j[1]), 2));
                //delta[0] = delta[0] / dd;
                //delta[1] = delta[1] / dd;

                float dotProduct = normalized_i[0] * delta[0] + normalized_i[1] * delta[1];

                //test if do product < 0
                if (dotProduct < 0)
                    continue;

                float deltaDotDiagonal = delta[0] * normalized_i[0] + delta[1] * normalized_i[1];
                menor_d[0] = delta[0] - deltaDotDiagonal * normalized_i[0];
                menor_d[1] = delta[1] - deltaDotDiagonal * normalized_i[1];
                dd = sqrt(pow((center_j[0] - menor_d[0]), 2) + pow((center_j[1] - menor_d[1]), 2));

                if(dd < 25)
                   [...]

Answer 1

Just to be clear, the actual lengths of the side segments is irrelevant, right? All you care about is whether the semi-infinite lines formed by the side segments of two triples form a square? Or do the actual segments need to intersect?

Assuming the former, a method to check whether two triples form a square is as follows. Let's use the Point3D and Vector3D from the System.Windows.Media.Media3D namespace to define some terminology, since these are decent general-purpose 3d double precision points and vectors that support basic linear algebra methods. These are c# so you can't use them directly but I'd like to be able to refer to some of the basic methods mentioned there.

Here is the basic method to check if two triples intersect:

1. Define a triple as follows: Center, Side1 and Side2 as three Point3D structures.

2. For each triple, define the normalized diagonal vector as

   NormalizedDiagonal = ((Side1 - Center) + (Side2 - Center)); NormalizedDiagonal.Normalize()

   (You might want to cache this for performance.)

3. Check if the two centers are equal within some linear tolerance you define. If equal, return false -- it's a degenerate case.

4. Check if the two diagonal vectors are antiparallel within some angular tolerance you define. (I.e. NormalizedDiagonal1 == -NormalizedDiagonal2 with some tolerance.) If not, return false, not a square.

5. Compute the vector from triple2.Center to triple2.Center: delta = triple2.Center - triple1.Center.

6. If double deltaDotDiagonal = DotProduct(delta, triple1.NormalizedDiagonal) < 0, return false - the two triples point away from each other.

7. Finally, compute the distance from the center of triple2 to the (infinite) diagonal line passing through the center triple1. If zero (within your linear tolerance) they form a square.

   To compute that distance: distance = (delta - deltaDotDiagonal*triple1.NormalizedDiagonal).Length

   Note: deltaDotDiagonal*triple1.NormalizedDiagonal is the projection of the delta vector onto triple1.NormalizedDiagonal, and thus delta - deltaDotDiagonal*triple1.NormalizedDiagonal is the component of delta that is perpendicular to that diagonal. Its length is the distance we seek.

Finally, If your definition of a square requires that the actual side segments intersect, you can add an extra check that the lengths of all the side segments are less than sqrt(2) * delta.Length.

This method checks if two triples form a square. Finding all triples that form squares is, of course, O(N-squared). If this is a problem, you can put them in an array and sort then by angle = Atan2(NormalizedDiagonal.Y, NormalizedDiagonal.X). Having done that, you can find triples that potentially form squares with a given triple by binary-searching the array for triples with angles = +/- π from the angle of the current triple, within your angular tolerance. (When the angle is near π you will need to check both the beginning and end of the array.)

Update

OK, let's see if I can do this with your classes. I don't have definitions for Vec2i and Vec2f so I could get this wrong...

double getLength(Vec2f vector)
{
    return sqrt(pow(vector[0], 2) + pow(vector[1], 2));
}

Vec2f scaleVector(Vec2f vec, float scale)
{
    Vec2f scaled;
    scaled[0] = vec[0] * scale;
    scaled[1] = vec[1] * scale;
    return scaled;
}

Vec2f subtractVectorsAsFloat(Vec2i first, Vec2i second)
{
    // return first - second as float.
    Vec2f diff;
    diff[0] = first[0] - second[0];
    diff[1] = first[1] - second[1];
    return diff;
}

Vec2f subtractVectorsAsFloat(Vec2f first, Vec2f second)
{
    // return first - second as float.
    Vec2f diff;
    diff[0] = first[0] - second[0];
    diff[1] = first[1] - second[1];
    return diff;
}

double dot(Vec2f first, Vec2f second)
{
    return first[0] * second[0] + first[1] * second[1];
}

//for all triples
for (size_t i = 0; i < toTry.size() - 1; i++) {

        Vec2i center_i = toTry[i].avg;
        //NormalizedDiagonal = ((Side1 - Center) + (Side2 - Center)); 
        Vec2i a = toTry[i].p, b = toTry[i].q;
        Vec2f normalized_i = normalizedDiagonal(center_i, toTry[i].p, toTry[i].q);

        for (size_t j = i + 1; j < toTry.size(); j++) {

            Vec2i center_j = toTry[j].avg;
            //Se os pontos sao proximos, nao importam
            if (areClose(center_i, center_j, 25))
                continue;

            Vec2f normalized_j = normalizedDiagonal(center_j, toTry[j].p, toTry[j].q);

            //test if antiparallel
            if (abs(normalized_i[0] - normalized_j[0]) > 0.1 || abs(normalized_i[1] - normalized_j[1] > 0.1))
                continue;

            // get a vector pointing from center_i to center_j.
            Vec2f delta = subtractVectorsAsFloat(center_j, center_i);

            //test if do product < 0
            float deltaDotDiagonal = dot(delta, normalized_i);
            if (deltaDotDiagonal < 0)
                continue;

            Vec2f deltaProjectedOntoDiagonal = scaleVector(normalized_i, deltaDotDiagonal);

            // Subtracting the dot product of delta projected onto normalized_i will leave the component
            // of delta which is perpendicular to normalized_i...
            Vec2f distanceVec = subtractVectorsAsFloat(deltaProjectedOntoDiagonal, center_j);

            // ... the length of which is the distance from center_j 
            // to the diagonal through center_i.
            double distance = getLength(distanceVec);

            if(distance < 25) {
            }
        }

Answer 2

1. In a pair of segments, call one "the base segment" and one that is obtained by rotating the base segment by π/2 counterclockwise is "the other segment".
2. For each triple, compute the angle between the base segment and the X axis. Call this its principal angle.
3. Sort triples by the principal angle.
4. Now for each triple with the principal angle of α any potential square-forming mate has the principal angle of α+π (mod 2π). This is easy to find by binary search.
5. Furthermore, for two candidate triples with vertices a and a' and principal angles α and α+π, the angle of vector aa' should be α+π/4.
6. Finally, if each of the four segments is at least |aa'|/√2 long, we have a square.

Answer 3

There are two approaches to solving this. One is a very direct approach that involves finding the intersection of two line segments.

You just use the triple coordinates to figure out the midpoint, and the two line segments that protrude from it (trivial). Do this for both triple-sets.

Now calculate the intersection points, if they exist, for all four possible permutations of the extending line segments. From the original answer to a similar question:

You might look at the code I wrote for Computational Geometry in C, which discusses this question in detail (Chapter 1, Section 5). The code is available as SegSegInt from the links at that web site.

In a nutshell, I recommend a different approach, using signed area of triangles. Then comparing appropriate triples of points, one can distinguish proper from improper intersections, and all degenerate cases. Once they are distinguished, finding the point of intersection is easy.

An alternate, image processing approach, would be to render the lines, define one unique color for the lines, and then apply an seed/flood fill algorithm to the first white zone found, applying a new unique color to future zones, until you flood fill an enclosed area that doesn't touch the border of the image.

Good luck!

References

---

1. finding the intersection of two line segments in 2d (with potential degeneracies), Accessed 2014-08-18, <https://math.stackexchange.com/questions/276735/finding-the-intersection-of-two-line-segments-in-2d-with-potential-degeneracies>