The two segments might not intersect at all, they might intersect at a single point or they might have a whole segment in common. The following figure shows those three possibilities. The last pair of segments (red and cyan) overlap in a segment, the pair before the red-cyan pair intersects at a single point and the first three pairs of segments do not intersect. Notice that the overlap segment will either be horizontal or vertical since the two segments are both horizontal or both vertical when a segment overlap occurs.
How would we write a simple python program that returns a string 'NO INTERSECTION', 'POINT INTERSECTION' or 'SEGMENT INTERSECTION' for each of the three possible cases outlined above and returns the intersection segment?
Lets suppose the endpoint coordinates of the first segment are given as a python list s1:[x1 y1 x2 y2] and similarly for the second segment s2:[x1 y1 x2 y2].
It is tempting to use a few if statements to check for the different configurations of the two line segments but boundary cases make such an approach hard to get right: Imagine one of the line segments is just a single point in the other segment. In this case we want to return "POINT INTERSECTION" not "SEGMENT INTERSECTION". Yet another case is if the two line segments are both points.
An easier and better solution is to write code that naturally handles all possible cases. We can first easily determine the overlapping region of the two line segments, and then see if it is a point, a segment, or if there is no overlap.
The x coordinate of the leftmost endpoint of the intersection segment will be
left = max(min(s1.x1,s1.x2),min(s2.x1,s2.x2)).
That is we search among the endpoints of s1 and s2 for the the one with the largest left coordinate (the min gets the endpoint in each segment that is the leftmost).
Similarly the x coordinate of the rightmost endpoint of the intersection segment will be
right = min(max(s1.x1,s1.x2),max(s2.x1,s2.x2)).
That is we search among the endpoints of s1 and s2 for the one with the smallest right coordinate (the max gets the endpoint in each segment that is the rightmost).
We can extend this logic to find the y coordinates of the endpoints of the intersection segment:
bottom = max(min(s1.y1,s1.y2),min(s2.y1,s2.y2))
top = min(max(s1.y1,s1.y2),max(s2.y1,s2.y2))
With the coordinates of the segment endpoints we can promptly find out if there is intersection or not. For example if left > right or bottom>top there is no intersection whatsoever. If left=right and bottom=top the 2 segments meet at a single point. Otherwise they overlap in a segment.
Here it is this solution (you can change the code and try different approaches: it will be executed roughly every minute, and you can change this interval by editing the value 60000 to the value most convenient to you)
It is tempting to use a few if statements to check for the different configurations of the two line segments but boundary cases make such an approach hard to get right: Imagine one of the line segments is just a single point in the other segment. In this case we want to return "POINT INTERSECTION" not "SEGMENT INTERSECTION". Yet another case is if the two line segments are both points.
An easier and better solution is to write code that naturally handles all possible cases. We can first easily determine the overlapping region of the two line segments, and then see if it is a point, a segment, or if there is no overlap.
The x coordinate of the leftmost endpoint of the intersection segment will be
left = max(min(s1.x1,s1.x2),min(s2.x1,s2.x2)).
That is we search among the endpoints of s1 and s2 for the the one with the largest left coordinate (the min gets the endpoint in each segment that is the leftmost).
Similarly the x coordinate of the rightmost endpoint of the intersection segment will be
right = min(max(s1.x1,s1.x2),max(s2.x1,s2.x2)).
That is we search among the endpoints of s1 and s2 for the one with the smallest right coordinate (the max gets the endpoint in each segment that is the rightmost).
We can extend this logic to find the y coordinates of the endpoints of the intersection segment:
bottom = max(min(s1.y1,s1.y2),min(s2.y1,s2.y2))
top = min(max(s1.y1,s1.y2),max(s2.y1,s2.y2))
With the coordinates of the segment endpoints we can promptly find out if there is intersection or not. For example if left > right or bottom>top there is no intersection whatsoever. If left=right and bottom=top the 2 segments meet at a single point. Otherwise they overlap in a segment.
Here it is this solution (you can change the code and try different approaches: it will be executed roughly every minute, and you can change this interval by editing the value 60000 to the value most convenient to you)
And a more concise way of coding it up is
Using your test:
ReplyDeletedef test_5(self):
print '-------------------------------'
s1 = [50, 75, 50, 87.5]
s2 = [35, 35, 74, 75]
expected = 'NO INTERSECTION'
print 'test_5 '
print 's1 ' + str(s1)
print 's2 ' + str(s2)
print 'expected result is '
print (expected, [])
print 'obtained '
print self.solution.intersection(s1, s2)
We obtain the following. These two lines do not intersect, however this algorithm shows they do.
test_5
s1 [50, 75, 50, 87.5]
s2 [35, 35, 74, 75]
expected result is
('NO INTERSECTION', [])
obtained
('POINT INTERSECTION', [50, 75])