How to check if two given line segments intersect? | GeeksforGeeks


How to check if two given line segments intersect? | GeeksforGeeks
Given two line segments (p1, q1) and (p2, q2), find if the given line segments intersect with each other.
Orientation of an ordered triplet of points in the plane can be
–counterclockwise
–clockwise
–colinear
The following diagram shows different possible orientations of (a, bc)
1. General Case:
- (p1q1p2) and (p1q1q2) have different orientations and
- (p2q2p1) and (p2q2q1) have different orientations
2. Special Case 
- (p1q1p2), (p1q1q2), (p2q2p1), and (p2q2q1) are all collinear and
- the x-projections of (p1q1) and (p2q2) intersect
- the y-projections of (p1q1) and (p2q2) intersect
bool onSegment(Point p, Point q, Point r)
{
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
       return true;
    return false;
}
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
    // See 10th slides from following link for derivation of the formula
    // http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;  // colinear
    return (val > 0)? 1: 2; // clock or counterclock wise
}
// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);
    // General case
    if (o1 != o2 && o3 != o4)
        return true;
    // Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
     // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;
    return false; // Doesn't fall in any of the above cases
}
Also check http://massivealgorithms.blogspot.com/2014/09/Chapter33-computational-geometry.html
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
How to Compute the Orientation
• slope of segment (p1,p2): σ = (y2−y1) / (x2−x1)
• slope of segment (p2,p3): τ = (y3−y2) / (x3−x2)
• Orientation test
- counterclockwise (left turn): σ < τ
- clockwise (right turn): σ > τ
- collinear (left turn): σ = τ
 • The orientation depends on whether the expression (y2−y1) (x3−x2) − (y3−y2) (x2−x1) is positive, negative, or null.

Point Inclusion
 • given a polygon and a point, is the point inside or outside the polygon?
 • orientation helps solving this problem in linear time

• Draw a horizontal line to the right of each point and extend it to infinity
• Count the number of times a line intersects the polygon.
We have: - even number ⇒ point is outside
- odd number ⇒ point is inside
Special case: intersect with special points

Simple Closed Path — Part I
 • Problem: Given a set of points ...
 • “Connect the dots” without crossings
• Pick the bottommost point a as the anchor point

• For each point p, compute the angle q(p) of the segment (a,p) with respect to the x-axis:
• Traversing the points by increasing angle yields a simple closed path:

- Observation:, we don’t care about the actual values of the angles. We just want to sort by angle. - Idea: use the orientation to compare angles without actually computing them!!

 the orientationcan be used to compare angles without actually computing them ... Cool!
θ(p) < θ(q) ⇔ orientation(a,p,q) = CCW • We can sort the points by angle by using any “sorting-by-comparison” algorithm (e.g., heapsort or merge-sort) and replacing angle comparisons with orientation tests • We obtain an O(N log N)-time algorithm for the simple closed path problem on N points

Given two straight line segments (represented as a start point and an end point), compute the point of intersection, if any

Point intersection(Point startl, Point endl, Point start2, Point end2) {
        /* Rearranging these so that, in order of x values: start is before end and
         * point 1 is before point 2. This will make some of the later logic simpler. */
        if (startl.x > endl.x) swap(startl, endl);
        if (start2.x > end2.x) swap(start2, end2);
        if (startl.x > start2.x) {
                swap(startl, start2);
                swap(endl, end2);
        }

        /* Compute lines (including slope and y-intercept). */
        Line linel new Line(startl, endl);
        Line line2 = new Line(start2, end2);

        /* If the lines are parallel, they intercept only if they have the same y
         * intercept and start 2 is on line 1. */
        if (linel.slope == line2.slope) {
                if (linel.yintercept == line2.yintercept &&
                    isBetween(startl, start2, endl)) {
                        return start2;
                }
                return null;
        }

        /* Get intersection coordinate. */
        double x = (line2.yintercept - linel.yintercept) / (linel.slope - line2.slope);
        double y = x * linel.slope + linel.yintercept;
        Point intersection = new Point(x, y);

        /* Check if within line segment range. */
        if (isBetween(startl, intersection, endl) &&
            isBetween(start2, intersection, end2)) {
                return intersection;
        }
        return null;
}

/* Checks if middle is between start and end. */
boolean isBetween(double start, double middle, double end) {
        if (start > end) {
                return end<= middle && middle<= start;
        } else {
                return start<= middle && middle<= end;
        }
}

/* Checks if middle is between start and end. */
boolean isBetween(Point start, Point middle, Point end) {
        return isBetween(start.x, middle.x, end.x) &&
               isBetween(start.y, middle.y, end.y);
}

/* Swap coordinates of point one and two. */
void swap(Point one, Point two) {
        double x one.x;
        double y = one.y;
        one.setlocation(two.x, two.y);
        two.setlocation(x, y);
}

public class Line {
public double slope, yintercept;

public Line(Point start, Point end) {
        double deltaY = end.y - start.y;
        double deltaX = end.x - start.x;
        slope = deltaY/deltaX; // Will be Infinity (not exception) when deltaX 0
        yintercept = end.y - slope * end.x;
}
}
public class Point {
public double x, y;
public Point(double x, double y) {
        this.x x;
        this.y = y;
}

public void setlocation(double x, double y) {
        this.x x;
        this.y = y;
}
}
http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
Also check http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
Read full article from How to check if two given line segments intersect? | GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts