about summary refs log tree commit diff homepage
path: root/utils/hacks/TreeGraphs/Graphics/Geometry/Intersect2D.py
blob: 9e97a9435805b6fccb60844644cbcd9aa1f40d4b (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# ===-- Intersect2D.py ----------------------------------------------------===##
# 
#                      The KLEE Symbolic Virtual Machine
# 
#  This file is distributed under the University of Illinois Open Source
#  License. See LICENSE.TXT for details.
# 
# ===----------------------------------------------------------------------===##

import vec2, math

def intersectLineCircle((p, no), (C, r)):
	x = vec2.sub(p,C)
	b = 2.*vec2.dot(no, x)
	c = vec2.sqr(x) - r*r
	dist = b*b - 4*c
	
	if dist<0:
		return None
	else:
		d = math.sqrt(dist)
		t0 = (-b - d)*.5
		t1 = (-b + d)*.5
		return (t0,t1)
	
#def intersectLineCircle((lineP,lineN),(circleP,circleR)):
#	dx,dy = vec2.sub(lineP,circleP)
#	nx,ny = lineN
#
#	a =   (nx*nx + ny*ny)
#	b = 2*(dx*nx + dy*ny)
#	c =   (dx*dx + dy*dy) - circleR*circleR
#	
#	k = b*b - 4*a*c
#	if k<0:
#		return None
#	else:
#		d = math.sqrt(k)
#		t1 = (-b - d)/2*a
#		t0 = (-b + d)/2*a
#		return t0,t1
	
def intersectCircleCircle(c0P, c0R, c1P, c1R):
	v = vec2.sub(c1P, c0P)
	d = vec2.length(v)
	
	R = c0R
	r = c1R

	try:	
		x = (d*d - r*r + R*R)/(2*d)
	except ZeroDivisionError:
		if R<r:
			return 'inside',()
		elif r>R:
			return 'outside',()
		else:
			return 'coincident',()
	
	k = R*R - x*x
	if k<0:
		if x<0:
			return 'inside',()
		else:
			return 'outside',()
	else:
		y = math.sqrt(k)
		return 'intersect',(vec2.toangle(v),vec2.toangle((x,y)))