pt@geovision.gvc.com (Paul Tomblin) (06/26/91)
I need an algorithm, and if anybody out there has it, or has a book with it, I'd appreciate it. What I need is to find intersections of line, but on a grid. I.e., I have a case where intersections found in vector terms cause problems when the intersection point is snapped to the database resolution. For instance: If you have three lines: 1) (-52,-78)-(52,81) 2) (0,0)-(1,4) 3) (0,0)-(1,3) In vector terms, lines 1 and 3 don't intersect. Niether do 2 and 3, except at (0,0). Lines 1 and 2 intersect at (0.6070, 2.4280). If the database resolution is 1.0, this intersection is snapped to (1,2), which causes line 1 (now (-52,-78)-(1,2)-(52,81)) and line 2 (now (0,0)-(1,2)-(1,4)) to both intersect line 3. Not too nice, since this won't be discovered until parcelize (or overlay) is over, and the points are being added to the database. If lines 1 and 3 are both part of the same polygon, the polygon topology would become invalid! I think the solution would be to ``connect the dots'', and THINK of the lines as being something like: (note: this is internal, not put into the database like this) 1) ...-(0,1)-(0,2)-(1,3)-(1,4)-... 2) (0,0)-(0,1)-(0,2)-(1,3)-(1,4) 3) (0,0)-(0,1)-(1,2)-(1,3) (maybe Breshenham's algorithm would be useful here) Then intersections would be found between 1, 2, and 3, with some coincident portions. After finding intersections, the lines would end up in the database as: 1) (-52,78)-(0,1)-(1,3)-(52,81) 2) (0,0)-(0,1)-(0,4) 3) (0,0)-(0,1)-(1,3) Note that line 3 is now coincident with line 2 over the first segment, and line 1 over the second segment, but that's just an artifact of my example. -- Paul Tomblin, pt@geovision.gvc.com (I speak for me, and only me) America's enthusiasm for Desert-Storm proves that the moral outrage over Vietnam wasn't a protest against fighting or killing, it was a protest against losing or dying. So much for morality.