Opened 5 years ago

Closed 12 months ago

#23427 closed defect (fixed)

Fix intersection of hyperbolic geodesic arcs

Reported by: Vincent Delecroix Owned by:
Priority: major Milestone: sage-9.5
Component: geometry Keywords: bug
Cc: Javier Honrubia González, Samuel Lelièvre Merged in:
Authors: Javier Honrubia González Reviewers: Vincent Delecroix, Dave Morris, Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: f3dc878 (Commits, GitHub, GitLab) Commit: f3dc8781bfdedf9d269cdea65eead6d67d5b40f1
Dependencies: Stopgaps:

Status badges

Description (last modified by Samuel Lelièvre)

The following geodesic arcs do not intersect but Sage still gives an intersection point.

sage: UHP = HyperbolicPlane().UHP()
sage: g1 = UHP.get_geodesic(2*QQbar.gen(), 5)
sage: g2 = UHP.get_geodesic(-1/2, Infinity)
sage: g1.intersection(g2)
[Point in UHP -0.500000000000000? + 1.284523257866513?*I]

Change History (29)

comment:1 Changed 5 years ago by Javier Honrubia González

It seems easy. Checking that the real part of the fixed point of both involutions lies between the real part of endpoints of both geodesics,would be a fast implementation. Are you going to tackle this? I have time these days to code it.

comment:2 Changed 5 years ago by Javier Honrubia González

Branch: u/jhonrubia6/intersection_of_hyperbolic_geodesics_is_wrong

comment:3 Changed 5 years ago by Javier Honrubia González

Authors: Javier Honrubia González
Commit: 3f2878194efe7adb432c655c2afcda70c7e33e13
Status: newneeds_review

New commits:

3f28781Bug corrected. Some examples on perpendicular_bisector() modified as to pass tests

comment:4 Changed 5 years ago by Vincent Delecroix

What about vertical geodesics?

comment:5 in reply to:  4 Changed 5 years ago by Vincent Delecroix

Status: needs_reviewneeds_work

Replying to vdelecroix:

What about vertical geodesics?

More precisely

sage: UHP = HyperbolicPlane().UHP()
sage: g1 = UHP.get_geodesic(I, 2*I)
sage: g2 = UHP.get_geodesic(I/2, 4*I)
sage: g3 = UHP.get_geodesic(3*I, 4*I)
sage: g1.intersection(g2)
[Boundary point in UHP +Infinity, Boundary point in UHP 0]
sage: g1.intersection(g3)
[Boundary point in UHP +Infinity, Boundary point in UHP 0]

comment:6 Changed 5 years ago by Javier Honrubia González

we also need to correct

sage: UHP = HyperbolicPlane().UHP()
sage: g1=UHP.get_geodesic(-1,+1)
sage: g2=UHP.get_geodesic(-1,-1+2*I)
sage: g1.intersection(g2)
[]

should return

[Boundary point in UHP -1]

and

UHP = HyperbolicPlane().UHP()
g1=UHP.get_geodesic(-1,I)
g2=UHP.get_geodesic(+1,(+cos(pi/3)+I*sin(pi/3)))
[Boundary point in UHP -1, Boundary point in UHP 1]

should return []

What should be the correct answer of the function in the following case?

UHP = HyperbolicPlane().UHP()
g1=UHP.get_geodesic(I,3*I)
g2=UHP.get_geodesic(2*I,4*I)

Maybe

[2*I,3*I]

or

Geodesic in UHP from 2*I to 3*I
Last edited 5 years ago by Javier Honrubia González (previous) (diff)

comment:7 in reply to:  6 Changed 5 years ago by Vincent Delecroix

Replying to jhonrubia6:

<SNIP>

What should be the correct answer of the function in the following case?

UHP = HyperbolicPlane().UHP()
g1=UHP.get_geodesic(I,3*I)
g2=UHP.get_geodesic(2*I,4*I)

Maybe

[2*I,3*I]

definitely not

or

Geodesic in UHP from 2*I to 3*I

Much better

comment:8 Changed 13 months ago by git

Commit: 3f2878194efe7adb432c655c2afcda70c7e33e133a07c7e7ceb2cc66f46d96b1f90b7bd574e52640

Branch pushed to git repo; I updated commit sha1. New commits:

150a482Merge remote-tracking branch 'origin/master' into t/23427/intersection_of_hyperbolic_geodesics_is_wrong
3a07c7einteresection() heavily modified to account for all different cases.

comment:9 Changed 13 months ago by Samuel Lelièvre

Ideally, work on top of the develop branch (currently Sage 9.5.beta6) rather than master.

comment:10 Changed 13 months ago by Samuel Lelièvre

Cc: Samuel Lelièvre added
Description: modified (diff)
Milestone: sage-8.1sage-9.5
Summary: intersection of hyperbolic geodesics is wrongFix intersection of hyperbolic geodesic arcs

comment:11 in reply to:  9 Changed 13 months ago by Javier Honrubia González

Replying to slelievre:

Ideally, work on top of the develop branch (currently Sage 9.5.beta6) rather than master.

Right, I've just noticed, I merge with develop and re-submit

comment:12 Changed 13 months ago by git

Commit: 3a07c7e7ceb2cc66f46d96b1f90b7bd574e52640715cbac82d2480b8f4cef5636ce31a58ddfb0282

Branch pushed to git repo; I updated commit sha1. New commits:

df1ed36Merge branch 'develop' into t/23427/intersection_of_hyperbolic_geodesics_is_wrong
715cbacmerged with the develop branch. Most issues fixed.

comment:13 Changed 13 months ago by Javier Honrubia González

However an important new bug appeared when dealing with the intersection in the PD model:

sage: g=HyperbolicPlane().PD().random_geodesic()
sage: h = g.perpendicular_bisector().complete()
sage: g.intersection(h)
[]

which is an obvious error. Somehow the problem lies in the abstract method intersection(self, other)

sage: g._cached_geodesic.intersection(h)
[]

whereas

sage: g._cached_geodesic.intersection(h._cached_geodesic)
[Point in UHP -1.27483700342883 + 2.78119562788909*I]

However

sage: g=HyperbolicPlane().PD().random_geodesic()
sage: h = g.perpendicular_bisector().complete()
sage: g.intersection(h)
[Point in UHP 0.815206723839169 + 2.95290895719856*I]

Work in progress

comment:14 Changed 13 months ago by git

Commit: 715cbac82d2480b8f4cef5636ce31a58ddfb028257917b5677c6976112aef0616cd831a25e7e18b9

Branch pushed to git repo; I updated commit sha1. New commits:

57917b5Bug involving intersection models other tha UHP solved.

comment:15 Changed 13 months ago by git

Commit: 57917b5677c6976112aef0616cd831a25e7e18b9b0648b27e31c67536205a4fe9c4e85d66adea382

Branch pushed to git repo; I updated commit sha1. New commits:

b0648b2ll test passed. Bug corrected with asymptotically parallel geodesics

comment:16 Changed 13 months ago by Javier Honrubia González

Status: needs_workneeds_review

comment:17 Changed 13 months ago by Dima Pasechnik

Just merge (or rebase) locally, and push the merged branch.

comment:18 Changed 13 months ago by Dave Morris

Here are the merge conflicts that I see with 9.5b7. They are in the EXAMPLES sections of the two perpendicular_bisector methods.

<<<<<<< HEAD
            sage: h = g.perpendicular_bisector()
            sage: P = g.plot(color='blue')+h.plot(color='orange');P  # optional - sage.plot
=======
            sage: h = g.perpendicular_bisector().complete()
            sage: P = g.plot(color='blue')+h.plot(color='orange');P
>>>>>>> b0648b27e31c67536205a4fe9c4e85d66adea382
<<<<<<< HEAD
            sage: h = g.perpendicular_bisector()
            sage: show(g.plot(color='blue')+h.plot(color='orange'))  # optional - sage.plot
=======
            sage: h = g.perpendicular_bisector().complete()
            sage: show(g.plot(color='blue')+h.plot(color='orange'))
>>>>>>> b0648b27e31c67536205a4fe9c4e85d66adea382

comment:19 Changed 13 months ago by Dima Pasechnik

so just use the lines in HEAD when you resolve the conflict.

comment:20 Changed 13 months ago by Dima Pasechnik

sorry - if these .complete() things are in the ticket's branch the you need to do the obvious editing.

comment:21 Changed 13 months ago by Dave Morris

Status: needs_reviewneeds_work

comment:22 Changed 12 months ago by git

Commit: b0648b27e31c67536205a4fe9c4e85d66adea382398c65da00edd148b74885773c4df4855f76dbec

Branch pushed to git repo; I updated commit sha1. New commits:

398c65dmerged with develop. Conflicts in EXAMPLES fixed

comment:23 Changed 12 months ago by Javier Honrubia González

Status: needs_workneeds_review

comment:24 Changed 12 months ago by Dima Pasechnik

Status: needs_reviewneeds_work

clean up is needed:

% tox -e pycodestyle --  src/sage/geometry/hyperbolic_space/hyperbolic_geodesic.py
pycodestyle recreate: /Users/dima/sage/.tox/src
pycodestyle run-test-pre: PYTHONHASHSEED='3653170419'
pycodestyle run-test: commands[0] | tox -c /Users/dima/sage/src/tox.ini -e pycodestyle -- src/sage/geometry/hyperbolic_space/hyperbolic_geodesic.py
pycodestyle create: /Users/dima/sage/src/.tox/pycodestyle
pycodestyle installdeps: pycodestyle
pycodestyle installed: pycodestyle==2.8.0
pycodestyle run-test-pre: PYTHONHASHSEED='400015120'
pycodestyle run-test: commands[0] | pycodestyle sage/geometry/hyperbolic_space/hyperbolic_geodesic.py
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1043:1: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1045:1: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1155:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1358:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1388:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1395:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1401:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1407:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1413:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1419:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1425:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1431:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1443:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1449:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1455:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1460:25: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1462:9: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1467:9: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1468:9: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1469:42: E261 at least two spaces before inline comment
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1469:43: E262 inline comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1470:20: E231 missing whitespace after ','
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1470:43: W291 trailing whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1473:24: E231 missing whitespace after ','
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1474:9: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1475:9: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1477:20: E231 missing whitespace after ','
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1480:24: E231 missing whitespace after ','
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1483:23: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1483:42: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1486:17: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1488:21: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1489:28: E231 missing whitespace after ','
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1489:46: E231 missing whitespace after ','
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1491:25: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1494:52: E231 missing whitespace after ','
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1494:59: E261 at least two spaces before inline comment
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1494:60: E262 inline comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1495:34: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1500:17: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1501:17: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1502:34: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1503:28: E231 missing whitespace after ','
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1505:25: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1507:34: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1512:13: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1513:13: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1514:30: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1515:24: E231 missing whitespace after ','
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1518:17: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1532:21: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1533:29: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1537:42: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1537:52: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1537:85: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1537:95: E225 missing whitespace around operator
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:1874:1: W293 blank line contains whitespace
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:2031:13: E741 ambiguous variable name 'I'
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:2036:13: E741 ambiguous variable name 'I'
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:2143:1: E265 block comment should start with '# '
sage/geometry/hyperbolic_space/hyperbolic_geodesic.py:2145:1: E265 block comment should start with '# '
14      E225 missing whitespace around operator
9       E231 missing whitespace after ','
2       E261 at least two spaces before inline comment
2       E262 inline comment should start with '# '
17      E265 block comment should start with '# '
2       E741 ambiguous variable name 'I'
1       W291 trailing whitespace
14      W293 blank line contains whitespace
ERROR: InvocationError for command /Users/dima/sage/src/.tox/pycodestyle/bin/pycodestyle sage/geometry/hyperbolic_space/hyperbolic_geodesic.py (exited with code 1)
______________________________ summary _______________________________
ERROR:   pycodestyle: commands failed
ERROR: InvocationError for command /usr/local/bin/tox -c src/tox.ini -e pycodestyle -- src/sage/geometry/hyperbolic_space/hyperbolic_geodesic.py (exited with code 1)

all of these except E741 can be trivially fixed. (Leave E741 as is).

comment:25 Changed 12 months ago by git

Commit: 398c65da00edd148b74885773c4df4855f76dbecf3dc8781bfdedf9d269cdea65eead6d67d5b40f1

Branch pushed to git repo; I updated commit sha1. New commits:

f3dc878Clean up done leaving E741

comment:26 Changed 12 months ago by Javier Honrubia González

Status: needs_workneeds_review

comment:27 Changed 12 months ago by Dima Pasechnik

Reviewers: Dima Pasechnik
Status: needs_reviewpositive_review

OK, good.

comment:28 Changed 12 months ago by Samuel Lelièvre

Reviewers: Dima PasechnikVincent Delecroix, Dave Morris, Dima Pasechnik

comment:29 Changed 12 months ago by Volker Braun

Branch: u/jhonrubia6/intersection_of_hyperbolic_geodesics_is_wrongf3dc8781bfdedf9d269cdea65eead6d67d5b40f1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.