Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2e2a392

Browse files
committed
Fix problems in handling the line data type
According to the source history, the internal format of line data typehas changed, but various functions working with it did were not updatedand thus were producing wrong results.This patch addresses various such issues, in particular:* Reject invalid specification A=B=0 on receive* Reject same points on line_construct_pp()* Fix perpendicular operator when negative values are involved* Avoid division by zero on perpendicular operator* Fix intersection and distance operators when neither A nor B are 1* Return NULL for closest point when objects are parallel* Check whether closest point of line segments is the intersection point* Fix closest point of line segments being on the wrong segmentAside from handling those issues, the patch also aims to make operatorsmore symmetric and less sen to precision loss. The EPSILON interfereswith even minor changes, but the least we can do is applying it to bothsides of the operators equally.Author: Emre HasegeliReviewed-by: Tomas VondraDiscussion:https://www.postgresql.org/message-id/CAE2gYzxF7-5djV6-cEvqQu-fNsnt%3DEqbOURx7ZDg%2BVv6ZMTWbg%40mail.gmail.com
1 parentf535d5f commit2e2a392

File tree

1 file changed

+108
-50
lines changed

1 file changed

+108
-50
lines changed

‎src/backend/utils/adt/geo_ops.c

Lines changed: 108 additions & 50 deletions
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,7 @@ static intpoint_inside(Point *p, int npts, Point *plist);
4848

4949
/* Routines for lines */
5050
staticinlinevoidline_construct(LINE*result,Point*pt,float8m);
51+
staticinlinefloat8line_sl(LINE*line);
5152
staticinlinefloat8line_invsl(LINE*line);
5253
staticboolline_interpt_line(Point*result,LINE*l1,LINE*l2);
5354
staticboolline_contain_point(LINE*line,Point*point);
@@ -980,6 +981,11 @@ line_recv(PG_FUNCTION_ARGS)
980981
line->B=pq_getmsgfloat8(buf);
981982
line->C=pq_getmsgfloat8(buf);
982983

984+
if (FPzero(line->A)&&FPzero(line->B))
985+
ereport(ERROR,
986+
(errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
987+
errmsg("invalid line specification: A and B cannot both be zero")));
988+
983989
PG_RETURN_LINE_P(line);
984990
}
985991

@@ -1040,6 +1046,11 @@ line_construct_pp(PG_FUNCTION_ARGS)
10401046
Point*pt2=PG_GETARG_POINT_P(1);
10411047
LINE*result= (LINE*)palloc(sizeof(LINE));
10421048

1049+
if (point_eq_point(pt1,pt2))
1050+
ereport(ERROR,
1051+
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
1052+
errmsg("invalid line specification: must be two distinct points")));
1053+
10431054
line_construct(result,pt1,point_sl(pt1,pt2));
10441055

10451056
PG_RETURN_LINE_P(result);
@@ -1076,11 +1087,15 @@ line_perp(PG_FUNCTION_ARGS)
10761087

10771088
if (FPzero(l1->A))
10781089
PG_RETURN_BOOL(FPzero(l2->B));
1079-
elseif (FPzero(l1->B))
1090+
if (FPzero(l2->A))
1091+
PG_RETURN_BOOL(FPzero(l1->B));
1092+
if (FPzero(l1->B))
10801093
PG_RETURN_BOOL(FPzero(l2->A));
1094+
if (FPzero(l2->B))
1095+
PG_RETURN_BOOL(FPzero(l1->A));
10811096

1082-
PG_RETURN_BOOL(FPeq(float8_div(float8_mul(l1->A,l2->B),
1083-
float8_mul(l1->B,l2->A)),-1.0));
1097+
PG_RETURN_BOOL(FPeq(float8_div(float8_mul(l1->A,l2->A),
1098+
float8_mul(l1->B,l2->B)),-1.0));
10841099
}
10851100

10861101
Datum
@@ -1135,6 +1150,20 @@ line_eq(PG_FUNCTION_ARGS)
11351150
*Line arithmetic routines.
11361151
*---------------------------------------------------------*/
11371152

1153+
/*
1154+
* Return slope of the line
1155+
*/
1156+
staticinlinefloat8
1157+
line_sl(LINE*line)
1158+
{
1159+
if (FPzero(line->A))
1160+
return0.0;
1161+
if (FPzero(line->B))
1162+
returnDBL_MAX;
1163+
returnfloat8_div(line->A,-line->B);
1164+
}
1165+
1166+
11381167
/*
11391168
* Return inverse slope of the line
11401169
*/
@@ -1157,16 +1186,21 @@ line_distance(PG_FUNCTION_ARGS)
11571186
{
11581187
LINE*l1=PG_GETARG_LINE_P(0);
11591188
LINE*l2=PG_GETARG_LINE_P(1);
1160-
float8result;
1161-
Pointtmp;
1189+
float8ratio;
11621190

11631191
if (line_interpt_line(NULL,l1,l2))/* intersecting? */
11641192
PG_RETURN_FLOAT8(0.0);
1165-
if (FPzero(l1->B))/* vertical? */
1166-
PG_RETURN_FLOAT8(fabs(float8_mi(l1->C,l2->C)));
1167-
point_construct(&tmp,0.0,l1->C);
1168-
result=line_closept_point(NULL,l2,&tmp);
1169-
PG_RETURN_FLOAT8(result);
1193+
1194+
if (!FPzero(l1->A)&& !isnan(l1->A)&& !FPzero(l2->A)&& !isnan(l2->A))
1195+
ratio=float8_div(l1->A,l2->A);
1196+
elseif (!FPzero(l1->B)&& !isnan(l1->B)&& !FPzero(l2->B)&& !isnan(l2->B))
1197+
ratio=float8_div(l1->B,l2->B);
1198+
else
1199+
ratio=1.0;
1200+
1201+
PG_RETURN_FLOAT8(float8_div(fabs(float8_mi(l1->C,
1202+
float8_mul(ratio,l2->C))),
1203+
HYPOT(l1->A,l1->B)));
11701204
}
11711205

11721206
/* line_interpt()
@@ -1207,27 +1241,36 @@ line_interpt_line(Point *result, LINE *l1, LINE *l2)
12071241
float8x,
12081242
y;
12091243

1210-
if (FPzero(l1->B))/* l1 vertical? */
1244+
if (!FPzero(l1->B))
12111245
{
1212-
if (FPzero(l2->B))/* l2 vertical? */
1246+
if (FPeq(l2->A,float8_mul(l1->A,float8_div(l2->B,l1->B))))
12131247
return false;
12141248

1215-
x=l1->C;
1216-
y=float8_pl(float8_mul(l2->A,x),l2->C);
1217-
}
1218-
elseif (FPzero(l2->B))/* l2 vertical? */
1219-
{
1220-
x=l2->C;
1221-
y=float8_pl(float8_mul(l1->A,x),l1->C);
1249+
x=float8_div(float8_mi(float8_mul(l1->B,l2->C),
1250+
float8_mul(l2->B,l1->C)),
1251+
float8_mi(float8_mul(l1->A,l2->B),
1252+
float8_mul(l2->A,l1->B)));
1253+
y=float8_div(-float8_pl(float8_mul(l1->A,x),l1->C),l1->B);
12221254
}
1223-
else
1255+
elseif (!FPzero(l2->B))
12241256
{
1225-
if (FPeq(l2->A,float8_mul(l1->A,float8_div(l2->B,l1->B))))
1257+
if (FPeq(l1->A,float8_mul(l2->A,float8_div(l1->B,l2->B))))
12261258
return false;
12271259

1228-
x=float8_div(float8_mi(l1->C,l2->C),float8_mi(l2->A,l1->A));
1229-
y=float8_pl(float8_mul(l1->A,x),l1->C);
1260+
x=float8_div(float8_mi(float8_mul(l2->B,l1->C),
1261+
float8_mul(l1->B,l2->C)),
1262+
float8_mi(float8_mul(l2->A,l1->B),
1263+
float8_mul(l1->A,l2->B)));
1264+
y=float8_div(-float8_pl(float8_mul(l2->A,x),l2->C),l2->B);
12301265
}
1266+
else
1267+
return false;
1268+
1269+
/* On some platforms, the preceding expressions tend to produce -0. */
1270+
if (x==0.0)
1271+
x=0.0;
1272+
if (y==0.0)
1273+
y=0.0;
12311274

12321275
if (result!=NULL)
12331276
point_construct(result,x,y);
@@ -2347,16 +2390,8 @@ dist_sl(PG_FUNCTION_ARGS)
23472390
{
23482391
LSEG*lseg=PG_GETARG_LSEG_P(0);
23492392
LINE*line=PG_GETARG_LINE_P(1);
2350-
float8result;
2351-
2352-
if (lseg_interpt_line(NULL,lseg,line))
2353-
result=0.0;
2354-
else
2355-
/* XXX shouldn't we take the min not max? */
2356-
result=float8_max(line_closept_point(NULL,line,&lseg->p[0]),
2357-
line_closept_point(NULL,line,&lseg->p[1]));
23582393

2359-
PG_RETURN_FLOAT8(result);
2394+
PG_RETURN_FLOAT8(lseg_closept_line(NULL,lseg,line));
23602395
}
23612396

23622397
/*
@@ -2533,20 +2568,26 @@ lseg_interpt_line(Point *result, LSEG *lseg, LINE *line)
25332568
staticfloat8
25342569
line_closept_point(Point*result,LINE*line,Point*point)
25352570
{
2536-
boolretvalPG_USED_FOR_ASSERTS_ONLY;
2537-
Pointclosept;
2571+
Pointclosept;
25382572
LINEtmp;
25392573

2540-
/* We drop a perpendicular to find the intersection point. */
2574+
/*
2575+
* We drop a perpendicular to find the intersection point. Ordinarily
2576+
* we should always find it, but that can fail in the presence of NaN
2577+
* coordinates, and perhaps even from simple roundoff issues.
2578+
*/
25412579
line_construct(&tmp,point,line_invsl(line));
2542-
retval=line_interpt_line(&closept,line,&tmp);
2580+
if (!line_interpt_line(&closept,&tmp,line))
2581+
{
2582+
if (result!=NULL)
2583+
*result=*point;
25432584

2544-
Assert(retval);/* perpendicular lines always intersect */
2585+
returnget_float8_nan();
2586+
}
25452587

25462588
if (result!=NULL)
25472589
*result=closept;
25482590

2549-
/* Then we calculate the distance between the points. */
25502591
returnpoint_dt(&closept,point);
25512592
}
25522593

@@ -2620,27 +2661,38 @@ lseg_closept_lseg(Point *result, LSEG *l1, LSEG *l2)
26202661
float8dist,
26212662
d;
26222663

2623-
d=lseg_closept_point(NULL,l1,&l2->p[0]);
2624-
dist=d;
2625-
if (result!=NULL)
2626-
*result=l2->p[0];
2664+
/* First, we handle the case when the line segments are intersecting. */
2665+
if (lseg_interpt_lseg(result,l1,l2))
2666+
return0.0;
26272667

2628-
d=lseg_closept_point(NULL,l1,&l2->p[1]);
2668+
/*
2669+
* Then, we find the closest points from the endpoints of the second
2670+
* line segment, and keep the closest one.
2671+
*/
2672+
dist=lseg_closept_point(result,l1,&l2->p[0]);
2673+
d=lseg_closept_point(&point,l1,&l2->p[1]);
26292674
if (float8_lt(d,dist))
26302675
{
26312676
dist=d;
26322677
if (result!=NULL)
2633-
*result=l2->p[1];
2678+
*result=point;
26342679
}
26352680

2636-
if (float8_lt(lseg_closept_point(&point,l2,&l1->p[0]),dist))
2637-
d=lseg_closept_point(result,l1,&point);
2638-
2639-
if (float8_lt(lseg_closept_point(&point,l2,&l1->p[1]),dist))
2640-
d=lseg_closept_point(result,l1,&point);
2641-
2681+
/* The closest point can still be one of the endpoints, so we test them. */
2682+
d=lseg_closept_point(NULL,l2,&l1->p[0]);
2683+
if (float8_lt(d,dist))
2684+
{
2685+
dist=d;
2686+
if (result!=NULL)
2687+
*result=l1->p[0];
2688+
}
2689+
d=lseg_closept_point(NULL,l2,&l1->p[1]);
26422690
if (float8_lt(d,dist))
2691+
{
26432692
dist=d;
2693+
if (result!=NULL)
2694+
*result=l1->p[1];
2695+
}
26442696

26452697
returndist;
26462698
}
@@ -2652,6 +2704,9 @@ close_lseg(PG_FUNCTION_ARGS)
26522704
LSEG*l2=PG_GETARG_LSEG_P(1);
26532705
Point*result;
26542706

2707+
if (lseg_sl(l1)==lseg_sl(l2))
2708+
PG_RETURN_NULL();
2709+
26552710
result= (Point*)palloc(sizeof(Point));
26562711

26572712
if (isnan(lseg_closept_lseg(result,l2,l1)))
@@ -2826,6 +2881,9 @@ close_ls(PG_FUNCTION_ARGS)
28262881
LSEG*lseg=PG_GETARG_LSEG_P(1);
28272882
Point*result;
28282883

2884+
if (lseg_sl(lseg)==line_sl(line))
2885+
PG_RETURN_NULL();
2886+
28292887
result= (Point*)palloc(sizeof(Point));
28302888

28312889
if (isnan(lseg_closept_line(result,lseg,line)))

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp