Número de tripletes de puntos colineales en un entorno estándar

Question

Esto puede ser una pregunta estúpida, pero estaba trabajando en algo y me topé con esta pregunta: si digamos que nos dan $n$ puntos en el plano que determinan $k$ líneas distintas, ¿cuál es el número de tripletes de puntos colineales?

Cualquier ayuda sería muy apreciada

Lo siento si resulta demasiado trivial o demasiado difícil encontrar algunos límites. (Estoy cansado de pensar en ello sin suerte)

Gracias.

Answer 1

puede haber muchos valores de tripletes de puntos colineales (3 puntos situados en una línea) ,

el valor mínimo puede ser cero si no hay 3 puntos en una línea, en este caso k = (n)C(2)

encontrar el valor máximo, si 3 puntos no son colineales entonces forman 3 líneas, si 3 puntos se vuelven colineales entonces constituyen 1 línea,

por lo que cada triplete de puntos colineales reduce el número de líneas en 2,

número de tripletas (máximo) = (nC2 - k)/2

Answer 2

Para el recuento de los tripletes colineales, se identifica una línea con dos puntos cualesquiera y luego se comprueba si una nueva línea formada por otros dos puntos puede ser coincidente o paralela y eso hay que tenerlo en cuenta al calcular los tripletes colineales.

Para resolver: 1. En primer lugar, recoge todos los puntos de una línea utilizando Map<Line, Set<Point2d>> como se sugiere en la propia pregunta. 2. En el caso de los tripletes, filtra las líneas que tengan al menos tres puntos 3. A continuación, calcule nC3 para cada uno de ellos y añádalo al resultado global.

Código para el problema anterior

    import java.util.*;

    public class CollinearTriplets {

        public static void main(String[] args) {
            Point2d A[] = new Point2d[8];
            A[0] = new Point2d(0, 0);
            A[1] = new Point2d(1, 1);
            A[2] = new Point2d(2, 2);
            A[3] = new Point2d(3, 3);
            A[4] = new Point2d(3, 2);
            A[5] = new Point2d(4, 2);
            A[6] = new Point2d(5, 1);
            A[7] = new Point2d(4, 4);

            System.out.println(countCollinear(A));
        }

        public static int factorial(int n) {
            int fact = 1;
            for (int i = 1; i <= n; i++) {
                fact = fact * i;
            }
            return fact;
        }

        private static int combinations(int n, int r) {
            return factorial(n) / (factorial(n - r) * factorial(r));
        }

        private static long countCollinear(Point2d[] points) {
            Map<Line, Set<Point2d>> lineToPoints = new HashMap<>();
            long result = 0;

            for (int i = 0; i < points.length; i++) {
                for (int j = i + 1; j < points.length; j++) {
                    double slope = 0d, xIntercept, yIntercept; // Default slope paralell to y-axis
                    if (points[i].x == points[j].x) {
                        slope = Double.MAX_VALUE; // Horizontal slope parallel to x-axis
                    } else if (points[i].y != points[j].y) {
                        xIntercept = points[j].x - points[i].x;
                        yIntercept = points[j].y - points[i].y;
                        slope = yIntercept / xIntercept;
                    }
                    Line currLine = new Line(points[i], slope);
                    if (Objects.isNull(lineToPoints.get(currLine))) {
                        lineToPoints.put(currLine, new HashSet<>());
                    }
                    lineToPoints.get(currLine).add(points[i]);
                    lineToPoints.get(currLine).add(points[j]);
                }

            }
            for (Line line : lineToPoints.keySet()) {
                int size = lineToPoints.get(line).size();
                if (size >= 3) {
                    result = result + combinations(size, 3);
                }
            }
            return result;
        }

        /**
         * Line which contains the starting point and slope so that you can identify exact line
         * equals method is overridden to check whether any new line is coinciding or parallel
         */
        static class Line {
            Point2d point;
            double slope;

            public Line(Point2d point, double slope) {
                this.point = point;
                this.slope = slope;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (!(o instanceof Line)) return false;
                Line line = (Line) o;

                if (line.slope == this.slope)
                    return ((((double) (line.point.y - this.point.y)) / (line.point.x - this.point.x)) == this.slope);
                return false;
            }

            @Override
            public int hashCode() {
                return Objects.hash(slope);
            }
        }

        static class Point2d {
            int x;
            int y;

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

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (!(o instanceof Point2d)) return false;
                Point2d point2d = (Point2d) o;
                return x == point2d.x &&
                        y == point2d.y;
            }

            @Override
            public int hashCode() {
                return Objects.hash(x, y);
            }
        }
    }

La complejidad temporal del código anterior O(N^2) y la complejidad espacial es O(N)