Java grouping point which can fall in a rectangle

Question

I am doing a research where I have stuck in solving a algorithm in efficient manner.I would be really helpful if someone help me out in this -

Algo -

I have a set of points (x1,y1) , (x2,y2)...(can be 10000 points). I would like to print points in a group - which can be enclosed by a rectangle of 10x10.

Examples -

p1 (10,10)
p2 (15,15)
p3 (40,100)
p4 (40,50)
p5 (40,90)
p6(200,200)
p7(400,350)

output 

gp1 -> p1 (10,10), p2 (15,15)
gp2 -> p3 (40,100), p5 (40,90)

Explanation - point p1 and p2 will fall in a rectangle if a rectangle of 10x10 starts from point p1. Similar p3 & p5 will fall in a rectangle of 10x10 if rectangle will start from point p3. It would also be helpful if we can find out the co-ordinate of each rectangle enclosing them.

Note: A single Point can belong to 2 different group..in this case all will be treated a single group and then size of rectangle will grow

What I tried -

I tried to take point p1 co-ordinate and compare its x & y with others. if i found point p2 near to it. I add them in a group and then skip p2 from comparing others. i start process again with p3.

It doesn't seems a efficient solution as in worst case it can have nxn complexity which is very bad.

Note: I request you all to please do not consider this as a homework as it is not.

If I understand you correctly this is a partitioning problem. They tend to be computationally onerous. One thing to notice is if you sort them in X you can find subsets of candidate points. To be within 10 of a given point both coordinates of the other point must be within 10. What about ambiguous cases such as (0,0), (9,9), (11,11)? (9,9) with in a 10x10 rectangle with (0,0) and (11,11) but not each other. — Persixty, Jan 22 '15 at 16:16
yes they can belong to 2 different group..in this case they will be treated a single group and then size of rectangle will become 20x20 — Learner, Jan 22 '15 at 17:47
What's the goal here -- is this a minimization problem, find the minimum number of rectangles that encloses all the points? If so, is a 20x20 rectangle just as good as a 10x10 one, or does it "cost" more? Also, will the rectangles always be squares, or can they be combined in other ways--say 10x20, or even 12x12? — John Kugelman, Jan 22 '15 at 17:58
(0,0)-(9,9) is a 10x10 height and width so are you sure of gp2 -> p3 (40,100), p5 (40,90) ? (31,81) <-[lower left] (40,90) [higher right> ->(49,99) it does not reach (40,100). Or am i wrong ? — philippe lhardy, Jan 22 '15 at 18:20

score 1 · Accepted Answer · edited May 23 '17 at 10:25

In order to get any kind of reasonable performance out of a clustering problem you are going to need to organize your data into a data structure that fits your algorithmic requirements first. The problem you are trying to solve might be a good fit for a "k-d tree" http://en.wikipedia.org/wiki/K-d_tree

Once you organize your data into a k-d tree you can then more efficiently ask questions about the distance relationships between the various nodes.

There is a stackoverflow question here about java implementations of a k-d tree. KDTree Implementation in Java

Gilbert Le Blanc · Answer 2 · 2015-01-22T20:36:38.127

Rather than an algorithm, you need to define a data structure that will hold the information that you want. Here's one way to define the data structure.

package com.ggl.fse;

import java.awt.Point;
import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.List;

public class RectangleGroup {

    private List<RectanglePoint> points;

    private Rectangle boundingRectangle;

    public RectangleGroup(int width, RectanglePoint rPoint) {
        this.points = new ArrayList<RectanglePoint>();
        this.points.add(rPoint);

        Point p = rPoint.getPoint();
        this.boundingRectangle = new Rectangle(p.x, p.y, width, width);
    }

    public boolean checkPoint(RectanglePoint rPoint) {
        if (isBound(rPoint)) {
            points.add(rPoint);
            return true;
        } else {
            return false;
        }
    }

    public boolean isBound(RectanglePoint rPoint) {
        return boundingRectangle.contains(rPoint.getPoint());
    }

    public class RectanglePoint {

        private Point point;

        private String label;

        public RectanglePoint(String label, int x, int y) {
            this(label, new Point(x, y));
        }

        public RectanglePoint(String label, Point point) {
            this.label = label;
            this.point = point;
        }

        public Point getPoint() {
            return point;
        }

        public String getLabel() {
            return label;
        }

    }

}

You can create a List of RectangleGroup instances. Each new RectanglePoint has to be tested against all of the RectangleGroup instances.

I made use of the Point and Rectangle classes from the AWT package.

You will have to combine rectangles later, in the event that a RectanglePoint fit in more than one RectangleGroup.

Java grouping point which can fall in a rectangle

2 Answers2