回复：怎么判断由4个顶点连接成的图形是正方形?图中有多少个正方形?

我怎么感觉拼接图形的方法不行呢。我更倾向于使用一种数据结构“图”，来记录顶点和边，注意边必须记录，边的作用是记录顶点间的连通性，一个正方形的4个顶点间必须是连通的，而判断连通的依据就是边是否存在。

终于写完了
#include <stdio.h>
#define XNUM 5
#define YNUM 5
#define SIDELEN 1
typedef enum direction{RIGHT, BELOW, LEFT, TOP}direction;
typedef class vertex{
public:
float x, y;
struct vertex *top;
struct vertex *below;
struct vertex *left;
struct vertex *right;
vertex(float row, float col):x(row), y(col){}
vertex(){}
void set_x (float x){this->x = x;}
void set_y (float y){this->y = y;}
void set_top (struct vertex *p){top = p;}
void set_below (struct vertex *p){below = p;}
void set_left (struct vertex *p){left = p;}
void set_right (struct vertex *p){right = p;}
}vertex;
vertex *chart;
vertex * loadVertex(){
vertex *v = new vertex[YNUM * XNUM];
for(int i = 0; i < YNUM; i++){
printf("\n\n");
for(int j = 0; j < XNUM; j++){
printf("* ");
int num = i * YNUM +j;
v[num].set_x(i);
v[num].set_y(j);
switch(i){
case 0:
v[num].set_top(NULL);
v[num].set_below(&v[(i + 1) * YNUM + j]);
break;
case YNUM - 1:
v[num].set_top(&v[(i - 1) * YNUM + j]);
v[num].set_below(NULL);
break;
default:
v[num].set_top(&v[(i - 1) * YNUM + j]);
v[num].set_below(&v[(i + 1) * YNUM + j]);
break;
}
switch(j){
case 0:
v[num].set_left(NULL);
v[num].set_right(&v[i * YNUM + (j + 1)]);
break;
case XNUM - 1:
v[num].set_left(&v[i * YNUM + (j - 1)]);
v[num].set_right(NULL);
break;
default:
v[num].set_left(&v[i * YNUM + (j - 1)]);
v[num].set_right(&v[i * YNUM + (j + 1)]);
break;
}
}
}
return v;
}
void connectVertex(vertex &v, vertex &connect){
if(v.x == connect.x){
if(v.y < connect.y){
v.right = &connect;
connect.left = &v;
}else{
v.left = &connect;
connect.right = &v;
}
return;
}
if(v.y == connect.y){
if(v.x < connect.x){
v.below = &connect;
connect.top = &v;
}else{
v.top = &connect;
connect.below = &v;
}
return;
}
vertex cha13 = chart[13];
vertex *p13 = &chart[13];
vertex cha12 = chart[12];
vertex *p12 = &chart[12];
}
void connectVertex(vertex &v, vertex &connect0, vertex &connect1){
connectVertex(v, connect0);
connectVertex(v, connect1);
}
void connectVertex(vertex &v, vertex &connect0, vertex &connect1, vertex &connect2){
connectVertex(v, connect0, connect1);
connectVertex(v, connect2);
}
void addToChart(vertex * v, int index){
float x = v->x; float y = v->y;
vertex *v00 = v, *v01 = new vertex(x, y + 0.5), *v02 = new vertex(x, y + 1);
vertex *v10 = new vertex(x + 0.5, y), *v12 = new vertex(x + 0.5, y + 1);
vertex *v20 = new vertex(x + 1, y), *v21 = new vertex(x + 1, y + 0.5), *v22 = new vertex(x + 1, y + 1);
connectVertex(*v00, *v01, *v10);
connectVertex(*v01, chart[7+index], *v02/*, chart[2+index]*/);
connectVertex(*v02, *v12);
connectVertex(*v10, *v20, chart[7+index]/*, chart[6+index]*/);
connectVertex(*v12, *v22, chart[7+index]/*, chart[8+index]*/);
connectVertex(*v20, *v21);
connectVertex(*v21, *v22, chart[7+index]/*, chart[12+index]*/);
}
typedef class squirrel{
public:
vertex *map;
int square;
squirrel():square(0){};
vertex* runto(vertex *start, direction d, float range){
vertex cha13 = chart[13];
vertex *p13 = &chart[13];
vertex cha12 = chart[12];
vertex *p12 = &chart[12];
vertex *v;
switch(d){
case RIGHT:
v = start->right;
while(v != NULL){
if(start->y + range == v->y)
return v;
v = v->right;
}
break;
case BELOW:
v = start->below;
while(v != NULL){
if(start->x + range == v->x)
return v;
v = v->below;
}
break;
case LEFT:
v = start->left;
while(v != NULL){
if(start->y - range == v->y)
return v;
v = v->left;
}
break;
case TOP:
v = start->top;
while(v != NULL){
if(start->x - range == v->x)
return v;
v = v->top;
}
break;
default: break;
}
return NULL;
}
bool vertex_run(vertex *v, float range){
vertex *t = v;
if(!(t = runto(t, RIGHT, range)))
return false;
if(!(t = runto(t, BELOW, range)))
return false;
if(!(t = runto(t, LEFT, range)))
return false;
vertex *b = t->top;
if(!(t = runto(t, TOP, range)))
return false;
return true;
}
void map_run(vertex *v){
for(vertex *vi = v; vi != NULL; vi = vi->below)
for(vertex *vj = vi; vj != NULL; vj = vj->right){
if(vertex_run(vj, 1))
square++;
if(vertex_run(vj, 0.5))
square++;
if(vertex_run(vj, 2))
square++;
if(vertex_run(vj, 3))
square++;
if(vertex_run(vj, 4))
square++;
}
}
}squirrel;
int main(int argc, char *argv[])
{
chart = loadVertex();
squirrel littel;
littel.map_run(chart);
vertex *v0 = new vertex(0.5, 1.5);
addToChart(v0, 0);
littel.map_run(v0);
vertex *v1 = new vertex(2.5, 1.5);
addToChart(v1, 10);
littel.map_run(v1);
printf("The square count = %d\n", littel.square);
}

main 中：
chart = loadVertex(); 加载5*5的点阵。
littel.map_run(chart); 找正方型。
vertex *v0 = new vertex(0.5, 1.5);//创建新加载的8个点
addToChart(v0, 0);加入5*5点阵
littel.map_run(v0);找新加的8个点的正方形（9个点，中心一个点是5*5点阵的）
同上两步
vertex *v1 = new vertex(2.5, 1.5);
addToChart(v1, 10);
littel.map_run(v1);

程序已经验证，结果正确。 大家都帮忙看看，改进改进。会C，正学C++，写de乱，可读性差吧！！！

没人看了么，我还写了一整天代码，都没人讨论...

我有个简单的方法：
建立一个二维数组存每个点坐标，从上到下每个点遍历，寻找这个点的右下点（不往左也不往上找），根据这个右下点可以计算出左下点和右上点，左下和右上存在的话就是一个正方形，两个for循环搞定。十几二十行代码的事

//dev-a_square
#include <cstdlib>
#include <iostream>
#include <math.h> using namespace std; struct ve// square.vertex
{
int x;
int y;
};
ve array[41]={ //以左下角为原点,构造矩阵
{0,0},{2,0},{4,0},{6,0},{8,0},
{0,2},{2,2},{4,2},{6,2},{8,2},
{0,4},{2,4},{4,4},{6,4},{8,4},
{0,6},{2,6},{4,6},{6,6},{8,6},
{0,8},{2,8},{4,8},{6,8},{8,8},
{3,1},{3,2},{3,3},{3,5},{3,6},{3,7},
{4,1},{4,3},{4,5},{4,7},
{5,1},{5,2},{5,3},{5,5},{5,6},{5,7}
};
int n=0,n_end=0; bool a_square(ve a,ve b,ve c,ve d)
{
ve e;
//寻找a点的对角点，只要bcd中有一点与a不在同一直线上即可
if((a.x!=b.x )&&(a.y!=b.y))
{
// cout<<"b may be a diagonal"<<endl;
//为了方便后续比较另外两个顶点与与这两个顶点的关系，
//将对角与b交换位置，此处正好是b所以无需交换
}
else
{
if((a.x!=c.x )&&(a.y!=c.y))
{
//cout<<"c may be a diagonal"<<endl;
e=c;//c与b的位置交换
c=b;
b=e;
}
else
{
if((a.x!=d.x )&&(a.y!=d.y))
{
// cout<<"d may be a diagonal"<<endl;
e=d;
d=b;
b=e;
}
else
{
// cout<<"abcd不可能组成正方形";
return 0;
}
}
}
//下面来判断cd和ab能否组成正方形。
if( ((c.x==a.x) && (c.y==b.y) //c和d的其中一个点的x为a的x，y为b的y
&&(d.x==b.x) && (d.y==a.y)) //另一个点的x为b的x，y为a的y
|| ((d.x==a.x) && (d.y==b.y)
&&(c.x==b.x) && (c.y==a.y)) )
{
//cout<<"abcd为矩形"<<endl;
}
if( //这一句是最关键的,貌似就错在这里了,哪位大侠帮忙看看...
(abs(a.x-b.x))==(abs(d.y-c.y))//相邻的两条边长度相等 的矩形是正方形
||(abs(a.y-b.y))==(abs(c.x-d.x))
)
{
/*******
cout<<"("<<a.x<<","<<a.y<<")"<<" and "<<
"("<< b.x<<","<<b.y<<")"<<" and "<<
"("<<c.x<<","<<c.y<<")"<<" and "<<
"("<< d.x<<","<<d.y<<")"<<" 四点是图中的正方形之一 "<< endl;
*********/
return 1;
}
else
{
// cout<<"abcd不可能组成正方形";
return 0;
}
}
int main(int argc, char *argv[])
{
int t=41;//t=sizeof(array)/sizeof(ve)
for(int a=0;a<t;a++)
{
for (int b=0;b<t;b++)
{
for(int c=0;c<t;c++)
{
for(int d=0;d<t;d++)
{
if(a_square(array[a],array,array[c],array[d]))
{
n++;
}
}
}
}
}
n_end=(n/24)-1;//扣掉 (3,3),(3,5),(5,3),(5,5)这个没有连通的.
cout<<"这个图中有"<<n_end<<"个正方形"<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}

图形转换为二维数列，顶点为1，最小边的一半为一个线段长度单位，线段为1，未连接为0
对每个顶点作为左上顶点，以边长为2~x（x为顶点右边剩余长度，步长为2）的正方形框去取数列，求出各边上数的积
满足框上各边上点的乘积不为0，则框的四个顶点是封闭的正方形
#include<iostream>
#include<stdlib.h>
using namespace std;
const int side_min=2; //最小边长为2,也作为循环用的步长
const int side_max=16; //最大边长为16
const int img[17][17]={ //将原图转换为数图，以下计算以此图进行
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1},
{1,0,0,0,1,0,1,1,1,1,1,0,1,0,0,0,1},
{1,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1},
{1,0,0,0,1,0,1,1,1,1,1,0,1,0,0,0,1},
{1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1},
{1,0,0,0,1,0,1,1,1,1,1,0,1,0,0,0,1},
{1,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1},
{1,0,0,0,1,0,1,1,1,1,1,0,1,0,0,0,1},
{1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
struct position{int x;int y;} //位置的结构
vertex[9][9]; //顶点
void getvertex(){ //获得各顶点的位置
for(int i=0;i<9;i=i+1){
for(int j=0;j<9;j=j+1){
vertex[i][j].x=side_min*i;
vertex[i][j].y=side_min*j;
} }
}
int main()
{
getvertex();
int count=0;
int x,y,side_valid;
for(int r=0;r<9;r=r+1){ //定行
for(int c=0;c<9;c=c+1){ //定列
x=vertex[r][c].x;y=vertex[r][c].y;//定点
side_valid=(x<y)?side_max-y:side_max-x;
for(int side=side_min;side<=side_valid;side=side+2){//定框
int pro_t=1,pro_b=1,pro_l=1,pro_r=1;//框上各边上点的积
for(int i=0;i<=side;i=i+1){ //框上竖边上的点
pro_l=pro_l*img[x][y+i];
pro_r=pro_r*img[x+side][y+i];
}
for(int j=0;j<=side;j=j+1){ //框上横边上的点
pro_t=pro_t*img[x+j][y];
pro_b=pro_b*img[x+j][y+side];
}
if(pro_t!=0 && pro_b!=0 && pro_l!=0 && pro_r!=0){
count=count+1;}
}
}
}
cout<<"有"<<count<<"个正方形\n";
system("pause");return 0;
}

//dev-a_square
#include <cstdlib>
#include <iostream>
#include <math.h>using namespace std;struct ve// square.vertex
{
int x;
int y;
};
ve array[41]={ //以左下角为原点,构造矩阵
{0,0},{2,0},{4,0},{6,0},{8,0},
{0,2},{2,2},{4,2},{6,2},{8,2},
{0,4},{2,4},{4,4},{6,4},{8,4},
{0,6},{2,6},{4,6},{6,6},{8,6},
{0,8},{2,8},{4,8},{6,8},{8,8},
{3,1},{3,2},{3,3},{3,5},{3,6},{3,7},
{4,1},{4,3},{4,5},{4,7},
{5,1},{5,2},{5,3},{5,5},{5,6},{5,7}
};
int n=0,n_end=0; bool a_square(ve a,ve b,ve c,ve d)
{
ve e;
if(//四个点中任意两个点都不能相同,否者就不够4个顶点了.
( (a.x==b.x) &&(a.y==b.y) ) ||
( (a.x==c.x) &&(a.y==c.y) ) ||
( (a.x==d.x) &&(a.y==d.y) ) ||
( (c.x==b.x) &&(c.y==b.y) ) ||
( (d.x==b.x) &&(d.y==b.y) ) ||
( (c.x==d.x) &&(c.y==d.y) )
)
{
return 0;
}
//寻找a点的对角点，只要bcd中有一点与a不在同一直线上即可
if((a.x!=b.x )&&(a.y!=b.y))
{
// cout<<"b may be a diagonal"<<endl;
//为了方便后续比较另外两个顶点与与这两个顶点的关系，
//将对角与b交换位置，此处正好是b所以无需交换
}
else
{
if((a.x!=c.x )&&(a.y!=c.y))
{
//cout<<"c may be a diagonal"<<endl;
e=c;//c与b的位置交换
c=b;
b=e;
}
else
{
if((a.x!=d.x )&&(a.y!=d.y))
{
// cout<<"d may be a diagonal"<<endl;
e=d;
d=b;
b=e;
}
else
{
// cout<<"abcd不可能组成正方形";
return 0;
}
}
}
//下面来判断cd和ab能否组成矩形。
if( ((c.x==a.x) && (c.y==b.y) //c和d的其中一个点的x为a的x，y为b的y
&&(d.x==b.x) && (d.y==a.y)) //另一个点的x为b的x，y为a的y
|| ((d.x==a.x) && (d.y==b.y)
&&(c.x==b.x) && (c.y==a.y)) )
{
//cout<<"abcd为矩形"<<endl;
}
else
{
return 0;
}
if( //验证临边是否相等
(abs(a.x-b.x)) ==(abs(a.y-b.y))//a点和b点是对角
)
{
/*******
cout<<"("<<a.x<<","<<a.y<<")"<<" and "<<
"("<< b.x<<","<<b.y<<")"<<" and "<<
"("<<c.x<<","<<c.y<<")"<<" and "<<
"("<< d.x<<","<<d.y<<")"<<" 四点是图中的正方形之一 "<< endl;
/*********/
return 1;
}
else
{
// cout<<"abcd不可能组成正方形";
return 0;
}
}
int main(int argc, char *argv[])
{
int t=41;//t=sizeof(array)/sizeof(ve)
for(int a=0;a<t;a++)
{
for (int b=0;b<t;b++)
{
for(int c=0;c<t;c++)
{
for(int d=0;d<t;d++)
{
if(a_square(array[a],array,array[c],array[d]))
{
n++;
}
}
}
}
}
n_end=(n/24)-1;//扣掉 (3,3),(3,5),(5,3),(5,5)这个没有连通的.
cout<<"这个图中有"<<n_end<<"个正方形"<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}