BrowserUk:
Sorry, I should've been more clear. I wasn't referring to the vertices, but the input points to the algorithm. So the diagonal line going through two of the points are the bisector for the other two corners. I put this case into the algorithm (just a few minutes ago):
my @points = ( [0,0], [2, 0], [0, 2], [2, 2] );
Yields the following lines:
[
[1, 0, 1, 0, 1], # X=1 for points 0, 1
[0, 1, 1, 0, 2], # Y=1 for points 0, 2
[0, 1, 1, 1, 3], # Y=1 for points 1, 3
[1, 1, 2, 0, 3], # X+Y=2 for points 0, 3
[1, 0, 1, 2, 3], # X=1 for points 2, 3
]
That fourth entry is the diagonal I was talking about. It's clearly the bisector for points 0 and 3, but since it intersects at the same point as the first two, it's irrelevant. Looking at the edge list:
[
[3, 1, 0], # Edge from (1,1) to (1,1)
[1, -1, 1],
[4, -1, 1],
[2, 0, -1],
[0, 0, -1]
]
Other than the first edge, the rest are as you'd expect to see. I'm suspecting some odd comparison (or roundoff) in the C code to be generating that 0-length segment.
Just for completeness, here's the list of vertices:
[
[1, 1],
[1, 1]
]
Looking at the results, I'm struck by a couple items:
- Some lines are identical, except for the point pairs they were generated from.
- Only one of the diagonal lines is generated, which is why I suspect roundoff or an odd conditional.
- It might be worthwhile to add disallow duplicate vertices and/or edges of zero length.
...roboticus
Update: I just tried the cross that you suggested, and the data showed *absolutely no* anomalies....odd!
Update: Fixed HTML (missed closer for UL). |