interactions computed from abstract segments

[smichr]

Unless the following idea is a freshman geometry blunder, I wonder if it might be useful to simply recast all input to integers (and the user would have to provide a function to convert a segment to a tuple of sortable coordinates). The user would be given, in return, a list of interacting segment indices. Here is an example with SymPy

>>> real_world_sides = Polygon((-1,0),(-1,1),(1,-1),(1,1)).rotate(pi/4).sides
>>> real_world_sides[0]
Segment2D(Point2D(-sqrt(2)/2, -sqrt(2)/2), Point2D(-sqrt(2), 0))

converted to tuples of coordinates

>>> tupleseq = [tuple(j.args for j in i.args) for i in real_world_sides]
>>> tupleseq[0]
((-sqrt(2)/2, -sqrt(2)/2), (-sqrt(2), 0))
>>> crossing(tupleseq)
[(1, 3)]

computing the real-world intersection point

>>> real_world_sides[1].intersection(real_world_sides[3])
[Point2D(-sqrt(2)/3, 0)]

The steps of the crossing function are to

1. convert numbers to integers that preserve the same ordering
2. making them canonical so they match the return values of isect
3. calculation of the intersections (which we ignore) and the segments
4. identify the segments with the segment index of the passed segments
5. return pairs of indices for which an intersection is known to exits

def ipts(pts):
    xs = list(sorted(set([i[0] for i in pts])))
    ys = list(sorted(set([i[1] for i in pts])))
    return [(xs.index(i[0]), ys.index(i[1])) for i in pts], (xs, ys)

def isegs(segs):
    pts, m = ipts([c for s in segs for c in s])
    segs = [tuple(pts[i:i+2]) for i in range(0, len(pts) - 1, 2)]
    return segs, m

def crossing(segments):
    recast, _ = isegs(segments)
    # make canonical
    recast = [(j, i) if i > j else (i, j) for i, j in recast]
    return [(recast.index(a), recast.index(b)) for _, (a, b) in isect_segments_include_segments(recast)]

{It might also make sense to drop the canonicalization step and to just keep track of the coordinates.}

[ideasman42]

Hi @smichr casting floats to integers (while not common AFAIK) works as long as the sign is never flipped (see this Q&A)

But I'm not sure what problem this solves exactly, since new intersections need to be calculated, this will need to be done in floating point so the results order correctly on the sweep line ~ any issues with float precision here will still apply.

[smichr]

what problem this solves exactly

I'm thinking from the SymPy perspective where exact values are representing coordinates which may be irrational and complicated. By switching to integers all intersections can be computed (quickly) as rationals and there would be no issues with comparison while computing the interacting segments. Afterwards, the exact intersections can be computed once the interacting pairs are known. So in the example I gave, the exact intersection, (-sqrt(2)/3, 0) is found rather than a floating approximation.

[smichr]

It's a freshman blunder.

Here's a set of segments in which there is an intersection:

>>> s
[((0, 0), (1/2, 1)), ((0, 9/8), (3, 0)), ((2, 1), (4, 0))]
>>> isect_segments(s)
[(9/19, 18/19)]

When converted to ordinal pts in x and y they become a set of segments in which there is no intersection.

>>> t
[((0, 0), (1, 1)), ((0, 2), (3, 0)), ((2, 1), (4, 0))]
>>> isect_segments(t)
[]

So getting no intersections in the ordinally remapped segments doesn't tell you whether the original set of segments intersected or not.

Is it true that if there is an intersection in the ordinally remapped set that there must have been an intersection in the original set? Nope:

>>> isect_segments([((0, 0), (4, 3)), ((0, 2), (1, 4/5))])
[]
>>> isect_segments([((0, 0), (2, 3)), ((0, 2), (1, 1))])
[(0.8, 1.2)]