| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1684.1 | two steps | SGOUTL::BELDIN_R | D-Day: 154 days and counting | Wed Oct 28 1992 15:09 | 15 |
| Just to make sure I understand, you don't count the intersection of
the lines of which the segments are a part, but just intersections of
the segments?
In that case, you can describe the problem algebraicly as solving the
intersection of the two lines and the inequalities
min(x1,x2,x3,x4) < x < max(x1,x2,x3,x4)
and
min(y1,y2,y3,y4) < y < max(y1,y2,y3,y4).
I would find the intersection of the lines and verify that it satisfies
the inequalities. Not elegant, but practical.
Dick
|
| 1684.2 | I didn't spell check | VMSDEV::HALLYB | Fish have no concept of fire. | Wed Oct 28 1992 15:25 | 19 |
| This is a simple case of two equations, two unknowns.
y2 - y1
(A) y - y1 = ------- * x - x1
x2 - x1
y4 - y3
(B) y - y3 = ------- * x - x3
x4 - x3
If these two equations are solvable, the lines intersect at the solution.
In your case (special deal for those not too curious) you only need check
and see that (y2-y1)/(x2-x1) not equal to (y4-y3)/(x4-x3). When those are
NOT equal, then fer sure the lines intersect ('cause they're not parallel).
A little more work is needed in case you get two lines that overlay each
other, but you don't seem to need that.
John
|
| 1684.3 | | 3D::ROTH | Geometry is the real life! | Wed Oct 28 1992 15:30 | 24 |
| What do you mean by "efficient"? This will depend on whether
you want to report *all* intersections between a given collection
of lines, (and whether intersections are likely or not), or if
you want to test a given line against a set of others, or
if you want to just compare a given pair of lines.
The reason for these questions is you can preprocess your line
segment database in some situations to *dramatically* speed things
up. Plane sweep algorithms are an example for sets of line segments.
To just compare a pair of lines, check if their bounding boxes
overlap. This trivially rejects many cases, and is numerically
more stable in some cases. If the boxes do, then calculate the
intersection between the lines by solving a 2 by 2 set of equations
and check if the solution lies on the line segments.
Your equations would be something like
x1 + (x2-x1)*s = x3 + (x4-x3)*t
y1 + (y2-y1)*s = y3 + (y4-y3)*t
Solve for s and t, checking if 0 <= s,t <= 1
- Jim
|
| 1684.4 | | 3D::ROTH | Geometry is the real life! | Wed Oct 28 1992 15:35 | 12 |
| > Your equations would be something like
> x1 + (x2-x1)*s = x3 + (x4-x3)*t
> y1 + (y2-y1)*s = y3 + (y4-y3)*t
> Solve for s and t, checking if 0 <= s,t <= 1
One more detail, if the determinant is zero (or nearly zero)
the segments are parallel, or nearly so, and won't overlap
(or probably don't)
- Jim
|
| 1684.5 | | DPE::TATARA | Eric Tatara TWO/C2 dtn 247-3020 | Wed Oct 28 1992 16:10 | 5 |
| I really am looking to count the number of intersections between a large number
of segments (typically 10-100).
If a plane sweep algorithm is easy to code, then that might be worth it,
otherwise i'd resort to comparing each segment against each other.
|
| 1684.6 | | 3D::ROTH | Geometry is the real life! | Wed Oct 28 1992 21:46 | 15 |
| For a hundred or so, the naive way of calculating intersections
between all pairs will probably be fast enough.
Otherwise the plane sweep idea will win - it's not hard to do.
I've written such code but it's imbedded in more complex routines
for stuff like hidden line removal of 3d drawings and polygon fill
for complex self-intersecting polygons.
Probably you should do what I'd do first - code the simpleminded
routine and see what happens. It's always useful to verify if
a more complex algorithm works anyway.
What is your application?
- Jim
|