/*
This code is a modified version of chull.c, as described in
"Computational Geometry in C" (Second Edition), Chapter 4,
modified for use with the shortest paths code sp.cpp (thus the
name chullsp). It is not written to be comprehensible without the
explanation in that book.
Input: 3n integer coordinates for the points.
It is used for the purposes of the shortest paths code in three
different ways:
1. -o flag: to output a geomview file of the polytope.
2. no flag: to produce a .in file for sp.
3 -g flag: to postprocess the sp output to geomview.
A fourth option is:
4. -m flag: mathematica rather than geomview output.
Finally, a fifth option is
5. -n flag: to indicate nonconvex (e.g., terrain) data
It is clear that these flag names are not well chosen, and should
be better organized.
The reason all this is done in the convex hull code is that chullsp creates
the data structure, from which it is then easy to tack on different
printout functions. But this is all rather hacked together in a rather
unsatisfactory manner at the moment.
Compile: gcc -o chullsp chullsp.c -lm
or make chullsp
Written by Joseph O'Rourke, with contributions by several students.
Modifications for use with sp by Biliana Kaneva.
Last modified: Septemeber 2000
Questions to orourke@cs.smith.edu.
--------------------------------------------------------------------
This code is Copyright 2000 by Joseph O'Rourke. It may be freely
redistributed in its entirety provided that this copyright notice is
not removed.
--------------------------------------------------------------------
*/
#include <stdio.h>
#include <math.h>
/*Define Boolean type */
typedef enum { FALSE, TRUE } bool;
/* Define vertex indices. */
#define X 0
#define Y 1
#define Z 2
#define MAX_INT 2147483647
/* Define structures for vertices, edges and faces */
typedef struct tVertexStructure tsVertex;
typedef tsVertex *tVertex;
typedef struct tEdgeStructure tsEdge;
typedef tsEdge *tEdge;
typedef struct tFaceStructure tsFace;
typedef tsFace *tFace;
struct tVertexStructure {
int v[4];
int vnum;
tEdge duplicate; /* pointer to incident cone edge (or NULL) */
bool onhull; /* T iff point on hull. */
bool mark; /* T iff point already processed. */
bool visible;
tVertex next, prev;
};
struct tEdgeStructure {
tFace adjface[2];
tVertex endpts[2];
tFace newface; /* pointer to incident cone face. */
bool delete; /* T iff edge should be delete. */
tEdge next, prev;
};
struct tFaceStructure {
tEdge edge[3];
tVertex vertex[3];
int label;
bool visible; /* T iff face visible from new point. */
bool lower;
tFace next, prev;
};
typedef struct PathStruct {
int num;
int *faces;
double *fractions;
int *vlabel;
int last;
} Path;
/* Define flags */
#define ONHULL TRUE
#define REMOVED TRUE
#define VISIBLE TRUE
#define PROCESSED TRUE
#define SAFE 1000000 /* Range of safe coord values. */
/* Global variable definitions */
Path *path;
tVertex vertices = NULL;
tEdge edges = NULL;
tFace faces = NULL;
double s[3];
bool debug = FALSE;
bool check = FALSE;
bool output = FALSE;
bool geomview = FALSE;
bool nonconvex = FALSE;
bool mathematica = FALSE;
int vnum = 0;
int vstart[3];
long vindex;
/* Function declarations */
tVertex MakeNullVertex( void );
void ReadVertices( void );
void Print( void );
void SubVec( int a[3], int b[3], int c[3]);
void DoubleTriangle( void );
void ConstructHull( void );
bool AddOne( tVertex p );
int VolumeSign(tFace f, tVertex p);
int Volumei( tFace f, tVertex p );
tFace MakeConeFace( tEdge e, tVertex p );
void MakeCcw( tFace f, tEdge e, tVertex p );
tEdge MakeNullEdge( void );
tFace MakeNullFace( void );
tFace MakeFace( tVertex v0, tVertex v1, tVertex v2, tFace f );
void CleanUp( void );
void CleanEdges( void );
void CleanFaces( void );
void CleanVertices( void );
bool Collinear( tVertex a, tVertex b, tVertex c );
void CheckEuler(int V, int E, int F );
int Normz(tFace f);
void PrintPoint( tVertex p );
void Checks( void );
void Consistency( void );
void Convexity( void );
void PrintOut( tVertex v );
void PrintVertices( void );
void PrintEdges( void );
void PrintFaces( void );
void PrintInputFile( void );
void PrintGeomviewPolytope( void );
void PrintGeomviewSP( void );
void PrintMathematica(void);
void PrintMathematicaFlip(void);
void LowerFaces();
#include "macros.h"
/*-------------------------------------------------------------------*/
main( int argc, char *argv[] )
{
if ( argc > 1 && argv[1][0] == '-' ) {
if( argv[1][1] == 'd' ) {
debug = TRUE;
check = TRUE;
fprintf( stderr, "Debug and check mode\n");
}
if( argv[1][1] == 'c' ) {
check = TRUE;
fprintf( stderr, "Check mode\n");
}
if (argv[1][1] == 'o') {
output = TRUE;
}
if (argv[1][1] == 'g') {
geomview = TRUE;
}
if (argv[1][1] == 'm') {
mathematica = TRUE;
}
if (argv[1][2] == 'n') {
nonconvex = TRUE;
}
}
else if ( argc > 1 && argv[1][0] != '-' ) {
printf ("Usage: %s -d[ebug] c[heck] o[utput geomview format] g[eomview shortest paths]\n", *argv );
printf ("x y z coords of vertices from stdin\n");
exit(1);
}
ReadVertices();
DoubleTriangle();
ConstructHull();
if (nonconvex)
{
LowerFaces();
}
if (output)
PrintGeomviewPolytope();
else
if (geomview)
PrintGeomviewSP();
else if (mathematica)
PrintMathematica();
/* PrintMathematicaFlip();*/
else
PrintInputFile();
/* Print();*/
}
void LowerFaces( void )
{
tFace f = faces;
tVertex v;
int i;
int Flower = 0; /* Total number of lower faces. */
do {
if ( Normz( f ) < 0 ) {
Flower++;
f->lower = TRUE;
}
else f->lower = FALSE;
f = f->next;
} while ( f != faces );
v = vertices;
do {
v->v[Z] = v->v[3];
v = v->next;
} while (v!=vertices);
/*printf("A total of %d lower faces identified.\n", Flower);*/
}
/*---------------------------------------------------------------------
MakeNullVertex: Makes a vertex, nulls out fields.
---------------------------------------------------------------------*/
tVertex MakeNullVertex( void )
{
tVertex v;
NEW( v, tsVertex );
v->duplicate = NULL;
v->onhull = !ONHULL;
v->mark = !PROCESSED;
ADD( vertices, v );
return v;
}
/*---------------------------------------------------------------------
ReadVertices: Reads in the vertices, and links them into a circular
list with MakeNullVertex. There is no need for the # of vertices to be
the first line: the function looks for EOF instead. Sets the global
variable vertices via the ADD macro.
---------------------------------------------------------------------*/
void ReadVertices( void )
{
tVertex v;
int x, y, z, i,j;
int vnum_local = 0;
if (geomview || mathematica)
{
scanf("%d", &vnum);
path = (Path *)calloc(vnum, sizeof(Path));
for (i=0; i < vnum; i++) {
scanf("%d", &path[i].num);
path[i].faces = (int *)calloc((path[i].num+1), sizeof(int));
path[i].fractions = (double *)calloc((path[i].num+1), sizeof(double));
path[i].vlabel = (int *)calloc((path[i].num+1), sizeof(int));
for (j=0; j < path[i].num; j++)
{
scanf("%d %d %lf", &path[i].faces[j], &path[i].vlabel[j], &path[i].fractions[j]);
}
path[i].last = i;
}
scanf("%d", &vindex);
}
/* scanf("%d %d %d", &vstart[0], &vstart[1], &vstart[2]);*/
while ( scanf ("%d %d %d", &x, &y, &z ) != EOF ) {
v = MakeNullVertex();
v->v[X] = x;
v->v[Y] = y;
if (nonconvex)
{
v->v[3] = z;
没有合适的资源?快使用搜索试试~ 我知道了~
sp.tar.gz_pre
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 33 浏览量
2022-09-23
23:03:09
上传
评论
收藏 29KB GZ 举报
温馨提示
共17个文件
h:6个
cpp:6个
readme:1个
This code is in a "pre-release" state, in that its documentation is currently less than professional. See the Web pages at for the latest information.
资源推荐
资源详情
资源评论
收起资源包目录
sp.tar.gz (17个子文件)
llist.h 2KB
macros.h 1KB
ctree.h 960B
cone.h 4KB
structs.h 3KB
mathops.h 1KB
sp.cpp 46KB
cone.cpp 1KB
structs.cpp 1KB
s10.in 2KB
README 956B
s10.out 402B
chullsp.c 49KB
ctree.cpp 3KB
mathops.cpp 6KB
llist.cpp 5KB
Makefile 596B
共 17 条
- 1
资源评论
局外狗
- 粉丝: 67
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功