1
$\begingroup$

I am writing a function to find the intersection of a pair of lines and another function to find the intersection of a pair of line segments. The parallel case and the single point intersection case are logically clean and my functions work well to find these. But, the cases where the lines are collinear or the line segments are collinear and overlapping is logically sloppy (at least in my mind)... Here's how I've approached the problem:

Parallel returns:

NULL (e.g. no intersection)

Point intersection returns:

a Coordinate (e.g. a point)

Collinear line segments that have a single common point returns:

a Coordinate (e.g. the common endpoint)

Collinear line segments that have multiple common points returns:

a Coordinate pair (e.g. the line segment of overlap)

Collinear lines returns:

the furthest separated pair of Coordinates (e.g. the largest line segment definable using any of the points that defined the lines being compared)

Logically in any collinear intersection situation it seems reasonable to just return any point within the overlapping region - it also seems to be reasonable to return every point in the overlapping region - it also seems reasonable to return no points at all (the argument being that collinear intersection is an illogical concept assuming the definition that line / line segment intersection is a single point). If I were to take the approach of returning every point of overlap I would not be able to represent the collinear line intersection case (X and Y would need to have infinity or zero values because there are no endpoints to the intersecting region)...

Briefly researching on the Internet I didn't find a clear-cut definition of collinear intersection - this indicates that I'm treading in the territory of the illogical... Nonetheless, I find it misleading to claim via the functions that I am writing that collinear line segments do not intersect... when I consider the case of determining whether or not a pair of rectangles that share a common collinear line segment intersect... certainly rectangles that share a portion of an edge are intersecting (aren't they)... or (broadening my thinking) is the argument that the rectangles are touching but not intersect... (is touching a standard geometric concept that's differentiated from intersection?) If touching is a differentiated concept then the situation of shared endpoint intersection of line segments is invalid (e.g. there is no intersection of the line segments, but there is touching of the line segments)...

So...

Is collinear intersection a well defined planar geometry concept?

If so, please point me to a reference so that I can absorb the definition and logic behind the definition.

If not, please comment on the approach that I'm following to validate it or provide a more effective way of thinking about these concepts.

Thanks!

$\endgroup$
0
$\begingroup$

A segment is a set of points from the space. The intersection of two sets $A$ and $B$ is defined as $A \cap B = \{x:x\in A \;\wedge\; x\in B \}.$

If you have 2 segments overlapping, why would you need to return something? I would associate each line or segment to a vector containing the slope and the shift about one coordinate axis of the given segment or line. The vector could also contain the endpoints of the segments.

Now, you would need to check if a segment is overlapping with another segment and then return the endpoints of a new segment defined as the intersection of the first two segments. This will be easy if the vectors contain the endpoints' coordinates.

$\endgroup$
  • $\begingroup$ The purpose of theses functions is to provide the calling program what's within the intersection (e.g. the collection of common points)... The goal is to simply provide an approach that's most suitable for the widest range of use cases... my hope is that by posting this question, the ensuing conversation will inform my approach so as to enable clean differentiation of concepts within the greater function library that I'm building - there may well be a family of functions that need to be built (thus the concept of differentiating touching and intersection) $\endgroup$ – Neoheurist Nov 7 '14 at 20:38
  • $\begingroup$ Additionally, I have methods to find suitable values for each of the cases listed in the question - so, I'm not really looking for the logic behind these functions... I'm asking for help to shape the pattern of functions that I'm building grounded upon geometric best practices / orthodoxy to define the methods within the interface Thanks! $\endgroup$ – Neoheurist Nov 7 '14 at 20:41
0
$\begingroup$

If the return is always a (collection of) range(s) for which the endpoints are defined, any and every other possible return description is included.
A single point is one range with identical endpoints. A line segment is a range with different endpoints.
This avoids leaving out any part of the intersection, but doesn't require an infinite list.

$\endgroup$
0
$\begingroup$

The objects of your universe are closed segments of positive length, closed half lines, and full lines in the plane, in short: closed one-dimensional convex sets in ${\mathbb R}^2$. Denote the set of these objects by ${\cal O}$. The intersection of two such objects is one of the following: empty, a single point, or again an element of ${\cal O}$.

Any $S\in{\cal O}$ can be extended to a full line $\ell_S$, the carrier line of $S$, and has a direction which can be represented by a unit vector ${\bf u}_S$, whereby ${\bf u}_S$ is determined only up to a factor $\pm1$.

Given two objects $S_1$, $S_2\in{\cal O}$, let $\ell_i$ be their carrier lines and ${\bf u}_i$ their directions. At the top level we then have the following three cases:

(a) $\quad {\bf u}_1\ne\pm {\bf u}_2\>$,

(b) $\quad {\bf u}_1=\pm {\bf u}_2\>,\ $ but $\ \ell_1\ne\ell_2$

(c) $\quad \ell_1=\ell_2\>$.

In case $(a)$ the two carrier lines intersect in a single point ${\bf p}$, and we have to test whether ${\bf p}\in S_1\cap S_2$. The exact form of this test depends on the way the objects are presented.

In case (b) the two carrier lines are parallel and disjoint, hence $S_1\cap S_2$ is empty.

In case (c) the common carrier line $\ell$ has a representation of the form $$\ell:\quad t\mapsto{\bf p}+t{\bf u}\qquad(-\infty<t<\infty)\ .$$ The sets $J_i:=\ell^{-1}(S_i)$ are then closed intervals of ${\mathbb R}$, and it remains to find the intersection of these intervals.

There is absolutely nothing fuzzy, or even illogical, in this story.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.