?? mathsubs.cpp
字號(hào):
#include "stdafx.h"
//#include "CubSurface.h"
#include "drawcli.h"
#include "math.h"
#include "SideLine.h"
//#define MIN_DISTANCE 10 //最小跨度
/*
判斷“點(diǎn)”是否在任意多邊形內(nèi)：
本算法采用射線追蹤法：
過待測(cè)點(diǎn)的一條射線與多邊形邊的交點(diǎn)的個(gè)數(shù)，若為奇數(shù)，則在
多邊形內(nèi)，否則為外部。
實(shí)際上，我們只關(guān)心交點(diǎn)個(gè)數(shù)，沒必要真正求出射線與邊的交點(diǎn)。
改進(jìn)的射線與邊判斷是否相交的方法如下：
被檢測(cè)的點(diǎn)P(x,y)向y= -∞方向作射線。對(duì)邊PiPi+1按以下順序檢測(cè)：
若(y>=yi and y>=yi＋1) //邊在被測(cè)點(diǎn)P的下方
{
//在左右之間或過右端點(diǎn):
若( xi<x 且 x<=xi＋1 ) 或 ( xi＋1<x 且 x<=xi ) )
射線與邊相交。
}
else 若(y>=yi || y>=yi＋1) //被測(cè)點(diǎn)P在邊的上、下之間
{
//在左右之間或過右端點(diǎn):
若( (xi<x 且 x<=xi＋1 ) 或 ( xi＋1<x 且 x<=xi ) )
{
求射線（垂線）與邊的交點(diǎn)yc
若yc<=y
射線與邊相交。
}
}
*/
BOOL insideEx(float *XPV, float *YPV, int N, double x, double y, int &LOCP)
{
if (N<3) return 0;
float xi,yi, xj,yj;
xi = XPV[N-1];
yi = YPV[N-1];
int p=0;
LOCP = 0;
for (int i=0; i<N; i++)
{
xj = XPV[i];
yj = YPV[i];
if (y>=yi && y>=yj) //點(diǎn)在上面
{
//在左右方向之間或過右邊頂點(diǎn)（線段其它部分在左邊）
if ( ( xi<x && x<=xj ) || ( xj<x && x<=xi) )
{
p++;
}
if (y==yi && y==yj) LOCP = 1;
}
else if (y>=yi || y>=yj) //點(diǎn)在上、下之間
{
if (xi==xj && x==xi) //在垂線上
{
LOCP = 1;
p++;
}
else if ( ( xi<x && x<=xj ) || ( xj<x && x<=xi) )
{
//計(jì)算射線（垂直向下的直線）與邊的交點(diǎn):
//由邊的直線方程：yc = y1+(xc-x1)*(y1-y2)/(x1-x2);
//令xc為待測(cè)點(diǎn)x
double yd = yi+(x-xi)*(yi-yj)/(xi-xj);
if (yd<=y)
{
if (yd==y) LOCP = 1;
p++;
}
}
}
xi = xj;
yi = yj;
}
return (p & 1);
}
//整數(shù)數(shù)組的實(shí)現(xiàn)：
BOOL insideEx(int *XPV, int *YPV, int N, int x, int y, int &LOCP)
{
if (N<3) return 0;
int xi,yi, xj,yj;
xi = XPV[N-1];
yi = YPV[N-1];
int p=0;
LOCP = 0;
for (int i=0; i<N; i++)
{
xj = XPV[i];
yj = YPV[i];
if (y>=yi && y>=yj) //點(diǎn)在上面
{
//在左右方向之間或過右邊頂點(diǎn)（線段其它部分在左邊）
if ( ( xi<x && x<=xj ) || ( xj<x && x<=xi) )
{
p++;
}
if (y==yi && y==yj) LOCP = 1;
}
else if (y>=yi || y>=yj) //點(diǎn)在上、下之間
{
if (xi==xj && x==xi) //在垂線上
{
LOCP = 1;
p++;
}
else if ( ( xi<x && x<=xj ) || ( xj<x && x<=xi) )
{
//計(jì)算射線（垂直向下的直線）與邊的交點(diǎn):
//由邊的直線方程：yc = y1+(xc-x1)*(y1-y2)/(x1-x2);
//令xc為待測(cè)點(diǎn)x
float yd = yi+(float)(x-xi)*(yi-yj)/(xi-xj);
if (yd<=y)
{
if (yd==y) LOCP = 1;
p++;
}
}
}
xi = xj;
yi = yj;
}
return (p & 1);
}
//點(diǎn)數(shù)組的實(shí)現(xiàn)：
BOOL insideEx(CPoint *XYP, int N, int x, int y, int &LOCP)
{
if (N<3) return 0;
int xi,yi, xj,yj;
xi = XYP[N-1].x;
yi = XYP[N-1].y;
int p=0;
LOCP = 0;
for (int i=0; i<N; i++)
{
xj = XYP[i].x;
yj = XYP[i].y;
if (y>=yi && y>=yj) //點(diǎn)在上面
{
//在左右方向之間或過右邊頂點(diǎn)（線段其它部分在左邊）
if ( ( xi<x && x<=xj ) || ( xj<x && x<=xi) )
{
p++;
}
if (y==yi && y==yj) LOCP = 1;
}
else if (y>=yi || y>=yj) //點(diǎn)在上、下之間
{
if (xi==xj && x==xi) //在垂線上
{
LOCP = 1;
p++;
}
else if ( ( xi<x && x<=xj ) || ( xj<x && x<=xi) )
{
//計(jì)算射線（垂直向下的直線）與邊的交點(diǎn):
//由邊的直線方程：yc = y1+(xc-x1)*(y1-y2)/(x1-x2);
//令xc為待測(cè)點(diǎn)x
float yd = yi+(float)(x-xi)*(yi-yj)/(xi-xj);
if (yd<=y)
{
if (yd==y) LOCP = 1;
p++;
}
}
}
xi = xj;
yi = yj;
}
return (p & 1);
}
//計(jì)算曲線的長(zhǎng)度（整數(shù)）:
double calcLength(int *x, int *y, int n)
{
int l;
double lm;
lm = 0;
for (l=0; l<n-1; l++)
{
lm = lm + sqrt( (double)(x[l+1]-x[l])*(x[l+1]-x[l])
+ (double)(y[l+1]-y[l])*(y[l+1]-y[l]) );
}
return lm;
}
//計(jì)算曲線的長(zhǎng)度（浮點(diǎn)）:
double calcLength(float *x, float *y, int n)
{
int l;
double lm;
lm = 0;
for (l=0; l<n-1; l++)
{
lm = lm + sqrt( (x[l+1]-x[l])*(x[l+1]-x[l])
+ (y[l+1]-y[l])*(y[l+1]-y[l]) );
}
return lm;
}
//判斷是否相交（數(shù)學(xué)意義的直線）
int testCrossed(float xa, float ya, float xb, float yb,
float xA, float yA, float xB, float yB,
float &xc, float &yc)
{
double A1 = ya-yb;
double B1 = xb-xa;
double C1 = -xa*A1-ya*B1;
double A2 = yA-yB;
double B2 = xB-xA;
double C2 = -xA*A2-yA*B2;
double CC=A2*B1-A1*B2;
if (CC==0) return 0;
xc = (float)((B2*C1-B1*C2)/CC);
yc = (float)((A1*C2-A2*C1)/CC);
return 1;
}
//判斷是否相交于第一條直線:
int testCross1( float xa, float ya, float xb, float yb,
float xA, float yA, float xB, float yB,
float &xc, float &yc)
{
if (! testCrossed( xa, ya, xb, yb, xA, yA, xB, yB, xc, yc)) return 0;
//是否落在第一條線上
if (xa<xb)
{
if ( xc<xa || xc>xb) return 0;
}
else
{
if ( xc>xa || xc<xb) return 0;
}
if (ya<yb)
{
if ( yc<ya || yc>yb) return 0;
}
else
{
if ( yc>ya || yc<yb) return 0;
}
return 1;
}
//判斷是否相交于第二條直線
int testCross2( float xa, float ya, float xb, float yb,
float xA, float yA, float xB, float yB,
float &xc, float &yc)
{
if (! testCrossed( xa, ya, xb, yb, xA, yA, xB, yB, xc, yc)) return 0;
//是否落在第二條線上
if (xA<xB)
{
if ( xc<xA || xc>xB) return 0;
}
else
{
if ( xc>xA || xc<xB) return 0;
}
if (yA<yB)
{
if ( yc<yA || yc>yB) return 0;
}
else
{
if ( yc>yA || yc<yB) return 0;
}
return 1;
}
//判斷是否相交點(diǎn)在二條直線上：
int testCross( float xa, float ya, float xb, float yb,
float xA, float yA, float xB, float yB,
float &xc, float &yc)
{
if (! testCrossed( xa, ya, xb, yb, xA, yA, xB, yB, xc, yc)) return 0;
if (xa<xb)
{
if (xc<xa || xc>xb) return 0;
}
else
{
if (xc>xa || xc<xb) return 0;
}
if (ya<yb)
{
if (yc<ya || yc>yb) return 0;
}
else
{
if (yc>ya || yc<yb) return 0;
}
if (xA<xB)
{
if (xc<xA || xc>xB) return 0;
}
else
{
if (xc>xA || xc<xB) return 0;
}
if (yA<yB)
{
if (yc<yA || yc>yB) return 0;
}
else
{
if (yc>yA || yc<yB) return 0;
}
return 1;
}
//判斷是否相交點(diǎn)在二條直線上：
long xA, long yA, long xB, long yB,
long &xc, long &yc)
{
float _xc = (float)xc;
float _yc = (float)yc;
return testCross((float)xa, (float)ya, (float)xb, (float)yb,
(float)xA, (float)yA, (float)xB, (float)yB,
_xc,_yc);
}
//直線是否與多邊型相交:
int crossXY(float *x, float *y,
float X, float Y,
float X1,float Y1,
float &XC, float &YC, int np)
{
//判斷是否相交于在二條直線上：
for (int i=0; i<np; i++)
{
int t= testCross(
x[i], y[i],
x[i+1], y[i+1],
X, Y,
X1, Y1,
XC, YC);
if (t) return 1;
}
return 0;
}
/*
判斷一個(gè)點(diǎn)，是否與一條曲線（多線段）的垂直交線的交點(diǎn)，落在該曲線上.
一個(gè)約束條件是，點(diǎn)到各個(gè)線段的距離（垂直距離）要小于給定的值。
*/
BOOL isVCrossAtLine(CPoint po, CPoint ps[], int nps, int &smin, int &ipos,
double &x0, double &y0)
{
CPoint p1,p2;
double A2,B2,C2;
double s;
double xk;
double A,B,C;
int issel = 0;
nps--;
for (int j=0; j<nps; j++)
{
p1 = ps[j];
p2 = ps[j+1];
A = p1.y - p2.y;
B = p2.x - p1.x;
if (A==0 && B==0)
{
if (po.x == p1.x && po.y==p1.y)
{
ipos = j;
return true;
}
continue;
}
C = -p1.x*A - p1.y*B;
//點(diǎn)到直線的距離:
s = fabs(A*po.x + B*po.y +C)/sqrt( B*B+ A*A);
if (s>=smin ) continue;
if (A==0) //水平線段，則過鼠標(biāo)點(diǎn)的垂線為垂直線
{
x0 = po.x;
y0 = p1.y;
if (p1.x < p2.x)
{
if (po.x<p1.x || po.x>p2.x)
continue;
}
else
{
if (po.x<p2.x || po.x>p1.x)
continue;
}
ipos = j;
smin = (int)s;
issel = true;
}
else if (B==0)
{
x0 = p1.x;
y0 = po.y;
if (p1.y < p2.y)
{
if (po.y<p1.y || po.y>p2.y)
continue;
}
else
{
if (po.y<p2.y || po.y>p1.y)
continue;
}
ipos = j;
smin = (int)s;
issel = true;
}
else
{
//點(diǎn)斜式
xk = (float)B/A;
A2 = xk;
B2 = -1;
C2 = po.y - xk * po.x;
x0 = - (C *B2-C2*B )/(A *B2-A2*B );
y0 = - (C2*A -C *A2)/(A *B2-A2*B );
if (p1.x < p2.x)
{
if (x0<p1.x || x0>p2.x)
continue;
}
else
{
if (x0<p2.x || x0>p1.x)
continue;
}
if (p1.y < p2.y)
{
if (y0<p1.y || y0>p2.y)
continue;
}
else
{
if (y0<p2.y || y0>p1.y)
continue;
}
ipos = j;
smin = (int)s;
issel = true;
} //end of dip-line
} //end for
return issel;
}
/*
分離的X,Y整數(shù)數(shù)組版本
*/
BOOL isVCrossAtLine(int pox, int poy, int psx[], int psy[],
int nps, int &smin, int &ipos,
double &x0, double &y0)
{
int p1x, p1y;
int p2x, p2y;
double A2,B2,C2;
double s;
double xk;
double A,B,C;
int issel = 0;
nps--;
for (int j=0; j<nps; j++)
{
p1x = psx[j];
p1y = psy[j];
p2x = psx[j+1];
p2y = psy[j+1];
A = p1y - p2y;
B = p2x - p1x;
if (A==0 && B==0)
{
if (pox == p1x && poy==p1y)
{
ipos = j;
smin = 0;
return true;
}
continue;
}
C = -p1x*A - p1y*B;
//點(diǎn)到直線的距離:
s = fabs(A*pox + B*poy +C)/sqrt( B*B+ A*A);
if (s>=smin ) continue;
if (A==0) //水平線段，則過鼠標(biāo)點(diǎn)的垂線為垂直線
{
x0 = pox;
y0 = p1y;
if (p1x < p2x)
{
if (pox<p1x || pox>p2x)
continue;
}
else
{
if (pox<p2x || pox>p1x)
continue;
}
ipos = j;
smin = (int)s;
issel = true;
}
else if (B==0)
{
x0 = p1x;
y0 = poy;
if (p1y < p2y)
{
if (poy<p1y || poy>p2y)
continue;
}
else
{
if (poy<p2y || poy>p1y)
continue;
}
ipos = j;
smin = (int)s;
issel = true;
}
else
{
//點(diǎn)斜式
xk = B/A;
A2 = xk;
B2 = -1;
C2 = poy - xk * pox;
if (A *B2-A2*B==0)
{
j=j;
}
x0 = - (C *B2-C2*B )/(A *B2-A2*B );
y0 = - (C2*A -C *A2)/(A *B2-A2*B );
if (p1x < p2x)
{
if (x0<p1x || x0>p2x)
continue;
}
else
{
if (x0<p2x || x0>p1x)
continue;
}
if (p1y < p2y)
{
if (y0<p1y || y0>p2y)
continue;
}
else
{
if (y0<p2y || y0>p1y)
continue;
}
ipos = j;
smin = (int)s;
issel = true;
} //end of dip-line
} //end for
return issel;
}
/*
分離的X,Y浮點(diǎn)數(shù)組版本
*/
BOOL isVCrossAtLine(float pox, float poy, float psx[], float psy[],
int nps, float &smin, int &ipos,
double &x0, double &y0)
{
float p1x, p1y;
float p2x, p2y;
double A2,B2,C2;
double s;
double xk;
double A,B,C;
int issel = 0;
nps--;
for (int j=0; j<nps; j++)
{
p1x = psx[j];
p1y = psy[j];
p2x = psx[j+1];
p2y = psy[j+1];
A = p1y - p2y;
B = p2x - p1x;
if (A==0 && B==0)
{
if (pox == p1x && poy==p1y)
{
ipos = j;
smin = 0;
return true;
}
continue;
}
C = -p1x*A - p1y*B;
//點(diǎn)到直線的距離:
s = fabs(A*pox + B*poy +C)/sqrt( B*B+ A*A);
if (s>=smin ) continue;
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -