Point-in-Triangle Search | Dataford Interview Questions

Given n triangles (3 coordinates each) that tile a 2D region without overlap, write a function that returns the triangle containing a query point, or -1.

Asked in the round 4 stage. For SQL, evaluate all rows in query_points against the triangles in triangles. Points on shared boundaries should be assigned to the lowest matching triangle_id; incomplete query coordinates should return -1.

Output

One row per query point with point_id and triangle_id
Return -1 when no triangle contains the point
Order by point_id ascending

Schema

triangles

Column	Type	Description
triangle_idPK	INT	Unique triangle identifier
x1	NUMERIC	X coordinate of the first vertex
y1	NUMERIC	Y coordinate of the first vertex
x2	NUMERIC	X coordinate of the second vertex
y2	NUMERIC	Y coordinate of the second vertex
x3	NUMERIC	X coordinate of the third vertex
y3	NUMERIC	Y coordinate of the third vertex

query_points

Column	Type	Description
point_idPK	INT	Unique query point identifier
x	NUMERIC	X coordinate of the query point
y	NUMERIC	Y coordinate of the query point

Your question is Point-in-Triangle Search. Start with the requirements and the two tables in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem