Python code in this repo serves for solving a specific problem within a developer candidate test. It is a Flask-based web application that provides a simple API. Available at collinearity-checker.herokuapp.com, licensed under the GPLv3.
-
Given a set of feature points in the bi-dimensional plane, determine every line that contains at least N or more collinear points (point coordinate in integer values).
-
Manage data through this REST API:
[POST]/pointadds a new point in space[GET]/lines/<n>gets all lines passing through at least N points (a line segment is a set of collinear points)
-
Create all possible pairs of points in the 2d space, so that each pair
(x1, y1)and(x2, y2)defines a strait line. -
For every line, check that a given point
(x, y), if it is not already on the line ends, is on that straight line using the following equation:(y1 - y2) * x + (x2 - x1) * y + (x1 * y2 - x2 * y1) == 0 -
If the given point
(x, y)is collinear with the line, add point coordinates to a set of line coordinates. -
Repeat for all remaining points.
This algorithm is realized in a Flask web application. Point coordinates are stored inside an object and remain for the lifetime of the app. This app is deployed on Heroku, and it is available at collinearity-checker.herokuapp.com. Please note that when the app on Heroku doesn't receive any traffic in 1 hour, it goes to sleep. If the sleeping web app receives web traffic, it will become active again after a short delay.
For local deployment, make sure that the app folder is a working directory for the app. Run app.py. It will start a Flask web app on your localhost, port 5000. By default, bi-dimensional space doesn't have any points in it.
- app — source code directory
- tests
- test_api.py — a test to assert the correctness of the responses from API
- test_main.py — a test that asserts the correctness of the Cartesian plane object. It uses hardcoded point data for validation of the collinearity.
- api.py — Flask api
- main.py — contains a class used by the API
- Procfile — lists the process types in the app, used for hosing on Heroku
- requirements.txt — necessary Python dependencies
- runtime.txt — specifies a Python runtime for Heroku
- tests
- resources — pictures for this README.md
List all points.
curl -X GET https://collinearity-checker.herokuapp.com/v1/point
Add a new point by providing parameters x and y. You can't add more than 100 points, because it is the allowed limit (see Performance section below).
curl -X POST -F "x=-10" -F "y=15" https://collinearity-checker.herokuapp.com/v1/points
Delete all points.
curl -X DELETE https://collinearity-checker.herokuapp.com/v1/point
List all groups of collinear points. The minimum allowed number of points in a group <n> that you provide at the end of URL is 3.
curl -X GET https://collinearity-checker.herokuapp.com/v1/line/5
Show a plot with points and lines. You can plot them in a browser — open this link:
https://collinearity-checker.herokuapp.com/v1/plot
-
The requested amount of N, collinear points in a segment, doesn't affect the performance.
-
The bottleneck of the app is the collinearity check, which runs as a nested loop, i.e. for every line segment it checks every point. This approach increases computing time exponentially, as shown on a graph below. That is why the maximum amount of 2d points is limited to 100.
-
One approach to boost the app speed would be to use spatial indices for preliminary filtering of irrelevant points for every segment (before going to the nested loop). It should be possible to implement this solution using Shapely.
-
Another way, useful for scaling the application in the cloud, would be to apply a PostgreSQL database to store points as Geometry features. Powered by PostGIS extension, PostgreSQL gives many time-proven tools for spatial relationship analysis.
- Repo owner: Yaroslav Vasyunin