求判断一个点是不是在一条线段里面或在不规则图形里面的算法。(200分)

的

的士

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-22

• #1

或者推荐几本书也行。

 

M

maming

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-22

• #2

有点麻烦

 

吕

吕雪松

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-22

• #3

呵，这是CAD/GIS基础算法，晚上我回家后给你帖上来，另，请多到GIS版转转，那里经常
有一些算法提供。

 

的

的士

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-22

• #4

多谢吕大侠。
请问有没有这种书啊。

 

U

ugvanxk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-22

• #5

我们都知道两点连成一条直线，用计算机语言来表示成为已知（x1,y1)与（x2,y2)的两个像素坐标值。并且我们可以通过移动鼠标事件onMouseMove或onMouseDown事件得到当前所在的坐标位置（x,y）。只要通过点到直线的距离公式就可求出是否鼠标落在直线上。
注意：因为像素值很小，所以在判断距离l时要给一定的冗余值最好为4个像素点
公式：l=abs((y2-y1)x+(x1_x2)y+x2*y1-x1*y2)/sqrt(sqr(y2-y1)+sqr(x1-x2))
if l< 4 then showmessage('击中线段');

 

卷

卷起千堆雪tyn

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-22

• #6

判断点是否在不规则图形里，我们通常是根据不规则图形建立区域，利用WINDOWS API 函数：PtInRegion()来判断.

 

Z

zyg_zm

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-22

• #7

这些我都做到了（当然少不了卷卷的帮助），如果要判断点是否在不规则图形里，你就得先
将这个图形看成一个多边形，象卷说的一样用PtInRegion来判断。如果是不规则线段的话你就把它
看成折线，分解成若干个直线来判断（我是用这种方法），判断点在直线上就不用说了，用直线方程。
上次卷告诉了我如何判断点在曲线上的方法，我想这种用法在不规则线段中也能用，只是要改动一下，
卷你说是不是，去看看这个吧：
http://www.delphibbs.com/delphibbs/dispq.asp?lid=909443
这个里面有卷给我的回答，和我自己改动过的C++ BUILDER函数

 

的

的士

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-22

• #8

有没有相关的书籍介绍呀。

 

卷

卷起千堆雪tyn

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-22

• #9

书籍？
书籍才不会讲解这种实际的问题呢；书上都是理论的东东，很难看懂的。

 

的

的士

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-23

• #10

ugvanxk:
我用你的方法怎么太不准呀，看看代码有没有错。
function TLine.PointIsInside(APoint: TPoint): Boolean;
begin
Result := Abs((FEndPoint.Y - FBeginPoint.Y) * APoint.X +
(FBeginPoint.X - FEndPoint.X) * APoint.Y +
FEndPoint.X * FBeginPoint.Y - FBeginPoint.X - FEndPoint.Y) /
Sqrt(Sqr(FEndPoint.Y- FBeginPoint.Y) + Sqr(FBeginPoint.X -FEndPoint.X)) < 4;
end;

 

吕

吕雪松

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-23

• #11

原理：
1，点在直线上：点到直线的垂直距离是否为小于最小阈值。如果是判断点是否在线段内则
求垂足是否在线段内。
function IsPtAtLine(X,Y : Double;PtList : TList;OffSet : double) : Boolean;
var
TX1,TY1,TX2,TY2,VX1,VY1,LL : double; {交点}
An1,An2 : double; {角度}
I : integer;
GeoPt : PGeoPoint;
begin;
result := FALSE;
for I := 0 to PtList.Count - 2 do begin
GeoPt := PGeoPoint(PtList.Items);
TX1 := GeoPt^.X;
TY1 := GeoPt^.Y;
GeoPt := PGeoPoint(PtList.Items[I + 1]);
TX2 := GeoPt^.X;
TY2 := GeoPt^.Y;
if IsPtInRect(X,Y,TX1,TY1,TX2,TY2) then begin
An1 := GetDirection(TX1,TY1,X,Y);
An2 := GetDirection(TX1,TY1,TX2,TY2);

if Abs(Sin(An1 - An2) * GetLength(TX1,TY1,X,Y)) < Offset then begin
result := TRUE;
Exit;
end;
end
else begin
if Abs(TX1 - TX2) < Offset then begin
if (Y > GetMin(TY1,TY2)) and (Y < GetMax(TY1,TY2)) and (Abs(X - TX1) < Offset) then begin
result := TRUE;
exit;
end;
end;
if Abs(TY1 - TY2) < Offset then begin
if (X > GetMin(TX1,TX2)) and (X < GetMax(TX1,TX2)) and (Abs(Y - TY1) < Offset) then begin
result := TRUE;
exit;
end;
end;
end;
end;
end;

2，点是否在多边形内：过此点的直线同多边形的一侧交点数是否为奇数。
function IsPtInRegion(X,Y : Double;PtList : TList) : Boolean;
var
TX1,TY1,TX2,TY2 : double; {交点}
I : integer;
LCount,RCount : integer; {射线左右交点个数}
XX,YY : double;
GeoPt : PGeoPoint;
begin
LCount := 0;
RCount := 0;
for I := 0 to PtList.Count - 2 do begin
GeoPt := PGeoPoint(PtList.items);
TX1 := GeoPt^.X;
TY1 := GeoPt^.Y;
GeoPt := PGeoPoint(PtList.items[I + 1]);
TX2 := GeoPt^.X;
TY2 := GeoPt^.Y;

GetIntersectedPoint(X - 10,Y,X,Y,TX1,TY1,TX2,TY2,XX,YY,2);
if (XX < X) and IsPtInRect(XX,YY,TX1,TY1,TX2,TY2) then Inc(LCount);
end;
if (LCount Mod 2) <> 0 then Result := TRUE else Result := FALSE;
end;

其中TList中的数据类型为：
PGeoPoint = ^TGeoPoint;
TGeoPoint = record
X,Y : double;
end;
//获得X1,Y1,X2,Y2的交点，无交点时返回FALSE,Flag为1时交点必须位于两个矩形交叉区域内，Flag为2时交点为广义交点，即直线的延长线有效
//注意：Flag为2时前四个参数一定为剪切线}
function GetIntersectedPoint(X1,Y1,X2,Y2,X3,Y3,X4,Y4 : Double;var XX,YY : double;Flag : integer):Boolean;
var
K1,K2,B1,B2 : double; {二条直线的斜率}
V1,V2 : Boolean; {有斜率为无穷大的线存在}
// V1,V2 : integer; {1 :初始值,2:TRUE, 3 : FALSE}
begin
//X1,Y1,X2,Y2 为第一条直线,X3,Y3,X4,Y4 为第二条直线}
V1 := FALSE;
V2 := FALSE;

K1 := 1.7 * 10e308;
K2 := 5 * 10 - 324;
B1 := K1;
B2 := K2;
if Abs(X2-X1)>0.00000000001 then begin
K1 := (Y2-Y1)/(X2-X1);
B1 := Y1-K1*X1;
end
else begin
XX := X1;
V1 := TRUE;
end;

if Abs(X4-X3)>0.00000000001 then begin
K2 := (Y4-Y3)/(X4-X3);
B2 := Y3-K2*X3;
end
else begin
XX := X3;
V2 := TRUE;
end;


if (Abs(K1 - K2) < 0.000000000000001) or (V1 and V2) then begin
Result := FALSE;
Exit;
end;

if (not V1) and (not V2) then begin
XX := (B1-B2)/(K2-K1);
YY := K1*XX+B1;
end
else if V2 then begin
YY := K1*XX+B1;
end else begin
YY := K2*XX+B2;
end;

if Flag = 1 then begin
//如果计算出来的交点位于两个矩形的公共区域，则为真交点}
if (IsPtInRect(XX,YY,X1,Y1,X2,Y2)) and (IsPtInRect(XX,YY,X3,Y3,X4,Y4)) then
result := TRUE
else
result := FALSE;
end
else
if Flag = 2 then begin
if (IsPtInRect(XX,YY,X3,Y3,X4,Y4)) then
result := TRUE
else
result := FALSE;
end;
end;
function IsPtInRect(X, Y: Double; X1,Y1,X2,Y2 : double):Boolean;
const
Buf : double = 10e-10;
begin
Result := (X > MinValue([X1,X2])- Buf) and (X < MaxValue([X1,X2]) + Buf) and (Y > MinValue([Y1,Y2]) - Buf) and (Y < MaxValue([Y1,Y2]) + Buf);
end;

：：

 

的

的士

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-03-24

• #12

多人接受答案了。

 

W

windFo

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-04-18

• #13

谢谢