Given a linked list of line segments, remove collinear points in the middle

Question

This code removes any middle point find in line. It works only in x and y axis. This problem is a Java implementation of this.

package com.atleyvirdee.myDataStructures.linkedlist.problems;

import com.atleyvirdee.myDataStructures.linkedlist.ILinkedList;
import com.atleyvirdee.myDataStructures.linkedlist.ILinkedListNode;
import com.atleyvirdee.myDataStructures.linkedlist.LinkedListerTraverser;
import com.atleyvirdee.myDataStructures.linkedlist.implemtations.SinglyLinkedList;

/**
 * 
 * @author jaspinder
 * 
 *         Given a linked list of co-ordinates where adjacent points either form a vertical line or
 *         a horizontal line. Delete points from the linked list which are in the middle of a
 *         horizontal or vertical line.
 * 
 *         Examples:
 * 
 *         Input: (0,10)->(1,10)->(5,10)->(7,10)
 *                                          |
 *                                        (7,5)->(20,5)->(40,5)
 *         Output: Linked List should be changed to following
 *         (0,10)->(7,10)
 *                   |
 *                 (7,5)->(40,5)
 *         The given linked list represents a horizontal line from (0,10)
 *         to (7, 10) followed by a vertical line from (7, 10) to (7, 5),
 *         followed by a horizontal line from (7, 5) to (40, 5).
 * 
 *         Input: (2,3)->(4,3)->(6,3)->(10,3)->(12,3)
 *         Output: Linked List should be changed to following
 *         (2,3)->(12,3)
 *         There is only one vertical line, so all middle points are removed.
 */
public class P13RemoveMiddlePoints {





  public static void main( String[] args ) {

    // Test Case 1
    System.out.println("Test Case One");
    ILinkedList<Point> one = new SinglyLinkedList<Point>();
    one.append(new Point(0, 10));
    one.append(new Point(1, 10));
    ILinkedListNode<Point> root = removeMiddlePoints(one.getRoot());
    LinkedListerTraverser<Point> traversers =
        new LinkedListerTraverser<Point>(root);
    traversers.traverseList();


    // Test Case 2
    System.out.println("\n\n\n\nTest Case Two");
    ILinkedList<Point> two = new SinglyLinkedList<Point>();
    two.append(new Point(0, 10));
    two.append(new Point(1, 10));
    two.append(new Point(5, 10));
    two.append(new Point(7, 10));
    root = removeMiddlePoints(two.getRoot());
    traversers = new LinkedListerTraverser<Point>(root);
    traversers.traverseList();


    // Test Case 3
    System.out.println("\n\n\n\nTest Case Three");
    ILinkedList<Point> three = new SinglyLinkedList<Point>();
    three.append(new Point(7, 54));
    three.append(new Point(7, 55));
    three.append(new Point(7, 56));
    three.append(new Point(7, 57));
    three.append(new Point(7, 58));
    root = removeMiddlePoints(three.getRoot());
    traversers = new LinkedListerTraverser<Point>(root);
    traversers.traverseList();


    // Test Case 4
    System.out.println("\n\n\n\nTest Case four");
    ILinkedList<Point> four = new SinglyLinkedList<Point>();
    four.append(new Point(0, 10));
    four.append(new Point(1, 10));
    four.append(new Point(5, 10));
    four.append(new Point(7, 10));
    four.append(new Point(7, 5));
    four.append(new Point(20, 5));
    four.append(new Point(20, 6));
    four.append(new Point(20, 8));
    four.append(new Point(40, 8));
    four.append(new Point(42, 8));
    four.append(new Point(432, 121));
    root = removeMiddlePoints(four.getRoot());
    traversers = new LinkedListerTraverser<Point>(root);
    traversers.traverseList();


    // Test Case 5
    System.out.println("\n\n\n\nTest Case five");
    ILinkedList<Point> five = new SinglyLinkedList<Point>();
    five.append(new Point(0, 10));
    root = removeMiddlePoints(five.getRoot());
    traversers = new LinkedListerTraverser<Point>(root);
    traversers.traverseList();
  }



  private static ILinkedListNode<Point> removeMiddlePoints( ILinkedListNode<Point> root ) {
    if ( root == null || root.getNext() == null || root.getNext().getNext() == null ) return root;
    ILinkedListNode<Point> current = root;
    ILinkedListNode<Point> next =
        (root != null && root.getNext() != null) ? root.getNext() : null;

        while(current!=null && next!=null){

          if(current.getData().y == next.getData().y){
              ILinkedListNode<Point> innerCurrent = current;
              ILinkedListNode<Point> innerNext = next;
              while(innerCurrent!=null && innerNext!=null && innerCurrent.getData().y == innerNext.getData().y){
                innerCurrent = innerNext;
                innerNext = (innerCurrent!=null && innerCurrent.getNext()!=null)?innerCurrent.getNext():null;
              }
              current.setNext(innerCurrent);
              System.out.println("Same y axis.");
          }


          if(current.getData().x == next.getData().x){
            ILinkedListNode<Point> innerCurrent = current;
            ILinkedListNode<Point> innerNext = next;
            while(innerCurrent!=null && innerNext!=null && innerCurrent.getData().x == innerNext.getData().x){
              innerCurrent = innerNext;
              innerNext = (innerCurrent!=null && innerCurrent.getNext()!=null)?innerCurrent.getNext():null;
            }
            current.setNext(innerCurrent);
            System.out.println("Same x axis.");
          }

          current = next;
          next = (current!=null && current.getNext()!=null)?current.getNext():null;
     } 
    return root;
  }
}


class Point implements Comparable<Point> {

  int x = 0;
  int y = 0;

  @Override
  public String toString() {
    return "(" + x + "," + y + ")";
  }

  public Point( int x, int y ) {
    this.x = x;
    this.y = y;
  }

  public int getX() {
    return x;
  }

  public void setX( int x ) {
    this.x = x;
  }

  public int getY() {
    return y;
  }

  public void setY( int y ) {
    this.y = y;
  }

  @Override
  public int compareTo( Point o ) {
    return 0;
  }
}

Answer 1

Java has a very capable LinkedList class already. Don't reinvent the wheel with yet another linked list implementation, which is likely incompatible with the Java Collections framework.

Why does the Point class bother to implement the Comparable interface at all if it does it altogether wrong?

You've gone through the trouble of defining .getX() and .getY() in your Point class, yet your algorithm just reaches into the object to access .x and .y directly. If you're going to do that, do it properly, with an immutable class:

public final class Point {
    public final int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }
}

Answer 2

Here are a few things that may help you improve your code, not yet mentioned in the other review.

Use correct spelling

The code currently contains this line:

import com.atleyvirdee.myDataStructures.linkedlist.implemtations.SinglyLinkedList;

However, "implementations" is not spelled correctly. It might be no problem for you, using some IDE that helpfully replicates that misspelling everywhere it occurs, but as you write code that other people will use, spelling things incorrectly will make for a annoying interface.

Use geometry

Any three different points on a Cartesian plane will define either a triangle or a straight line. With a bit of thinking, I'm sure that you'll see that the area of the triangle will be: $$A = \frac{1}{2}(x_1 - x_0)(y_2 - y_0) - (x_2 - x_0)(y_1 - y_0)$$

The interesting property of this (which is called the signed area of a triangle) is that if the area is positive, the vertices are oriented counterclockwise (anti-clockwise). If the area is negative, the points are oriented clockwise. If the area is zero, the points are collinear. Since you're interested only in collinearity, we can omit the \$\frac{1}{2}\$ and calculate \$2A\$. If that quantity is 0, the points are collinear and one may be removed.

But which one is the center one? In your case, the points are already apparently sorted, so it is easy. In the general case, we can simply compare either the \$x\$ or \$y\$ coordinates (or both in the worst case). The center point will necessarily have \$x_0 \le x_1 \le x_2\$ and \$y_0 \le y_1 \le y_2\$ where \$(x_0, y_0)\$ and \$(x_2, y_2)\$ are the end points and \$(x_1, y_1)\$ is the collinear point between them.

This may be more than you need if you're only interested in collinear points that align with the \$x\$ and \$y\$ axes, but I think it's sufficiently generally useful that it's worth knowing the technique.