[PATCH] Add overlaps geometric operators that ignore point overlaps

Started by Ankit Kumar Pandeyabout 3 years ago2 messages

Ankit Kumar Pandey

itsankitkp@gmail.com

about 3 years ago

1 attachment(s)

Hi,

This is patch for todo item: Add overlaps geometric operators that
ignore point overlaps

Issue:

SELECT circle '((0,0), 1)' && circle '((2,0),1) returns True

Expectation: In above case, both figures touch other but do not overlap
(i.e. touching != overlap). Hence, it should return false.

Cause:

Less than or equal check between distance of center and sum of radius

Datum
circle_overlap(PG_FUNCTION_ARGS)
{
CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);

PG_RETURN_BOOL(FPle(point_dt(&circle1->center, &circle2->center),
float8_pl(circle1->radius, circle2->radius)));
}

Possible fix:

# Don't check for <= , just < would suffice.

Datum
circle_overlap(PG_FUNCTION_ARGS)
{
CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);

PG_RETURN_BOOL(FPlt(point_dt(&circle1->center, &circle2->center),
float8_pl(circle1->radius, circle2->radius)));
}

same for boxes as well.

Results:

Before:

select box '((0,0),(1,1))' && box '((0,1), (1,2))';
?column?
----------
t
(1 row)

With patch:

select box '((0,1),(1,1))' && box '((1,1), (1,2))';
?column?
----------
f
(1 row)

Bring box slightly ( > EPSILON) inside the other box

select box '((0,0),(1,1.0001))' && box '((0,1), (1,2))';
?column?
----------
t
(1 row)

similar for circle.

Now, as per as discussion
(/messages/by-id/20100322175532.GG26428@fetter.org)
and corresponding change in docs,
https://www.postgresql.org/docs/15/functions-geometry.html, it mentions

`Do these objects overlap? (One point in common makes this true.) `.
Does this means current behavior is correct? Or do we still need the
proposed change (if so, with proper updates in docs)?

If current behavior is correct, this todo item might need some update
(unless I missed anything) otherwise any suggestion is welcomed.

Also, I did some search around this and there is general sense of
differentiation between overlap and touch of geometric figures. I am not
able to find any function which can determine if two geometric figures
touch each

other at a point (and if there is real use case of this).

In any case, patch attached for a reference. Any feedback is welcomed.

--
Regards,
Ankit Kumar Pandey

Attachments:

v1-0001-ignore-point-overlap-operation.patchtext/x-patch; charset=UTF-8; name=v1-0001-ignore-point-overlap-operation.patchDownload

From 1c180b50493c416d063bca9ed0a1669c2b1b191d Mon Sep 17 00:00:00 2001
From: Ankit Kumar Pandey <itsankitkp@gmail.com>
Date: Sun, 1 Jan 2023 00:25:06 +0530
Subject: [PATCH] Ignore point overlap operation

Geometric figure does not overlap if they just
touch each other. This patch removes requirement of point overlap for
overlap condition.
---
 doc/src/sgml/func.sgml          |  2 +-
 src/backend/utils/adt/geo_ops.c | 10 +++++-----
 2 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml
index 3bf8d021c3..d1abd545a4 100644
--- a/doc/src/sgml/func.sgml
+++ b/doc/src/sgml/func.sgml
@@ -11209,7 +11209,7 @@ CREATE TYPE rainbow AS ENUM ('red', 'orange', 'yellow', 'green', 'blue', 'purple
         <returnvalue>boolean</returnvalue>
        </para>
        <para>
-        Do these objects overlap?  (One point in common makes this true.)
+        Do these objects overlap?  (One point in common does not count as overlap.)
         Available for <type>box</type>, <type>polygon</type>,
         <type>circle</type>.
        </para>
diff --git a/src/backend/utils/adt/geo_ops.c b/src/backend/utils/adt/geo_ops.c
index 86da025906..6a06abfd2c 100644
--- a/src/backend/utils/adt/geo_ops.c
+++ b/src/backend/utils/adt/geo_ops.c
@@ -570,10 +570,10 @@ box_overlap(PG_FUNCTION_ARGS)
 static bool
 box_ov(BOX *box1, BOX *box2)
 {
-	return (FPle(box1->low.x, box2->high.x) &&
-			FPle(box2->low.x, box1->high.x) &&
-			FPle(box1->low.y, box2->high.y) &&
-			FPle(box2->low.y, box1->high.y));
+	return (FPlt(box1->low.x, box2->high.x) &&
+			FPlt(box2->low.x, box1->high.x) &&
+			FPlt(box1->low.y, box2->high.y) &&
+			FPlt(box2->low.y, box1->high.y));
 }
 
 /*		box_left		-		is box1 strictly left of box2?
@@ -4765,7 +4765,7 @@ circle_overlap(PG_FUNCTION_ARGS)
 	CIRCLE	   *circle1 = PG_GETARG_CIRCLE_P(0);
 	CIRCLE	   *circle2 = PG_GETARG_CIRCLE_P(1);
 
-	PG_RETURN_BOOL(FPle(point_dt(&circle1->center, &circle2->center),
+	PG_RETURN_BOOL(FPlt(point_dt(&circle1->center, &circle2->center),
 						float8_pl(circle1->radius, circle2->radius)));
 }
 
-- 
2.37.2

Kyotaro Horiguchi

horikyota.ntt@gmail.com

about 3 years ago

In reply to: Ankit Kumar Pandey (#1)

Re: [PATCH] Add overlaps geometric operators that ignore point overlaps

Hello.

At Sun, 1 Jan 2023 01:13:24 +0530, Ankit Kumar Pandey <itsankitkp@gmail.com> wrote in

This is patch for todo item: Add overlaps geometric operators that
ignore point overlaps

Issue:

SELECT circle '((0,0), 1)' && circle '((2,0),1) returns True

Expectation: In above case, both figures touch other but do not
overlap (i.e. touching != overlap). Hence, it should return false.

This may be slightly off from the common definition in other geometric
processing systems, it is the established behavior of PostgreSQL that
should already have users.

About the behavior itself, since it seems to me that the words "touch"
and "overlap" have no rigorous mathematical definitions, that depends
on definition. The following discussion would be mere a word play..

If circle ((0,0),1) means a circumference, i.e. a set of points
described as "x^2 + y^2 = 1" (or it may be a disc containing the area
inside (<=) here) and "overlap" means "share at least a point", the
two circles are overlapping. This seems to be our current stand point
and what is expressed in the doc.

If it meant the area exclusively inside the outline (i.e. x^2 + y^2 <
1), the two circles could be said touching but not overlapping. Or,
if circle is defined as "(<)= 1" but "overlap" meant "share at least
an area", they could be said not overlapping but touching? (I'm not
sure about the border between a point and an area here and the
distinction would be connected with the annoying EPSILON..) The same
discussion holds for boxes or other shapes.

Now, as per as discussion
(/messages/by-id/20100322175532.GG26428@fetter.org)
and corresponding change in docs,
https://www.postgresql.org/docs/15/functions-geometry.html, it
mentions

`Do these objects overlap? (One point in common makes this true.)
`. Does this means current behavior is correct? Or do we still need
the proposed change (if so, with proper updates in docs)?

If current behavior is correct, this todo item might need some update
(unless I missed anything) otherwise any suggestion is welcomed.

I read the todo description as we may want *another set* of operators
to do that, not to change the current behavior of the existing
operators.

regards.

--
Kyotaro Horiguchi
NTT Open Source Software Center