多边形求交
1. 动画的实现
使用glutTimerFunc函数，反复回调刷新，产生动画效果。2. 点在多边形内部判断
使用多边形的性质，多边形内部的点起始的射线与多边形有奇数个交点，外部的点起始的射线有偶数个交点。所以，我写算法的依据就是从一个点做水平的射线，计算其与各个边有没有交点
3. 求交点
简单的二维几何学4. 交集的点序：
当我们得到了交点和型内点后，下一个是核心问题，点序。我们定义红色的多边形是P，白色的是Q，交点是M，等待排序的点如标注
首先我们将点存储成两组:
组1：M1P2M2M3M4
组2：Q1M1M2M3M4Q5
在每个有序组内，都按照顺时针存储。这里要注意一个问题，如果一个边上有两个交点，需要使用顶点与交点的距离来判定点序。
然后，将组2插入组1：
我们知道，要插入的Q点，一定在两个交点M之间。
所以，我们先把组2顺时针移动变成：M4Q5Q1M1M2M3
这时候，在组1中找到M4和M1
M1P2M2M3M4
将Q5Q1按顺序插入：
M1P2M2M3M4 Q5Q1
这样，就得到了相交的图像。
同理，并运算也是这样进行，不过就是把型内点变成型外点。
5. 数据结构
这里只用了堆栈，但是后来发现，使用链表更具优越性，但尚未修改。6. 改进方式
如果想在凹多边形使用这套算法，必须先进行凹多边形三角划分，再套用方法。7. 算法框图
引用了：黄俊华, 闫遂军, 朱小龙,等. 一种凸多边形的交、并求解算法[J]. 桂林理工大学学报, 2007, 27(4):589-592.
效果及实现
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
#include "list.h"
#include "gl/glut.h"
#include "stack.h"
const GLfloat Pi = 3.1415926536f;
GLfloat
POLYGON_A[5][2] = { { 0, 0 },{ -0.1f, 0.5f },{ 0, 0.9f },{ 0.4f, 0.7f },{ 0.5f, 0.2f } };
GLfloat
//POLYGON_B[5][2] = { { -0.4f, 0.1 },{ -0.6, 0.6f },{ -0.5f, 0.7f },{ 0.1f, 0.71f },{ -0.2f, 0.21f } };
POLYGON_B[5][2] = { { -0.4f, 0.1 },{ -0.6, 0.5f },{ -0.5f, 0.7f },{ 0.1f, 0.51f },{ -0.2f, 0.21f } };
//POLYGON_B[5][2] = { { -0.5f, 0.1 },{ -0.6, 0.8f },{ -0.5f, 0.9f },{ 0.1f, 0.71f },{ -0.2f, 0.21f } };
GLfloat movetmp = 0.00301f;
int num = 5;
GLfloat label=1;
int jb = 1;//取1为交，取0为并
GLfloat max(GLfloat a, GLfloat b) {
if (a > b) return a;
else return b;
}
GLfloat min(GLfloat a, GLfloat b) {
if( a < b) return a;
else return b;
}
int next(int a) {
if (a == (num - 1)) return 0;
else return a + 1;
}
int last(int a) {
if (a == 0) return num-1;
else return a - 1;
}
int PtInPolygon(GLfloat p[2], GLfloat POLYGON[5][2], int nCount)
{
int nCross = 0;
GLfloat x;
for (int i = 0; i < nCount; i++)
{
GLfloat p1[2];
GLfloat p2[2];
p1[0]= POLYGON[i][0];
p1[1] = POLYGON[i][1];
p2[0] = POLYGON[next(i)][0];
p2[1] = POLYGON[next(i)][1];
// 求解 y=p.y 与 p1p2 的交点
if (p1[1] == p2[1]) // p1p2 与 y=p0.y平行
continue;
if (p[1] < min(p1[1], p2[1])) // 交点在p1p2延长线上
continue;
if (p[1] >= max(p1[1], p2[1])) // 交点在p1p2延长线上
continue;
// 求交点的 X 坐标 --------------------------------------------------------------
x = (p[1] - p1[1]) * (p2[0] - p1[0]) /(p2[1] - p1[1]) + p1[0];
if (x >p[0])
nCross++; // 只统计单边交点
}
// 单边交点为偶数，点在多边形之外 ---
return (nCross % 2 == 1);
}
GLfloat getX(GLfloat pointA[2], GLfloat pointB[2], GLfloat pointC[2], GLfloat pointD[2],int nt) {
GLfloat X[2];
GLfloat m, n, a, b, c, d;//ax+by=m cx + dy = n
b = -1; d = -1;
a = (pointA[1] - pointB[1]) / (pointA[0] - pointB[0]);
m = (pointA[1] - pointB[1]) / (pointA[0] - pointB[0])*pointA[0] - pointA[1];
c= (pointC[1] - pointD[1]) / (pointC[0] - pointD[0]);
n = (pointC[1] - pointD[1]) / (pointC[0] - pointD[0])*pointC[0] - pointC[1];
X[0]= (m*d - b*n) / (a*d - b*c);
X[1]= (m*c - a*n) / (b*c - a*d);
if ((X[0] <= max(pointA[0], pointB[0])) && (X[0] >= min(pointA[0], pointB[0])) && (X[0] <= max(pointC[0], pointD[0])) && (X[0] >= min(pointC[0], pointD[0])) && (X[1] <= max(pointA[1], pointB[1])) && (X[1] >= min(pointA[1], pointB[1])) && (X[1] <= max(pointC[1], pointD[1])) && (X[1] >= min(pointC[1], pointD[1])))
{
if (nt == 1) return X[1];
else return X[0];
}
else return 10086;
}
void myDisplay(void)
{
int n = 1000;
int a = 0;
int c = 0;
//int x;
//int y;
int number=0;
//int labelinB[11];
int part[5][5];
int k = 0;
GLfloat pointBtmp[3];
GLfloat X[2],Xtmp[2];
GLfloat Distance[2];
GLfloat pointB[100][3];
DuLinkList Listx;
DuLinkList Listy;
InitList(&Listx);
InitList(&Listy);
Stack mystackx;
Stack mystacky;
InitStack(&mystackx);
InitStack(&mystacky);
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 3; j++){
pointB[i][j]= -1;
}
}
glClear(GL_COLOR_BUFFER_BIT);
// 按照 A->C->E->B->D->A 的顺序，可以一笔将五角星画出
glBegin(GL_LINE_LOOP);
glColor3f(1.0f, 0.0f, 0.0f);
glVertex2fv(POLYGON_A[0]);
glVertex2fv(POLYGON_A[1]);
glVertex2fv(POLYGON_A[2]);
glVertex2fv(POLYGON_A[3]);
glVertex2fv(POLYGON_A[4]);
glEnd();
glBegin(GL_LINE_LOOP);
glColor3f(1.0f, 1.0f, 1.0f);
glVertex2fv(POLYGON_B[0]);
glVertex2fv(POLYGON_B[1]);
glVertex2fv(POLYGON_B[2]);
glVertex2fv(POLYGON_B[3]);
glVertex2fv(POLYGON_B[4]);
glEnd();
/* number = 0;
//In B polygon
k = 0;
x = 0;
for (c = 0; c < num; c++) {
if (PtInPolygon(POLYGON_B[c], POLYGON_A, num) == 1) {
labelinB[k] = c;
if ((labelinB[k] - labelinB[k - 1]) == 1) {
y = y + 1;
part[x][y + 1] = labelinB[k];
}
else {
part[x][0] = labelinB[k];
x = x + 1;
y = 0;
}
k++;
//Push(&mystackx, POLYGON_B[c][0]);
//Push(&mystacky, POLYGON_B[c][1]);
glBegin(GL_POLYGON);
for (int i = 0; i < n; ++i)
glVertex2f(POLYGON_B[c][0] + 0.02 * cos(2 * Pi / n*i), POLYGON_B[c][1] + 0.02 * sin(2 * Pi / n*i));
glEnd();
}
}
labelinB[k] = -1;
*/
//求交点
for (a = 0; a < num; a++) {
number = 0;
if (PtInPolygon(POLYGON_A[a], POLYGON_B, num) == jb) {
Push(&mystackx, POLYGON_A[a][0]);
Push(&mystacky, POLYGON_A[a][1]);
glBegin(GL_POLYGON);
for (int i = 0; i < n; ++i)
glVertex2f(POLYGON_A[a][0] + 0.02 * cos(2 * Pi / n*i), POLYGON_A[a][1] + 0.02 * sin(2 * Pi / n*i));
glEnd();
}
for (c = 0;c < num; c++) {
X[0] = getX(POLYGON_A[a], POLYGON_A[next(a)], POLYGON_B[c], POLYGON_B[next(c)], 0);
X[1] = getX(POLYGON_A[a], POLYGON_A[next(a)], POLYGON_B[c], POLYGON_B[next(c)], 1);
if (X[0] != 10086) {
number++;
Distance[number-1]=sqrt((X[0] - POLYGON_A[a][0]) *(X[0] - POLYGON_A[a][0]) + (X[1] - POLYGON_A[a][1])*(X[1] - POLYGON_A[a][1]));
Push(&mystackx, X[0]);
Push(&mystacky, X[1]);
glBegin(GL_POLYGON);
for (int i = 0; i < n; ++i)
glVertex2f(X[0] + 0.02 * cos(2 * Pi / n*i), X[1] + 0.02 * sin(2 * Pi / n*i));
glEnd();
if (number == 2 && Distance[0]>Distance[1]) {
Pop(&mystackx);
Pop(&mystacky);
Xtmp[0]=Pop(&mystackx);
Xtmp[1]=Pop(&mystacky);
Push(&mystackx, X[0]);
Push(&mystacky, X[1]);
Push(&mystackx, Xtmp[0]);
Push(&mystacky, Xtmp[1]);
}
}
}
}
//插入分块
//对偶交叉
//求交点
k = 0;
for (a = 0; a < num; a++) {
number = 0;
if (PtInPolygon(POLYGON_B[a], POLYGON_A, num) == jb) {
pointB[k][0] = POLYGON_B[a][0];
pointB[k][1] = POLYGON_B[a][1];
pointB[k][2] = 1;//1表示要插入的点
k++;
glBegin(GL_POLYGON);
for (int i = 0; i < n; ++i)
glVertex2f(POLYGON_B[a][0] + 0.02 * cos(2 * Pi / n*i), POLYGON_B[a][1] + 0.02 * sin(2 * Pi / n*i));
glEnd();
}
for (c = 0; c < num; c++) {
X[0] = getX(POLYGON_B[a], POLYGON_B[next(a)], POLYGON_A[c], POLYGON_A[next(c)], 0);
X[1] = getX(POLYGON_B[a], POLYGON_B[next(a)], POLYGON_A[c], POLYGON_A[next(c)], 1);
if (X[0] != 10086) {
//
//
number++;
Distance[number - 1] = sqrt((X[0] - POLYGON_B[a][0]) *(X[0] - POLYGON_B[a][0]) + (X[1] - POLYGON_B[a][1])*(X[1] - POLYGON_B[a][1]));
pointB[k][0] = X[0];
pointB[k][1] = X[1];
pointB[k][2] = 0;//1表示要插入的点
k++;
glBegin(GL_POLYGON);
for (int i = 0; i < n; ++i)
glVertex2f(X[0] + 0.02 * cos(2 * Pi / n*i), X[1] + 0.02 * sin(2 * Pi / n*i));
glEnd();
if (number == 2 && Distance[0]>Distance[1]) {
k--;
pointB[k][0] = -1;
pointB[k][1] =-1;
pointB[k][2] = -1;//1表示要插入的点
k--;
Xtmp[0] = pointB[k][0];
Xtmp[1] = pointB[k][1];
pointB[k][0] = X[0];
pointB[k][1] = X[1];
pointB[k][2] = 0;//1表示要插入的点
k++;
pointB[k][0] = Xtmp[0];
pointB[k][1] = Xtmp[1];
pointB[k][2] = 0;//1表示要插入的点
k++;
}
}
}
}
//插入操作
k--;
a = k;
while ((pointB[0][2] == 1 || pointB[k][2] == 1) && a>=0) {
pointBtmp[0] = pointB[k][0];
pointBtmp[1] = pointB[k][1];
pointBtmp[2] = pointB[k][2];
for (int i = 0; i < k; i++) {
pointB[k - i][0] = pointB[k - i - 1][0];
pointB[k - i][1] = pointB[k - i - 1][1];
pointB[k - i][2] = pointB[k - i - 1][2];
}
pointB[0][0] = pointBtmp[0];
pointB[0][1] = pointBtmp[1];
pointB[0][2] = pointBtmp[2];
a--;//判断并集时候的分离情况
}
//绘制分离的两图
if (a ==-1 || jb==0) {
a = -1;
glBegin(GL_POLYGON);
glColor3f(1.0f, 1.0f, 0.0f);
while (a<k) {
a++;
X[0] = pointB[a][0];
X[1] = pointB[a][1];
glVertex2fv(X);
}
glEnd();
glBegin(GL_POLYGON);
glColor3f(1.0f, 1.0f, 0.0f);
while (!IsEmpty(&mystackx)) {
X[0] = Pop(&mystackx);
X[1] = Pop(&mystacky);
glVertex2fv(X);
}
glEnd();
}
//涂色黄色
if (a != -1) {
glBegin(GL_POLYGON);
glColor3f(1.0f, 1.0f, 0.0f);
while (!IsEmpty(&mystackx)) {
X[0] = Pop(&mystackx);
X[1] = Pop(&mystacky);
glVertex2fv(X);
for (int i = k; i >= 0; i--) {
if (X[0] == pointB[i][0] && X[1] == pointB[i][1] && pointB[i - 1][2] == 1 && jb==1) {
while (pointB[i][2] != 1 && i >= 0) i--;//找到需要插入的开始点（只要不是1就跳过去）
while (pointB[i][2] == 1 && i >= 0) {//对于所有的1来说，都进行这个操作
Xtmp[0] = pointB[i][0];
Xtmp[1] = pointB[i][1];
glVertex2fv(Xtmp);
i--;
}
}
}
}
glEnd();
}
glFlush();//这个一定要在函数最后面
}
void drive(int data)
{
if (_kbhit()) /* do nothing */ movetmp = 0;
for (int i = 0; i < 5; i++) {
POLYGON_B[i][0] = POLYGON_B[i][0] + movetmp;
}
if ((POLYGON_B[0][0] < -0.8) || (POLYGON_B[0][0] > 1)) movetmp = -movetmp;
glutTimerFunc(5, drive, -1);// call drive() again in 50 milliseconds /*callback function moves the car. .... move x, y, z, etc
glutPostRedisplay();
}
int main(int argc, char *argv[])
{
glutInit(&argc, argv);
glColor3f(1.0, 0.0, 0.0);
glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);
glutInitWindowPosition(100, 100);
glutInitWindowSize(500, 500);
glutCreateWindow("第一次 OpenGL 作业");
glutDisplayFunc(&myDisplay);
glutTimerFunc(5, drive, -1); // physics, movement equations here
glutMainLoop();
return 0;
}