incorrect intersection between parallel but non-intersecting polygons

40 views
Skip to first unread message

Noah Toyonaga

unread,
Aug 8, 2020, 4:08:06 AM8/8/20
to sage-devel
Hello,

I have found that sage finds a non-zero intersection between polygons when they are parallel but non-intersecting. A reproducible example:
```
# Define parallel polygons.
a = Polyhedron([[0, -1, 1], [1, -1, 1], [1, 1, -1]])
b = Polyhedron([[0.0, -0.5, 1.5], [1.0, -0.5, 1.5], [1.0, 1.5, -0.5]])

# Intersection.
c = a.intersection(b)

# c -> 
# `A 2-dimensional polyhedron in RDF^3 defined as the convex hull of 3
# vertices (use the .plot() method to plot)`

a.plot(fill='green') + b.plot(fill='red') + c.plot(fill='orange')
```

However, when the polygons are made non-parallel the correct answer (zero intersection) is found.

```
# Define parallel polygons.
a = Polyhedron([[0, -1, 1], [1, -1, 1], [1, 1, -1]])
b = Polyhedron([[0.0, -0.15, 1.5], [1.0, -0.5, 1.5], [1.0, 1.5, -0.5]])

# Intersection.
c = a.intersection(b)

# c -> 
# `The empty polyhedron in RDF^3 (use the .plot() method to plot)

a.plot(fill='green') + b.plot(fill='red') + c.plot(fill='orange')
```

Noah

Vincent Delecroix

unread,
Aug 8, 2020, 6:24:37 AM8/8/20
to sage-...@googlegroups.com
Hello,

This is definitely a bug. Thanks for the report. I opened
the ticket #30319 to track the issue, see

https://trac.sagemath.org/ticket/30319

Note that if you use rational coordinates, it looks fine. With

a = Polyhedron([[0, -1, 1], [1, -1, 1], [1, 1, -1]])
b = Polyhedron([[0, -1/2, 3/2], [1, -1/2, 3/2], [1, 3/2, -1/2]])
c = a.intersection(b)

the polyhedron c is empty.

Best
Vincent

Samuel Lelievre

unread,
Aug 9, 2020, 8:36:57 AM8/9/20
to sage-devel
Thanks Noah for the report here and at

- Ask Sage question 52910: Unexpected intersection between parallel polygons

Thanks Vincent for opening a ticket!
Reply all
Reply to author
Forward
0 new messages