
平台论坛博客文库

› 论坛 › 程序设计 › C/C++ › 如何求四条直线所围成的四边形的顶点

1 23 / 3 页

如何求四条直线所围成的四边形的顶点 [复制链接]

jianjiandandan

白手起家

论坛徽章:: 0

21楼 [报告]

发表于 2007-09-30 09:37 |只看该作者

正在编写，请大家不要着急啊，本人编码的能力比较弱，
只好慢工出细活了，等做完了，请大家帮我参考参考啊！

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

drowsyboy

丰衣足食

论坛徽章:: 0

22楼 [报告]

发表于 2007-10-09 12:54 |只看该作者

国庆节没事，写了一个函数，似乎可以解决这个问题

原帖由 jianjiandandan 于 2007-9-28 15:57 发表
小弟近来遇到一个问题如下：
已知四条直线的方程，判断出这四条直线是否围成了一个四边形，
如果围成了一个四边形，那么请求出这四个顶点。
程序倒是编出来，但是感觉很丑陋，代码也很长。
现在向各位大侠请 ...

请大家斧正

问题描述
=======================================================================
平面中有四条直线，其位置任意，现需要判断这四条是否围成四边形。如果
围成四边形，则求出所有的四边形（可以是凸，也可以是凹）的顶点。
原问题的描述见：http://bbs.chinaunix.net/thread-997555-1-4.html
=======================================================================
问题分析
=======================================================================
其基本的解决思路是:
1).构造一个张4*4的表，来表示四条直线之间的相互关系，是否相交？如果
不相交，则求出其交点。
2).从第一条直线出发，找到与之相交的另外一条直线，并记录它们交点到
交点集中去;
3).从找到的这条直线上，找到到另外一条直线，及其交点，且这个焦点不在
已记录的交点集中，如果满足上述条件的点找不到，则回溯前一步的结果（即回
到前一步，删除加入到交点集中的点，然后找下一个点），如果满足上诉条件的
点找到，则继续重复步骤3；
4).上述步骤3种，如果已经找到满足条件的四个点，且从最后一个点出发，
可以到达第一个出发的点，那么则构成我们需要找的四边形，这时就顺序打印四
边形的四个顶点。如果不能到达，则向上回溯；
5).如果从第一条直线的所有的与之相交的直线，均查找完毕，则搜索结束。

=======================================================================

所有源代码

/*
*
*
**qrangle.h**
*
*
*/
#ifndef _QRANGLE_H_
#define _QRANGLE_H_
struct point {
float x;
float y;
}; // 交点
struct line {
float a;
float b;
float c;
}; // 直线利用形如 ax+by+c=0 的形式表示直线
struct linerela {
int bIntersect;
struct point scon;
struct linerela *pnext;
}; // 直线关系结构，也用来存放结果
// bIntersect = 0 两条直线平行
// = 1 直线相交
// struct point scon; 直线交点，只在bIntersect=1 是表示交点
// 表示结果是，bIntersect没有意义，scon存放定点
// 所有的定点通过 pnext连接
#define LINENUM 4 //我们找四边形，有四条直线
#endif
/*
*
*
**qrutils.h**
*
*qrutils.h定义了库函数的API，该文件与qrangle.h一起，都需要export给用户
*/
#ifndef _QRUTILS_H_
#define _QRUTILS_H_
#include "qrangle.h"
int find_rangle(struct line *psLine, struct linerela **psRes);
void show_result(struct linerela *pRes);
void free_mem(struct linerela *pRes);
#endif
/*
*
*
**qrangle.c**
*
* 利用一个接口API写的一个测试用例
*/
#include <stdio.h>
#include "qrangle.h"
int main(void)
{
struct line asLine[LINENUM] = {
{1, -1, 1},
{1, 1, -1},
{3, -2, -2},
{3, 2, 2}
//{1, 1, 1},
//{1, -1, 1},
//{1, 1, -1},
//{1, -1, -1}
};
struct linerela *psRes = NULL;
int iFind;
iFind = find_rangle(asLine, &psRes);
if ( NULL != psRes ) {
show_result(psRes);
free_mem(psRes);
}
return 0;
}
/*
*
*
**qrutils.c**
*
* 库函数文件，提供具体的实现
*/
#include <stdio.h>
#include "qrutils.h"
#include "qrangle.h"
#define DET(a1,b1,a2,b2) ((a1)*(b2)-(a2)*(b1)) //计算行列式 ((a1,b1),(a2,b2))
#define VERY_ZERO 0.00001 //表示一个很小的数，用来浮点数和零比较
#define GET_VALUE(x1,y1,x2,y2,x,y) \ //计算点(x,y)在由(x1,y1),(x2,y2)点构成的直线的计算值
( ((y2)-(y1))*(x) + ((x1)-(x2))*(y) + ((x2)-(x1))*(y1) + ((y1)-(y2))*(x1) )
void init_table(struct line *psLine, struct linerela (*psTable)[LINENUM])
{ //初始化直线关系表
int i, j;
float a1, a2;
float b1, b2;
float c1, c2;
for ( i = 0 ; i < LINENUM ; i ++ ) {
for ( j = i ; j < LINENUM ; j ++ ) {
a1 = (psLine + i)->a;
b1 = (psLine + i)->b;
c1 = (psLine + i)->c;
a2 = (psLine + j)->a;
b2 = (psLine + j)->b;
c2 = (psLine + j)->c;
if ( 0 == DET(a1, b1, a2, b2) ) {
(*(psTable+j)+i)->bIntersect = (*(psTable+i)+j)->bIntersect = 0; //平行
}
else {
(*(psTable+j)+i)->bIntersect = (*(psTable+i)+j)->bIntersect = 1; //相交
(*(psTable+j)+i)->scon.x = (*(psTable+i)+j)->scon.x = \
DET(b1, c1, b2, c2)/DET(a1, b1, a2, b2); //求交点x坐标
(*(psTable+j)+i)->scon.y = (*(psTable+i)+j)->scon.y = \
-1 * DET(a1, c1, a2, c2)/DET(a1, b1, a2, b2); //求交点y坐标
}
}
}
}
void AppendPoint(struct linerela **ppsRes, struct point sp)
{ //把点sp加到链表中
struct linerela *tmp;
struct linerela *node;
node = (struct linerela *) malloc(sizeof(struct linerela));
node->scon.x = sp.x;
node->scon.y = sp.y;
node->pnext = NULL;
if ( NULL == *ppsRes ) {
*ppsRes = node; //初始链表为空
}
else {
tmp = *ppsRes;
while ( NULL != tmp->pnext ) {
tmp = tmp -> pnext;
}
tmp->pnext = node; //加入链表尾部，其实加到头部也可以，还相对简单些
}
}
int Exist_In_Result(struct linerela **ppsRes, struct point sp)
{ //判断一个点sp，是否已经在链表中
struct linerela *tmp = *ppsRes ;
if ( NULL == tmp ) {
return 0;
}
while ( NULL != tmp ) {
if ( fabs(tmp->scon.x - sp.x) < VERY_ZERO && \
fabs(tmp->scon.y - sp.y) < VERY_ZERO ) {
return 1;
}
tmp = tmp->pnext;
}
return 0;
}
void Remove_Last_Point(struct linerela **ppsRes)
{ //从链表中删除最近加入的节点
struct linerela *tmp = *ppsRes;
struct linerela *p = NULL;
while ( NULL != tmp->pnext ) {
p = tmp;
tmp = tmp->pnext;
}
if ( tmp == *ppsRes ) { //only one point is in the result
free(*ppsRes);
*ppsRes = NULL;
}
else {
free(tmp);
p->pnext = NULL;
}
}
int judge_quard(struct linerela *psRes)
{ //判断找到的四个点，能否构成一个四边形
struct point *asTmp[LINENUM];
int i = 0;
//先把四个点从链表中拷到数组中，方便操作
while ( NULL != psRes && i < LINENUM ) {
asTmp[i] = &psRes->scon;
psRes = psRes->pnext;
i ++;
}
if ( i < LINENUM ) {
return 0;
}
//排除有3点共线的情况
if ( fabs(DET(asTmp[0]->x-asTmp[1]->x, asTmp[0]->y-asTmp[1]->y, asTmp[1]->x-asTmp[2]->x, asTmp[1]->y-asTmp[2]->y)) > VERY_ZERO &&
fabs(DET(asTmp[0]->x-asTmp[1]->x, asTmp[0]->y-asTmp[1]->y, asTmp[1]->x-asTmp[3]->x, asTmp[1]->y-asTmp[3]->y)) > VERY_ZERO &&
fabs(DET(asTmp[0]->x-asTmp[2]->x, asTmp[0]->y-asTmp[2]->y, asTmp[3]->x-asTmp[2]->x, asTmp[3]->y-asTmp[2]->y)) > VERY_ZERO &&
fabs(DET(asTmp[3]->x-asTmp[1]->x, asTmp[3]->y-asTmp[1]->y, asTmp[1]->x-asTmp[2]->x, asTmp[1]->y-asTmp[2]->y)) > VERY_ZERO ) {
float fa = 0.0, fc = 0.0;
float fb = 0.0, fd = 0.0;
//四个点中，任何3个都不共线
//假设四个点 a-->b-->c-->d-->a
//判断是否构成四边的依据是，点a，c 在直线bd两侧或者点b，d在ac直线两侧
//感谢ceh提供了判断思路
fa = GET_VALUE(asTmp[1]->x, asTmp[1]->y, asTmp[3]->x, asTmp[3]->y, asTmp[0]->x, asTmp[0]->y);
fc = GET_VALUE(asTmp[1]->x, asTmp[1]->y, asTmp[3]->x, asTmp[3]->y, asTmp[2]->x, asTmp[2]->y);
fb = GET_VALUE(asTmp[0]->x, asTmp[0]->y, asTmp[2]->x, asTmp[2]->y, asTmp[1]->x, asTmp[1]->y);
fd = GET_VALUE(asTmp[0]->x, asTmp[0]->y, asTmp[2]->x, asTmp[2]->y, asTmp[3]->x, asTmp[3]->y);
if ( ( fa*fc < (-1 * VERY_ZERO) ) || ( fb*fd < (-1 * VERY_ZERO) ) ) {
return 1;
}
}
return 0;
}
void do_search(struct linerela (*pLineRelaTable)[LINENUM], struct linerela **ppsRes, int iPointNum, int iLineNum, \
struct linerela **pResultSet)
{ //递归搜索，直到符合条件的四个点
int i = 0;
if ( LINENUM == iPointNum ) { //已找到了四个点
//for循环判断，最后一个点是否能到达第一个点
for ( i = 0 ; i < LINENUM ; i ++ ) {
if ( 1 == (*(pLineRelaTable + iLineNum) + i)->bIntersect && \
fabs((*(pLineRelaTable + iLineNum) + i)->scon.x - (*ppsRes)->scon.x) < VERY_ZERO && \
fabs((*(pLineRelaTable + iLineNum) + i)->scon.y - (*ppsRes)->scon.y) < VERY_ZERO ) {
if ( judge_quard(*ppsRes) ) { //是否构成四边形
struct linerela *ptmp = *ppsRes;
while ( NULL != ptmp ) { //把这四个点记录到结果集中
AppendPoint(pResultSet, ptmp->scon);
ptmp = ptmp->pnext;
}
}
}
}
return; //回溯……
}
for ( i = 0 ; i < LINENUM ; i ++ ) { //从当前直线查找
if ( 0 == (*(pLineRelaTable + iLineNum) + i)->bIntersect ) {
continue; //平行
}
if ( Exist_In_Result(ppsRes, (*(pLineRelaTable + iLineNum) + i)->scon) ) {
continue; //交点已经加入
}
AppendPoint(ppsRes, (*(pLineRelaTable + iLineNum) + i)->scon);
//加入点，递归查找
do_search(pLineRelaTable, ppsRes, iPointNum + 1, i, pResultSet);
//go back
Remove_Last_Point(ppsRes); //删除加入的点，找其他分支
}
}
static void remove_duplicate(struct linerela **ppResSet)
{ //把结果集中，找到的重复的四边去掉，这个算法，写太复杂了，应该可以改进
int k = 0, m = 0;
int notinflag = 0;
struct linerela *pStart, *pEnd, *pCheckB, *pSave, *pCheckP, *pRemovePre;
pStart = pEnd = pCheckB = *ppResSet;
while ( k < LINENUM -1 ) { //设置找到初始查找的位置
pCheckB = pCheckB->pnext;
k ++;
}
pRemovePre = pCheckB;
pCheckB = pCheckB->pnext;
while ( NULL != pCheckB ) {
notinflag = 0; //没有重复标志
pEnd = pStart;
k = 0;
while ( k < LINENUM - 1 ) { //去顶比较结束的地方
pEnd = pEnd->pnext;
k ++;
}
pSave = pEnd->pnext;
pEnd->pnext = NULL;
pCheckP = pCheckB;
for ( k = 0 ; k < LINENUM ; k ++ ) { //判断是否重复
if ( Exist_In_Result (&pStart, pCheckP->scon ) ) {
pCheckP = pCheckP->pnext;
}
else { //只要有一个定点不同，就不可能是重复的四边形
notinflag = 1;
break;
}
}
if ( notinflag ) { //没找到，重复下一轮的比较
pEnd->pnext = pSave;
pStart = pSave;
if ( pStart == pCheckB ) { //前面所有的都找过了，没有重复，搜索下一个四边形
k = 0;
while ( k < LINENUM - 1) {
pCheckB = pCheckB->pnext;
k ++;
}
pRemovePre = pCheckB;
pCheckB = pCheckB->pnext;
pStart = pEnd = *ppResSet;
}
}
else { //四边形重复了，删除那四个顶点，并继续搜索
pEnd->pnext = pSave;
pRemovePre->pnext = pCheckP;
while ( pCheckB != pCheckP ) {
pEnd = pCheckB->pnext;
free(pCheckB);
pCheckB = pEnd;
}
pStart = *ppResSet;
}
}
}
int find_rangle(struct line *psLine, struct linerela **ppResSet)
{ //从四条直线中，找四边形
struct linerela **ppsRes;
struct linerela asLineRelaTable[LINENUM][LINENUM];
//如果传入的NULL
if ( NULL == psLine ) {
return 1;
}
memset(asLineRelaTable, 0, sizeof(struct linerela)*LINENUM*LINENUM);
//初始化直线关系表
init_table(psLine, asLineRelaTable);
*ppsRes = NULL;
*ppResSet = NULL;
do_search(asLineRelaTable, ppsRes, 0, 0, ppResSet);
if ( NULL != ppResSet) { //如果找到了四边形，则去除重复的
remove_duplicate(ppResSet);
}
return 0;
}
void show_result(struct linerela *pRes)
{ //打印结果
int i = 0;
printf("The found rangle is : \n");
while ( NULL != pRes ) {
printf("\tpoint %d: %f\t%f\n", i+1, pRes->scon.x, pRes->scon.y);
pRes = pRes->pnext;
i ++;
if ( LINENUM == i ) { //每四个点构成一个四边形
printf("\n");
i = 0;
}
}
void free_mem(struct linerela *pRes)
{ //释放开配的内存
struct linerela *tmp = pRes ;
while ( NULL != pRes ) {
tmp = pRes->pnext ;
free(pRes);
pRes = tmp;
}
}
/*
*
*
**Makefile**
*
*
*/
CC = gcc
CFLAGS = -g
DFLAGS = $(CFLAGS)
Target = qrangle
OBJECT = qrangle.o qrutils.o
.PHONY : all clean
all : $(OBJECT)
$(CC) $(DFLAGS) -o $(Target) $^
$(OBJECT) : %.o : %.c
$(CC) $(CFLAGS) -c $<
clean:
rm -rf $(OBJECT)
rm -rf $(Target)

复制代码

[ 本帖最后由 drowsyboy 于 2007-10-9 12:58 编辑 ]

1 23 / 3 页

返回列表

Chinaunix › 论坛 › 程序设计 › C/C++ › 如何求四条直线所围成的四边形的顶点

如何求四条直线所围成的四边形的顶点 [复制链接]

国庆节没事，写了一个函数，似乎可以解决这个问题

浏览过的版块