Решение на Пресичания от Габриела Грозева

Обратно към всички решения

Към профила на Габриела Грозева

Резултати

  • 10 точки от тестове
  • 1 отнета точка
  • 9 точки общо
  • 19 успешни тест(а)
  • 1 неуспешни тест(а)

Код

package main
import (
"fmt"
"math"
"github.com/fmi/go-homework/geom"
)
func sub(a geom.Vector, b geom.Vector) geom.Vector {
v := geom.Vector{X: (a.X - b.X), Y: (a.Y - b.Y), Z: (a.Z - b.Z)}
return v
}
func cross(v geom.Vector, ov geom.Vector) geom.Vector {
result := geom.Vector{
X: v.Y*ov.Z - v.Z*ov.Y,
Y: v.Z*ov.X - v.X*ov.Z,
Z: v.X*ov.Y - v.Y*ov.X,
}
return result
}
func dot(v geom.Vector, ov geom.Vector) float64 {
return v.X*ov.X + v.Y*ov.Y + v.Z*ov.Z
}
type Triangle struct {
a, b, c geom.Vector
}
func NewTriangle(a, b, c geom.Vector) Triangle {
t := Triangle{a: a, b: b, c: c}
return t
}
func (tr Triangle) Intersect(ray geom.Ray) bool {
e1 := sub(tr.b, tr.a)
e2 := sub(tr.c, tr.a)
h := cross(ray.Direction, e2)
a := dot(e1, h)
f := 1 / a
s := sub(ray.Origin, tr.a)
u := f * dot(s, h)
if u < 0.0 || u > 1.0 {
return false
}
q := cross(s, e1)
v := f * dot(ray.Direction, q)
if v < 0.0 || u+v > 1.0 {
return false
}
t := f * dot(e2, q)
if t > 0.00001 {
return true
}
return false
}
type Quad struct {
a, b, c, d geom.Vector
}
func NewQuad(a, b, c, d geom.Vector) Quad {
q := Quad{a: a, b: b, c: c, d: d}
return q
}
func (q Quad) Intersect(ray geom.Ray) bool {
t1 := NewTriangle(q.a, q.b, q.c)
intersected1 := t1.Intersect(ray)
t2 := NewTriangle(q.a, q.c, q.d)
intersected2 := t2.Intersect(ray)
t3 := NewTriangle(q.a, q.b, q.d)
intersected3 := t3.Intersect(ray)
t4 := NewTriangle(q.c, q.b, q.d)
intersected4 := t4.Intersect(ray)
return (intersected1 || intersected2) && (intersected3 || intersected4)

Не мога да разбера защо ти трябват четири триъгълника. Замисли се какво ще стане с твоето решение ако четириъгълника не е изпъкнал.

Четири са точно заради кейса, в който четириъгълника е вдлъбнат, ако разделим четириъгълника 2 пъти с по 2 триъгълника в единия от кейсовете четириъгълника пак ще си е вдлъбнат (ще е истинското представяне на четириъгълника), а в дугия ще е изпъкнал. Просто в момента не ми се занимава да търся решението със смятането и на това решение сложнотта му е константа - няма да е мн по-различно.

}
type Sphere struct {
origin geom.Vector
r float64
}
func NewSphere(origin geom.Vector, r float64) Sphere {
s := Sphere{origin: origin, r: r}
return s
}
func (s Sphere) Intersect(ray geom.Ray) bool {
l := sub(s.origin, ray.Origin)
tc := dot(l, ray.Direction)
if tc < 0.0 {
return false
}
d := math.Sqrt((tc * tc) - dot(l, l))
if d > s.r {
return false
}
return true
}
func main() {
a, b, c := geom.NewVector(-1, -1, 0), geom.NewVector(1, -1, 0), geom.NewVector(0, 1, 0)
tr := NewTriangle(a, b, c)
ray := geom.NewRay(geom.NewVector(0, 0, -1), geom.NewVector(0, 0, 1))
if tr.Intersect(ray) {
fmt.Println("ray intersects tr")
}
}

Лог от изпълнението

PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.004s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
--- FAIL: TestSphereSimpleIntersection (0.00s)
    solution_test.go:206: Expected intersection to be true but it was not
FAIL
exit status 1
FAIL	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.003s
PASS
ok  	_/tmp/d20181122-57-1wedugr	0.002s

История (4 версии и 3 коментара)

Габриела обнови решението на 19.11.2018 23:02 (преди 9 месеца)

+package main
+
+import (
+ "fmt"
+ "math"
+
+ "github.com/fmi/go-homework/geom"
+)
+
+func sub(a geom.Vector, b geom.Vector) geom.Vector {
+ v := geom.Vector{X: (a.X - b.X), Y: (a.Y - b.Y), Z: (a.Z - b.Z)}
+ return v
+}
+
+func cross(v geom.Vector, ov geom.Vector) geom.Vector {
+ result := geom.Vector{
+ X: v.Y*ov.Z - v.Z*ov.Y,
+ Y: v.Z*ov.X - v.X*ov.Z,
+ Z: v.X*ov.Y - v.Y*ov.X,
+ }
+ return result
+}
+
+func dot(v geom.Vector, ov geom.Vector) float64 {
+ return v.X*ov.X + v.Y*ov.Y + v.Z*ov.Z
+}
+
+type Triangle struct {
+ a, b, c geom.Vector
+}
+
+func NewTriangle(a, b, c geom.Vector) Triangle {
+ t := Triangle{a: a, b: b, c: c}
+ return t
+}
+
+func (tr Triangle) Intersect(ray geom.Ray) bool {
+ e1 := sub(tr.b, tr.a)
+ e2 := sub(tr.c, tr.a)
+ h := cross(ray.Direction, e2)
+ a := dot(e1, h)
+
+ if a > -0.00001 && a < 0.00001 {
+ return false
+ }
+
+ f := 1 / a
+ s := sub(ray.Origin, tr.a)
+ u := f * dot(s, h)
+
+ if u < 0.0 || u > 1.0 {
+ return false
+ }
+
+ q := cross(s, e1)
+ v := f * dot(ray.Direction, q)
+
+ if v < 0.0 || u+v > 1.0 {
+ return false
+ }
+
+ t := f * dot(e2, q)
+
+ if t > 0.00001 {
+ return true
+ }
+ return false
+}
+
+type Quad struct {
+ a, b, c, d geom.Vector
+}
+
+func NewQuad(a, b, c, d geom.Vector) Quad {
+ q := Quad{a: a, b: b, c: c, d: d}
+ return q
+}
+
+func (q Quad) Intersect(ray geom.Ray) bool {
+ t1 := NewTriangle(q.a, q.b, q.c)
+ if t1.Intersect(ray) {
+ return true
+ }
+ t2 := NewTriangle(q.a, q.c, q.d)
+ if t2.Intersect(ray) {
+ return true
+ }
+ return false
+}
+
+type Sphere struct {
+ origin geom.Vector
+ r float64
+}
+
+func NewSphere(origin geom.Vector, r float64) Sphere {
+ s := Sphere{origin: origin, r: r}
+ return s
+}
+
+func (s Sphere) Intersect(ray geom.Ray) bool {
+ l := sub(s.origin, ray.Origin)
+ tc := dot(l, ray.Direction)
+ if tc < 0.0 {
+ return false
+ }
+
+ d := math.Sqrt((tc * tc) - dot(l, l))
+ if d > s.r {
+ return false
+ }
+ return true
+}
+
+func main() {
+ a, b, c := geom.NewVector(-1, -1, 0), geom.NewVector(1, -1, 0), geom.NewVector(0, 1, 0)
+ tr := NewTriangle(a, b, c)
+
+ ray := geom.NewRay(geom.NewVector(0, 0, -1), geom.NewVector(0, 0, 1))
+
+ if tr.Intersect(ray) {
+ fmt.Println("ray intersects tr")
+ }
+}

Габриела обнови решението на 19.11.2018 23:21 (преди 9 месеца)

package main
import (
"fmt"
"math"
"github.com/fmi/go-homework/geom"
)
func sub(a geom.Vector, b geom.Vector) geom.Vector {
v := geom.Vector{X: (a.X - b.X), Y: (a.Y - b.Y), Z: (a.Z - b.Z)}
return v
}
func cross(v geom.Vector, ov geom.Vector) geom.Vector {
result := geom.Vector{
X: v.Y*ov.Z - v.Z*ov.Y,
Y: v.Z*ov.X - v.X*ov.Z,
Z: v.X*ov.Y - v.Y*ov.X,
}
return result
}
func dot(v geom.Vector, ov geom.Vector) float64 {
return v.X*ov.X + v.Y*ov.Y + v.Z*ov.Z
}
type Triangle struct {
a, b, c geom.Vector
}
func NewTriangle(a, b, c geom.Vector) Triangle {
t := Triangle{a: a, b: b, c: c}
return t
}
func (tr Triangle) Intersect(ray geom.Ray) bool {
e1 := sub(tr.b, tr.a)
e2 := sub(tr.c, tr.a)
h := cross(ray.Direction, e2)
a := dot(e1, h)
if a > -0.00001 && a < 0.00001 {
return false
}
f := 1 / a
s := sub(ray.Origin, tr.a)
u := f * dot(s, h)
if u < 0.0 || u > 1.0 {
return false
}
q := cross(s, e1)
v := f * dot(ray.Direction, q)
if v < 0.0 || u+v > 1.0 {
return false
}
t := f * dot(e2, q)
if t > 0.00001 {
return true
}
return false
}
type Quad struct {
a, b, c, d geom.Vector
}
func NewQuad(a, b, c, d geom.Vector) Quad {
q := Quad{a: a, b: b, c: c, d: d}
return q
}
func (q Quad) Intersect(ray geom.Ray) bool {
t1 := NewTriangle(q.a, q.b, q.c)
- if t1.Intersect(ray) {
- return true
- }
+ intersected1 := t1.Intersect(ray)
t2 := NewTriangle(q.a, q.c, q.d)
- if t2.Intersect(ray) {
- return true
- }
- return false
+ intersected2 := t2.Intersect(ray)
+ t3 := NewTriangle(q.a, q.b, q.d)
+ intersected3 := t3.Intersect(ray)
+ t4 := NewTriangle(q.c, q.b, q.d)
+ intersected4 := t4.Intersect(ray)
+ return intersected1 && intersected2 && intersected3 && intersected4
}
type Sphere struct {
origin geom.Vector
r float64
}
func NewSphere(origin geom.Vector, r float64) Sphere {
s := Sphere{origin: origin, r: r}
return s
}
func (s Sphere) Intersect(ray geom.Ray) bool {
l := sub(s.origin, ray.Origin)
tc := dot(l, ray.Direction)
if tc < 0.0 {
return false
}
d := math.Sqrt((tc * tc) - dot(l, l))
if d > s.r {
return false
}
return true
}
func main() {
a, b, c := geom.NewVector(-1, -1, 0), geom.NewVector(1, -1, 0), geom.NewVector(0, 1, 0)
tr := NewTriangle(a, b, c)
ray := geom.NewRay(geom.NewVector(0, 0, -1), geom.NewVector(0, 0, 1))
if tr.Intersect(ray) {
fmt.Println("ray intersects tr")
}
}

Габриела обнови решението на 19.11.2018 23:30 (преди 9 месеца)

package main
import (
"fmt"
"math"
"github.com/fmi/go-homework/geom"
)
func sub(a geom.Vector, b geom.Vector) geom.Vector {
v := geom.Vector{X: (a.X - b.X), Y: (a.Y - b.Y), Z: (a.Z - b.Z)}
return v
}
func cross(v geom.Vector, ov geom.Vector) geom.Vector {
result := geom.Vector{
X: v.Y*ov.Z - v.Z*ov.Y,
Y: v.Z*ov.X - v.X*ov.Z,
Z: v.X*ov.Y - v.Y*ov.X,
}
return result
}
func dot(v geom.Vector, ov geom.Vector) float64 {
return v.X*ov.X + v.Y*ov.Y + v.Z*ov.Z
}
type Triangle struct {
a, b, c geom.Vector
}
func NewTriangle(a, b, c geom.Vector) Triangle {
t := Triangle{a: a, b: b, c: c}
return t
}
func (tr Triangle) Intersect(ray geom.Ray) bool {
e1 := sub(tr.b, tr.a)
e2 := sub(tr.c, tr.a)
h := cross(ray.Direction, e2)
a := dot(e1, h)
if a > -0.00001 && a < 0.00001 {
return false
}
f := 1 / a
s := sub(ray.Origin, tr.a)
u := f * dot(s, h)
if u < 0.0 || u > 1.0 {
return false
}
q := cross(s, e1)
v := f * dot(ray.Direction, q)
if v < 0.0 || u+v > 1.0 {
return false
}
t := f * dot(e2, q)
if t > 0.00001 {
return true
}
return false
}
type Quad struct {
a, b, c, d geom.Vector
}
func NewQuad(a, b, c, d geom.Vector) Quad {
q := Quad{a: a, b: b, c: c, d: d}
return q
}
func (q Quad) Intersect(ray geom.Ray) bool {
t1 := NewTriangle(q.a, q.b, q.c)
intersected1 := t1.Intersect(ray)
t2 := NewTriangle(q.a, q.c, q.d)
intersected2 := t2.Intersect(ray)
t3 := NewTriangle(q.a, q.b, q.d)
intersected3 := t3.Intersect(ray)
t4 := NewTriangle(q.c, q.b, q.d)
intersected4 := t4.Intersect(ray)
- return intersected1 && intersected2 && intersected3 && intersected4
+ return (intersected1 || intersected2) && (intersected3 || intersected4)

Не мога да разбера защо ти трябват четири триъгълника. Замисли се какво ще стане с твоето решение ако четириъгълника не е изпъкнал.

Четири са точно заради кейса, в който четириъгълника е вдлъбнат, ако разделим четириъгълника 2 пъти с по 2 триъгълника в единия от кейсовете четириъгълника пак ще си е вдлъбнат (ще е истинското представяне на четириъгълника), а в дугия ще е изпъкнал. Просто в момента не ми се занимава да търся решението със смятането и на това решение сложнотта му е константа - няма да е мн по-различно.

}
type Sphere struct {
origin geom.Vector
r float64
}
func NewSphere(origin geom.Vector, r float64) Sphere {
s := Sphere{origin: origin, r: r}
return s
}
func (s Sphere) Intersect(ray geom.Ray) bool {
l := sub(s.origin, ray.Origin)
tc := dot(l, ray.Direction)
if tc < 0.0 {
return false
}
d := math.Sqrt((tc * tc) - dot(l, l))
if d > s.r {
return false
}
return true
}
func main() {
a, b, c := geom.NewVector(-1, -1, 0), geom.NewVector(1, -1, 0), geom.NewVector(0, 1, 0)
tr := NewTriangle(a, b, c)
ray := geom.NewRay(geom.NewVector(0, 0, -1), geom.NewVector(0, 0, 1))
if tr.Intersect(ray) {
fmt.Println("ray intersects tr")
}
}

Габриела обнови решението на 20.11.2018 16:16 (преди 9 месеца)

package main
import (
"fmt"
"math"
"github.com/fmi/go-homework/geom"
)
func sub(a geom.Vector, b geom.Vector) geom.Vector {
v := geom.Vector{X: (a.X - b.X), Y: (a.Y - b.Y), Z: (a.Z - b.Z)}
return v
}
func cross(v geom.Vector, ov geom.Vector) geom.Vector {
result := geom.Vector{
X: v.Y*ov.Z - v.Z*ov.Y,
Y: v.Z*ov.X - v.X*ov.Z,
Z: v.X*ov.Y - v.Y*ov.X,
}
return result
}
func dot(v geom.Vector, ov geom.Vector) float64 {
return v.X*ov.X + v.Y*ov.Y + v.Z*ov.Z
}
type Triangle struct {
a, b, c geom.Vector
}
func NewTriangle(a, b, c geom.Vector) Triangle {
t := Triangle{a: a, b: b, c: c}
return t
}
func (tr Triangle) Intersect(ray geom.Ray) bool {
e1 := sub(tr.b, tr.a)
e2 := sub(tr.c, tr.a)
h := cross(ray.Direction, e2)
a := dot(e1, h)
- if a > -0.00001 && a < 0.00001 {
- return false
- }
-
f := 1 / a
s := sub(ray.Origin, tr.a)
u := f * dot(s, h)
if u < 0.0 || u > 1.0 {
return false
}
q := cross(s, e1)
v := f * dot(ray.Direction, q)
if v < 0.0 || u+v > 1.0 {
return false
}
t := f * dot(e2, q)
-
if t > 0.00001 {
return true
}
return false
}
type Quad struct {
a, b, c, d geom.Vector
}
func NewQuad(a, b, c, d geom.Vector) Quad {
q := Quad{a: a, b: b, c: c, d: d}
return q
}
func (q Quad) Intersect(ray geom.Ray) bool {
t1 := NewTriangle(q.a, q.b, q.c)
intersected1 := t1.Intersect(ray)
t2 := NewTriangle(q.a, q.c, q.d)
intersected2 := t2.Intersect(ray)
t3 := NewTriangle(q.a, q.b, q.d)
intersected3 := t3.Intersect(ray)
t4 := NewTriangle(q.c, q.b, q.d)
intersected4 := t4.Intersect(ray)
return (intersected1 || intersected2) && (intersected3 || intersected4)
}
type Sphere struct {
origin geom.Vector
r float64
}
func NewSphere(origin geom.Vector, r float64) Sphere {
s := Sphere{origin: origin, r: r}
return s
}
func (s Sphere) Intersect(ray geom.Ray) bool {
l := sub(s.origin, ray.Origin)
tc := dot(l, ray.Direction)
if tc < 0.0 {
return false
}
d := math.Sqrt((tc * tc) - dot(l, l))
if d > s.r {
return false
}
return true
}
func main() {
a, b, c := geom.NewVector(-1, -1, 0), geom.NewVector(1, -1, 0), geom.NewVector(0, 1, 0)
tr := NewTriangle(a, b, c)
ray := geom.NewRay(geom.NewVector(0, 0, -1), geom.NewVector(0, 0, 1))
if tr.Intersect(ray) {
fmt.Println("ray intersects tr")
}
}