Point to line
double pointLine(Point a, Point b, Point p) {
double cross = (b.x-a.x)*(p.y-a.y) - (b.y-a.y)*(p.x-a.x);
double ab = Math.hypot(b.x-a.x, b.y-a.y);
return Math.abs(cross) / ab;
}Advertisement
Point to segment
double pointSeg(Point a, Point b, Point p) {
double dot = (p.x-a.x)*(b.x-a.x) + (p.y-a.y)*(b.y-a.y);
double len2 = (b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y);
double t = Math.max(0, Math.min(1, dot / len2));
double px = a.x + t*(b.x-a.x), py = a.y + t*(b.y-a.y);
return Math.hypot(p.x-px, p.y-py);
}Advertisement
Complexity
O(1) per query.
Segment-segment distance
4 point-to-segment checks + segment intersection check. O(1).