when you go to zillow.com , you have a feature to select any random shape on the map and click on Apply button, to show you the properties on sale within the shape. I want to put my thoughts on how you can design a algorithm for this.

I want to start with an assumption if the shape is a perfect circle, because i have no clue how a random shape feature can be implemented. (I will keep exploring and update this article). So, the smaller problem-1 will be how to retrieve the co-ordinates faster which falls inside the circle given huge set of points.

PS: I am doing this more in terms of implementing a search in java. Please give your thoughts and suggestions.

1st Approach : Brute force

For each point P1(X1,Y1) to Pn (Xn,Yn)— calculate the distance and if it is < circleRadius then add to show list. drawbacks: If point population is huge — and radius is small .

This is brute force way and no special logic needed . Complexity is O(n) — but if n is very high , for every query to find points in circle the algorithm will search all the points.

2nd Approach : Caching all Point and Distance combination

• For all possible point combinations [ (P1,P2) , (P1,P3) .. (P1,Pn),(P2,P3),..(P2,Pn), ..(Pn-1,Pn) ], calculate the distance for each combination
• Total combinations : (n-1)*(n)/2
• This is costly , with O(n*2). But this happens only once and hence all subsequent requests asking for points is faster
• Every request to get points in circle will there after happens with 0(n) and doesn’t iterate through all n. (Breaks out of the loop after seeing first point greater than circle radius )

Java Classes and data structures :

Point.

• class with Id, streetAddress, xCor , yCor
• has equals and hash code implementation

PointDistance

• is class which holds Point and distance.
• has logic to sort Points from the reference point in natural order.
• HashMap<Point,List<PointDistance> — once this is constructed
• given a source point(center of the circle) — we will do get(Point),
• Point class has equals and hash code overridden.
• hash code is generated using coordinates x,y and street address which makes hash collision rare and make faster retrieval of 

Source code: https://github.com/muralikboddu/locationservice/tree/master

My blog on medium.com : https://medium.com/@muralikboddu/how-does-zillow-draw-and-apply-feature-work-96b07522bc91