fix polygon_crossing issue with collinear edge

[deboc]

I found some cases where polygon_crossing() misses to label some edges as not visible. The code bellow is an example of failure case before the fix.

I'm not totally sure, but my investigations lead me to conclude that this (co0 and co1) case in polygon_crossing() can solve that out.

import pyvisgraph as vg

# Set obstacles
obstacles = [
    [
        vg.Point(200.00, 50.00),
        vg.Point(200.00, 100.00),
        vg.Point(700.00, 100.00),
        vg.Point(700.00, 50.00)
    ], [
        vg.Point(4.00, 200.00),
        vg.Point(600.00, 200.00),
        vg.Point(600.00, 150.00),
        vg.Point(4.00, 150.00),
        vg.Point(4.00, 0.00),
        vg.Point(0.00, 0.00),
        vg.Point(0.00, 150.00),
        vg.Point(0.00, 200.00),
        vg.Point(0.00, 800.00),
        vg.Point(4.00, 800.00)
    ]
]

# Build path showing issue with polygon_crossing function
g = vg.VisGraph()
g.build(obstacles)
path = g.shortest_path(vg.Point(50, 400), vg.Point(50, 20))
print(path)
print("The edge from Point(0.00, 150.00) to Point(4.00, 150.00) outputed is wrong")

# Display with pygame
import pygame, time, sys

pygame.init()
screen = pygame.display.set_mode((800, 800))
screen.fill(0xFFFFFF)
for poly in obstacles:
    pygame.draw.polygon(screen, 0x000000, [(p.x, p.y) for p in poly])
pygame.draw.lines(screen, 0xFF0000, False, [(p.x, p.y) for p in path], 2)
pygame.display.update()
while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            sys.exit(0)
    time.sleep(0.1)

[TaipanRex]

Seems the issue is with points vg.Point(0.00, 150.00) and vg.Point(0.00, 200.00). These two points are on the line segment from vg.Point(0.00, 0.00) and vg.Point(0.00, 800.00), they are colinear. I'll need to do some debugging to see why your fix works.

[TaipanRex]

I think I know what the problem is now, adding if co0 and co1: continue wont be enough, I will do a write up of the bug in #20, as thats where the issue is.

[TaipanRex]

@deboc, for d8a7fd3, do you have a example where you would end up with an out of bounds value? I would like to add a test case.

[deboc]

Yes sorry I didn't. I will try to find out one. In short, I remember to have encountered a acos(1.00000000001) numerical issue at some point.