Programming Assignment 3: Collinear Points

The problem. Given a set of N distinct points in the plane, draw every (maximal) line segment that connects a subset of 4 or more of the points.
Point data type. Create an immutable data type Point that represents a point in the plane by implementing the following API:
public class Point implements Comparable { public final Comparator SLOPE_ORDER;//compare points by slope to this point public Point(int x, int y)//construct the point (x, y) public void draw()//draw this point public void drawTo(Point that)//draw the line segment from this point to that point public String toString()//string representation public int compareTo(Point that)//is this point lexicographically smaller than that point? public double slopeTo(Point that)//the slope between this point and that point }
To get started, use the data type Point.java , which implements the constructor and the draw(), drawTo(), and toString() methods. Your job is to add the following components.

The compareTo() method should compare points by their y-coordinates, breaking ties by their x-coordinates. Formally, the invoking point (x0, y0) is less than the argument point (x1, y1) if and only if either y0 < y1 or if y0 = y1 and x0 < x1.

The slopeTo() method should return the slope between the invoking point (x0, y0) and the argument point (x1, y1), which is given by the formula (y1 − y0)/(x1 −x0). Treat the slope of a horizontal line segment as positive zero; treat the slope of a vertical line segment as positive infinity; treat the slope of a degenerate line segment (between a point and itself) as negative infinity.

The SLOPE_ORDER comparator should compare points by the slopes they make with the invoking point (x0, y0). Formally, the point (x1, y1) is less than the point (x2,y2) if and only if the slope (y1 − y0)/(x1 − x0) is less than the slope (y2 − y0)/(x2 − x0). Treat horizontal, vertical, and degenerate line segments as in the slopeTo() method.

import java.util.Comparator;



public class Point implements Comparable<Point> {



 public final Comparator<Point> SLOPE_ORDER = new PointCmp();



 private final int x; // x coordinate

 private final int y; // y coordinate



 public Point(int x, int y) {

  /* DO NOT MODIFY */

  this.x = x;

  this.y = y;

 }



 public void draw() {

  /* DO NOT MODIFY */

  StdDraw.point(x, y);

 }



 public void drawTo(Point that) {

  /* DO NOT MODIFY */

  StdDraw.line(this.x, this.y, that.x, that.y);

 }



 public double slopeTo(Point that) {

  /* YOUR CODE HERE */

  if (this.compareTo(that) == 0)

   return Double.POSITIVE_INFINITY*-1;

  else if (this.x == that.x)

   return Double.POSITIVE_INFINITY;

  else if (this.y == that.y)

   return +0;

  else

   return (that.y - this.y) * 1.0 / (that.x - this.x);

 }



 private class PointCmp implements Comparator<Point> {



  @Override

  public int compare(Point o1, Point o2) {

   // TODO Auto-generated method stub

   if (slopeTo(o1) < slopeTo(o2) || (slopeTo(o1) == slopeTo(o2) && o1.compareTo(o2) == -1))

    return -1;

   else if (slopeTo(o1) > slopeTo(o2) || (slopeTo(o1) == slopeTo(o2) && o1.compareTo(o2) == 1))

    return 1;

   else

    return 0;

  }



 }



 @Override

 public int compareTo(Point that) {

  // TODO Auto-generated method stub

  if (this.y < that.y || (this.y == that.y && this.x < that.x))

   return -1;

  else if (this.y == that.y && this.x == that.x)

   return 0;

  else

   return 1;

 }



 public String toString() {

  /* DO NOT MODIFY */

  return "(" + x + ", " + y + ")";

 }



 public static void main(String[] args) {

  // TODO Auto-generated method stub

  In in = new In(args[0]);

  int num = in.readInt();

  Point points[] = new Point[num];

  for (int i = 0; i < num; i++) {

   int x = in.readInt();

   int y = in.readInt();

   points[i] = new Point(x, y);

  }

  

  

 }



}

Brute force. Write a program Brute.java that examines 4 points at a time and checks whether they all lie on the same line segment, printing out any such line segments to standard output and drawing them using standard drawing. To check whether the 4 points p, q, r, and s are collinear, check whether the slopes between p and q, between p and r, and between p and s are all equal.
The order of growth of the running time of your program should be N4 in the worst case and it should use space proportional to N.

public class Brute {

    public static void main(String[] args) {

        // rescale coordinates and turn on animation mode

        StdDraw.setXscale(0, 32768);

        StdDraw.setYscale(0, 32768);

        StdDraw.show(0);

        StdDraw.setPenRadius(0.01);  // make the points a bit larger



        // read in the input

        String filename = args[0];

        In in = new In(filename);

        int N = in.readInt();

        Point points[] = new Point[N];

        for (int i = 0; i < N; i++) {

            int x = in.readInt();

            int y = in.readInt();

            points[i] = new Point(x, y);

            points[i].draw();

        }

        

        for (int i = 0; i < N; i++) {

            for (int j = 0; j < N - i - 1; j++) {

                if (points[j].compareTo(points[j+1]) == 1) {

                    Point temp = points[j];

                    points[j] = points[j + 1];

                    points[j + 1] = temp;

                }

            }

        }

 

        for (int i = 0; i < N; i++) {

            for (int j = i + 1; j < N; j++) {

                for (int k = j + 1; k < N; k++) {

                    for(int l = k + 1; l < N; l++) {

                        if(points[i].slopeTo(points[j]) == points[j].slopeTo(points[k])&&

                           points[j].slopeTo(points[k]) == points[k].slopeTo(points[l])) {

                            points[i].drawTo(points[l]);

                            StdOut.print(points[i].toString()+" -> "+points[j].toString()

                                        +" -> "+points[k].toString()+" -> "+points[l].toString());

                            StdOut.println();

                        }

                                                                            

                    }

                }

            }

        }



        // display to screen all at once

        StdDraw.show(0);



        // reset the pen radius

        StdDraw.setPenRadius();

    }

}

A faster, sorting-based solution. Remarkably, it is possible to solve the problem much faster than the brute-force solution described above. Given a point p, the following method determines whether p participates in a set of 4 or more collinear points.

Think of p as the origin.

For each other point q, determine the slope it makes with p.

Sort the points according to the slopes they makes with p.

Check if any 3 (or more) adjacent points in the sorted order have equal slopes with respect to p. If so, these points, together with p, are collinear.

Applying this method for each of the N points in turn yields an efficient algorithm to the problem. The algorithm solves the problem because points that have equal slopes with respect to p are collinear, and sorting brings such points together. The algorithm is fast because the bottleneck operation is sorting.
Write a program Fast.java that implements this algorithm. The order of growth of the running time of your program should be N2 log N in the worst case and it should use space proportional to N.
소스 코드 보정 대기;

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

표준 Pascal 범위 내에서 Delphi 입문

표준 Pascal (Standard Pascal) 에서 해설되고 있는 범위에서의 Delphi 는 어떻게 되어 있는지를, 문득 알고 싶어졌습니다. 이 기사는 ** "Delphi 콘솔 응용 프로그램에서 uses 절을 작...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Programming Assignment 3: Collinear Points

좋은 웹페이지 즐겨찾기