c++ - Finding a square in a group of coordinates -

ok, i'm having bit of trouble finding solution seems simple geometry problem.

i have list of triple coordinates form square angle.

between these triple-coordinates want find pair forms square.

i believe best can exemplify show image:

1. and 2. irrelevant. 3. , 4. i'm looking for.

for each triple coordinate have midle point, angle is, , 2 other points describe 2 segments form angle.

summing up, given 6 points, 2 diagonal + 4 other points, how can find if these make square?

obs: 2 lines make angle consistent don't have same size.

obs2:the lines different triples may not intersect

thank time , , insight provided.

if term used incorrect or plain hard understand let me know, i'm not native english speaker.

edit: code stands.

//for triples (size_t = 0; < totry.size() - 1; i++) {              vec2i center_i = totry[i].avg;             //normalizeddiagonal = ((side1 - center) + (side2 - center));              vec2i = totry[i].p, b = totry[i].q;             vec2f normalized_i = normalizeddiagonal(center_i, totry[i].p, totry[i].q);              (size_t j = + 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 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)                    [...] 

just clear, actual lengths of side segments irrelevant, right? care whether semi-infinite lines formed side segments of 2 triples form square? or actual segments need intersect?

assuming former, method check whether 2 triples form square follows. let's use point3d , vector3d system.windows.media.media3d namespace define terminology, since these decent general-purpose 3d double precision points , vectors support basic linear algebra methods. these c# can't use them directly i'd able refer of basic methods mentioned there.

here basic method check if 2 triples intersect:

1. define triple follows: center, side1 , side2 3 point3d structures.

2. for each triple, define normalized diagonal vector as

   normalizeddiagonal = ((side1 - center) + (side2 - center)); normalizeddiagonal.normalize()

   (you might want cache performance.)

3. check if 2 centers equal within linear tolerance define. if equal, return false -- it's degenerate case.

4. check if 2 diagonal vectors antiparallel within angular tolerance define. (i.e. normalizeddiagonal1 == -normalizeddiagonal2 tolerance.) if not, return false, not square.

5. compute vector triple2.center triple2.center: delta = triple2.center - triple1.center.

6. if double deltadotdiagonal = dotproduct(delta, triple1.normalizeddiagonal) < 0, return false - 2 triples point away each other.

7. finally, compute distance center of triple2 (infinite) diagonal line passing through center triple1. if 0 (within linear tolerance) form square.

   to compute distance: distance = (delta - deltadotdiagonal*triple1.normalizeddiagonal).length

   note: deltadotdiagonal*triple1.normalizeddiagonal projection of delta vector onto triple1.normalizeddiagonal, , delta - deltadotdiagonal*triple1.normalizeddiagonal component of delta perpendicular diagonal. length distance seek.

finally, if definition of square requires actual side segments intersect, can add check lengths of side segments less sqrt(2) * delta.length.

this method checks if 2 triples form square. finding triples form squares is, of course, o(n-squared). if problem, can put them in array , sort angle = atan2(normalizeddiagonal.y, normalizeddiagonal.x). having done that, can find triples potentially form squares given triple binary-searching array triples angles = +/- π angle of current triple, within angular tolerance. (when angle near π need check both beginning , end of array.)

update

ok, let's see if can classes. don't have definitions vec2i , vec2f 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 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 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 triples (size_t = 0; < totry.size() - 1; i++) {          vec2i center_i = totry[i].avg;         //normalizeddiagonal = ((side1 - center) + (side2 - center));          vec2i = totry[i].p, b = totry[i].q;         vec2f normalized_i = normalizeddiagonal(center_i, totry[i].p, totry[i].q);          (size_t j = + 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;              // vector pointing center_i center_j.             vec2f delta = subtractvectorsasfloat(center_j, center_i);              //test if product < 0             float deltadotdiagonal = dot(delta, normalized_i);             if (deltadotdiagonal < 0)                 continue;              vec2f deltaprojectedontodiagonal = scalevector(normalized_i, deltadotdiagonal);              // subtracting dot product of delta projected onto normalized_i leave component             // of delta perpendicular normalized_i...             vec2f distancevec = subtractvectorsasfloat(deltaprojectedontodiagonal, center_j);              // ... length of distance center_j              // diagonal through center_i.             double distance = getlength(distancevec);              if(distance < 25) {             }         }