Решение на Пресичания от Мирослав Лалев

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

Към профила на Мирослав Лалев

Резултати

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

Код

package main
import (
"math"
"github.com/fmi/go-homework/geom"
)
const eps float64 = 1e-6
type Triangle struct {
a, b, c geom.Vector
}
func NewTriangle(a, b, c geom.Vector) Triangle {
return Triangle{a: a, b: b, c: c}
}
func (t Triangle) Intersect(ray geom.Ray) bool {
normal := t.getNormal()
n := dot(normal, ray.Direction)
if math.Abs(n) < eps {
// ray is parallel to the plane
return false
}
origDist := dot(normal, t.a)
correction := -(dot(normal, ray.Origin) + origDist) / n
if correction < 0 {
// ray either starts before the triangle with positive, or
// behind the triangle with negative direction
return false
}
intersectionPoint := sum(ray.Origin, vecXnum(ray.Direction, correction))
return t.checkIntersectionPoint(intersectionPoint, normal)
}
func (t Triangle) getNormal() geom.Vector {
ba, ca := diff(t.b, t.a), diff(t.c, t.a)
return cross(ba, ca)
}
func (t Triangle) checkIntersectionPoint(point, planeNormal geom.Vector) bool {
ba := diff(t.b, t.a)
pa := diff(point, t.a)
baXpa := cross(ba, pa)
if dot(planeNormal, baXpa) < 0 {
return false
}
ac := diff(t.a, t.c)
pc := diff(point, t.c)
acXpc := cross(ac, pc)
if dot(planeNormal, acXpc) < 0 {
return false
}
cb := diff(t.c, t.b)
pb := diff(point, t.b)
cbXpb := cross(cb, pb)
if dot(planeNormal, cbXpb) < 0 {
return false
}
return true
}
type Quad struct {
a, b, c, d geom.Vector
}
func NewQuad(a, b, c, d geom.Vector) Quad {
return Quad{a: a, b: b, c: c, d: d}
}
func (q Quad) Intersect(ray geom.Ray) bool {
// all four points will be in the same plane, so
// plane normal could be obtained from one of the triangles
t := NewTriangle(q.a, q.b, q.c)
normal := t.getNormal()
n := dot(normal, ray.Direction)
if math.Abs(n) < eps {
// ray is parallel to the plane
return false
}
origDist := dot(normal, t.a)
correction := -(dot(normal, ray.Origin) + origDist) / n
if correction < 0 {
// ray either starts before the triangle with positive, or
// behind the triangle with negative direction
return false
}
intersectionPoint := sum(ray.Origin, vecXnum(ray.Direction, correction))
return q.checkIntersectionPoint(intersectionPoint, normal)
}
func (q Quad) checkIntersectionPoint(point, planeNormal geom.Vector) bool {
ad := diff(q.a, q.d)
pd := diff(point, q.d)
if dot(planeNormal, cross(ad, pd)) < 0 {
return false
}
dc := diff(q.d, q.c)
pc := diff(point, q.c)
if dot(planeNormal, cross(dc, pc)) < 0 {
return false
}
cb := diff(q.c, q.b)
pb := diff(point, q.b)
if dot(planeNormal, cross(cb, pb)) < 0 {
return false
}
ba := diff(q.b, q.a)
pa := diff(point, q.a)
if dot(planeNormal, cross(ba, pa)) < 0 {
return false
}
return true
}
type Sphere struct {
origin geom.Vector
r float64
}
func NewSphere(origin geom.Vector, r float64) Sphere {
return Sphere{origin: origin, r: r}
}
func (s Sphere) Intersect(ray geom.Ray) bool {
delta := diff(s.origin, ray.Origin)
rayOriginHeight := dot(delta, normalize(ray.Direction))
intersection := dot(delta, delta) - rayOriginHeight*rayOriginHeight
if intersection > s.r {
return false
}
intersectHeight := math.Sqrt(s.r - intersection)
firstIntersection, secondIntersection := rayOriginHeight-intersectHeight, rayOriginHeight+intersectHeight
return firstIntersection >= 0 || secondIntersection >= 0
}
func normalize(a geom.Vector) geom.Vector {
len := math.Sqrt(a.X*a.X + a.Y*a.Y + a.Z*a.Z)
if len == 0 {
return a
}
return geom.Vector{X: a.X / len, Y: a.Y / len, Z: a.Z / len}
}
func sum(a, b geom.Vector) geom.Vector {
return geom.NewVector(a.X+b.X, a.Y+b.Y, a.Z+b.Z)
}
func diff(a, b geom.Vector) geom.Vector {
return geom.NewVector(a.X-b.X, a.Y-b.Y, a.Z-b.Z)
}
func vecXnum(a geom.Vector, n float64) geom.Vector {
return geom.NewVector(a.X*n, a.Y*n, a.Z*n)
}
func cross(a, b geom.Vector) geom.Vector {
return geom.NewVector(a.Y*b.Z-a.Z*b.Y, a.Z*b.X-a.X*b.Z, a.X*b.Y-a.Y*b.X)
}
func dot(a, b geom.Vector) float64 {
return a.X*b.X + a.Y*b.Y + a.Z*b.Z
}

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

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

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

Мирослав обнови решението на 18.11.2018 22:02 (преди 9 месеца)

+package main
+
+import (
+ "math"
+
+ "github.com/fmi/go-homework/geom"
+)
+
+const eps float64 = 1e-6
+
+type Triangle struct {
+ a, b, c geom.Vector
+}
+
+func NewTriangle(a, b, c geom.Vector) Triangle {
+ return Triangle{a: a, b: b, c: c}
+}
+
+func (t Triangle) Intersect(ray geom.Ray) bool {
+ normal := t.getNormal()
+ n := dot(normal, ray.Direction)
+ if math.Abs(n) < eps {
+ // ray is parallel to the plane
+ return false
+ }
+
+ origDist := dot(normal, t.a)
+ correction := -(dot(normal, ray.Origin) + origDist) / n
+ if correction < 0 {
+ // ray either starts before the triangle with positive, or
+ // behind the triangle with negative direction
+ return false
+ }
+
+ intersectionPoint := sum(ray.Origin, vecXnum(ray.Direction, correction))
+ return t.checkIntersectionPoint(intersectionPoint, normal)
+}
+
+func (t Triangle) getNormal() geom.Vector {
+ ba, ca := diff(t.b, t.a), diff(t.c, t.a)
+ return cross(ba, ca)
+}
+
+func (t Triangle) checkIntersectionPoint(point, planeNormal geom.Vector) bool {
+ ba := diff(t.b, t.a)
+ pa := diff(point, t.a)
+ if dot(planeNormal, cross(ba, pa)) < 0 {
+ return false
+ }
+ ac := diff(t.a, t.c)
+ pc := diff(point, t.c)
+ if dot(planeNormal, cross(ac, pc)) < 0 {
+ return false
+ }
+ cb := diff(t.c, t.b)
+ pb := diff(point, t.b)
+ if dot(planeNormal, cross(cb, pb)) < 0 {
+ return false
+ }
+ return true
+}
+
+type Quad struct {
+ a, b, c, d geom.Vector
+}
+
+func NewQuad(a, b, c, d geom.Vector) Quad {
+ return Quad{a: a, b: b, c: c, d: d}
+}
+
+func (q Quad) Intersect(ray geom.Ray) bool {
+ // all four points will be in the same plane, so
+ // plane normal could be obtained from one of the triangles
+ t := NewTriangle(q.a, q.b, q.c)
+ normal := t.getNormal()
+ n := dot(normal, ray.Direction)
+ if math.Abs(n) < eps {
+ // ray is parallel to the plane
+ return false
+ }
+
+ origDist := dot(normal, t.a)
+ correction := -(dot(normal, ray.Origin) + origDist) / n
+ if correction < 0 {
+ // ray either starts before the quad with positive, or
+ // behind the quad with negative direction
+ return false
+ }
+
+ intersectionPoint := sum(ray.Origin, vecXnum(ray.Direction, correction))
+ return q.checkIntersectionPoint(intersectionPoint, normal)
+}
+
+func (q Quad) checkIntersectionPoint(point, planeNormal geom.Vector) bool {
+ ba := diff(q.b, q.a)
+ pa := diff(point, q.a)
+ if dot(planeNormal, cross(ba, pa)) < 0 {
+ return false
+ }
+ ac := diff(q.a, q.c)
+ pc := diff(point, q.c)
+ if dot(planeNormal, cross(ac, pc)) < 0 {
+ return false
+ }
+ cd := diff(q.c, q.d)
+ pd := diff(point, q.d)
+ if dot(planeNormal, cross(cd, pd)) < 0 {
+ return false
+ }
+ db := diff(q.d, q.b)
+ pb := diff(point, q.b)
+ if dot(planeNormal, cross(db, pb)) < 0 {
+ return false
+ }
+ return true
+}
+
+type Sphere struct {
+ origin geom.Vector
+ r float64
+}
+
+func NewSphere(origin geom.Vector, r float64) Sphere {
+ return Sphere{origin: origin, r: r}
+}
+
+func (s Sphere) Intersect(ray geom.Ray) bool {
+ delta := diff(s.origin, ray.Origin)
+ rayOriginHeight := dot(delta, ray.Direction)
+ d2 := dot(delta, delta) - rayOriginHeight*rayOriginHeight
+ if d2 > s.r {
+ return false
+ }
+ intersectHeight := math.Sqrt(s.r - d2)
+ firstIntersection, secondIntersection := rayOriginHeight-intersectHeight, rayOriginHeight+intersectHeight
+ return firstIntersection >= 0 || secondIntersection >= 0
+}
+
+func sum(a, b geom.Vector) geom.Vector {
+ return geom.NewVector(a.X+b.X, a.Y+b.Y, a.Z+b.Z)
+}
+
+func diff(a, b geom.Vector) geom.Vector {
+ return geom.NewVector(a.X-b.X, a.Y-b.Y, a.Z-b.Z)
+}
+
+func vecXnum(a geom.Vector, n float64) geom.Vector {
+ return geom.NewVector(a.X*n, a.Y*n, a.Z*n)
+}
+
+func cross(a, b geom.Vector) geom.Vector {
+ return geom.NewVector(a.Y*b.Z-a.Z*b.Y, a.Z*b.X-a.X*b.Z, a.X*b.Y-a.Y*b.X)
+}
+
+func dot(a, b geom.Vector) float64 {
+ return a.X*b.X + a.Y*b.Y + a.Z*b.Z
+}

Бих ти препоръчал да си напишеш няколко теста и да видиш дали всяка фигура работа. А не да разчиташ на sample теста.

А за да ти отговоря на оригиналния въпрос - точките ще са в ред. По часовниковата стрелка или обратно, но винаги в ред.

Не си спомням какво правят в учебниците по математика. Но ако вземеш молив работещ в 3D пространството и чертаеш линии от точка до точка в същия ред, в който са дадени на конструктор функцията, ще имаш четириъгълник.

Мирослав обнови решението на 21.11.2018 00:38 (преди 9 месеца)

package main
import (
"math"
"github.com/fmi/go-homework/geom"
)
const eps float64 = 1e-6
type Triangle struct {
a, b, c geom.Vector
}
func NewTriangle(a, b, c geom.Vector) Triangle {
return Triangle{a: a, b: b, c: c}
}
func (t Triangle) Intersect(ray geom.Ray) bool {
normal := t.getNormal()
n := dot(normal, ray.Direction)
if math.Abs(n) < eps {
// ray is parallel to the plane
return false
}
origDist := dot(normal, t.a)
correction := -(dot(normal, ray.Origin) + origDist) / n
if correction < 0 {
// ray either starts before the triangle with positive, or
// behind the triangle with negative direction
return false
}
intersectionPoint := sum(ray.Origin, vecXnum(ray.Direction, correction))
return t.checkIntersectionPoint(intersectionPoint, normal)
}
func (t Triangle) getNormal() geom.Vector {
ba, ca := diff(t.b, t.a), diff(t.c, t.a)
return cross(ba, ca)
}
func (t Triangle) checkIntersectionPoint(point, planeNormal geom.Vector) bool {
ba := diff(t.b, t.a)
pa := diff(point, t.a)
- if dot(planeNormal, cross(ba, pa)) < 0 {
+ baXpa := cross(ba, pa)
+ if dot(planeNormal, baXpa) < 0 {
return false
}
ac := diff(t.a, t.c)
pc := diff(point, t.c)
- if dot(planeNormal, cross(ac, pc)) < 0 {
+ acXpc := cross(ac, pc)
+ if dot(planeNormal, acXpc) < 0 {
return false
}
cb := diff(t.c, t.b)
pb := diff(point, t.b)
- if dot(planeNormal, cross(cb, pb)) < 0 {
+ cbXpb := cross(cb, pb)
+ if dot(planeNormal, cbXpb) < 0 {
return false
}
return true
}
type Quad struct {
a, b, c, d geom.Vector
}
func NewQuad(a, b, c, d geom.Vector) Quad {
return Quad{a: a, b: b, c: c, d: d}
}
func (q Quad) Intersect(ray geom.Ray) bool {
// all four points will be in the same plane, so
// plane normal could be obtained from one of the triangles
t := NewTriangle(q.a, q.b, q.c)
normal := t.getNormal()
n := dot(normal, ray.Direction)
if math.Abs(n) < eps {
// ray is parallel to the plane
return false
}
origDist := dot(normal, t.a)
correction := -(dot(normal, ray.Origin) + origDist) / n
if correction < 0 {
- // ray either starts before the quad with positive, or
- // behind the quad with negative direction
+ // ray either starts before the triangle with positive, or
+ // behind the triangle with negative direction
return false
}
intersectionPoint := sum(ray.Origin, vecXnum(ray.Direction, correction))
return q.checkIntersectionPoint(intersectionPoint, normal)
}
func (q Quad) checkIntersectionPoint(point, planeNormal geom.Vector) bool {
- ba := diff(q.b, q.a)
- pa := diff(point, q.a)
- if dot(planeNormal, cross(ba, pa)) < 0 {
+ ad := diff(q.a, q.d)
+ pd := diff(point, q.d)
+ if dot(planeNormal, cross(ad, pd)) < 0 {
return false
}
- ac := diff(q.a, q.c)
+ dc := diff(q.d, q.c)
pc := diff(point, q.c)
- if dot(planeNormal, cross(ac, pc)) < 0 {
+ if dot(planeNormal, cross(dc, pc)) < 0 {
return false
}
- cd := diff(q.c, q.d)
- pd := diff(point, q.d)
- if dot(planeNormal, cross(cd, pd)) < 0 {
+ cb := diff(q.c, q.b)
+ pb := diff(point, q.b)
+ if dot(planeNormal, cross(cb, pb)) < 0 {
return false
}
- db := diff(q.d, q.b)
- pb := diff(point, q.b)
- if dot(planeNormal, cross(db, pb)) < 0 {
+ ba := diff(q.b, q.a)
+ pa := diff(point, q.a)
+ if dot(planeNormal, cross(ba, pa)) < 0 {
return false
}
return true
}
type Sphere struct {
origin geom.Vector
r float64
}
func NewSphere(origin geom.Vector, r float64) Sphere {
return Sphere{origin: origin, r: r}
}
func (s Sphere) Intersect(ray geom.Ray) bool {
delta := diff(s.origin, ray.Origin)
rayOriginHeight := dot(delta, ray.Direction)

Малко ми беше трудно да измисля подходящо име... Това е височината, спусната от origin към правата, която е перпендикулярна на пресичащия лъч. :Д

Иначе да, приел съм че е нормализиран. Ще си го сметна сам.

d2 := dot(delta, delta) - rayOriginHeight*rayOriginHeight
if d2 > s.r {
return false
}
intersectHeight := math.Sqrt(s.r - d2)
firstIntersection, secondIntersection := rayOriginHeight-intersectHeight, rayOriginHeight+intersectHeight
return firstIntersection >= 0 || secondIntersection >= 0
}
func sum(a, b geom.Vector) geom.Vector {
return geom.NewVector(a.X+b.X, a.Y+b.Y, a.Z+b.Z)
}
func diff(a, b geom.Vector) geom.Vector {
return geom.NewVector(a.X-b.X, a.Y-b.Y, a.Z-b.Z)
}
func vecXnum(a geom.Vector, n float64) geom.Vector {
return geom.NewVector(a.X*n, a.Y*n, a.Z*n)
}
func cross(a, b geom.Vector) geom.Vector {
return geom.NewVector(a.Y*b.Z-a.Z*b.Y, a.Z*b.X-a.X*b.Z, a.X*b.Y-a.Y*b.X)
}
func dot(a, b geom.Vector) float64 {
return a.X*b.X + a.Y*b.Y + a.Z*b.Z
}

Мирослав обнови решението на 21.11.2018 00:58 (преди 9 месеца)

package main
import (
"math"
"github.com/fmi/go-homework/geom"
)
const eps float64 = 1e-6
type Triangle struct {
a, b, c geom.Vector
}
func NewTriangle(a, b, c geom.Vector) Triangle {
return Triangle{a: a, b: b, c: c}
}
func (t Triangle) Intersect(ray geom.Ray) bool {
normal := t.getNormal()
n := dot(normal, ray.Direction)
if math.Abs(n) < eps {
// ray is parallel to the plane
return false
}
origDist := dot(normal, t.a)
correction := -(dot(normal, ray.Origin) + origDist) / n
if correction < 0 {
// ray either starts before the triangle with positive, or
// behind the triangle with negative direction
return false
}
intersectionPoint := sum(ray.Origin, vecXnum(ray.Direction, correction))
return t.checkIntersectionPoint(intersectionPoint, normal)
}
func (t Triangle) getNormal() geom.Vector {
ba, ca := diff(t.b, t.a), diff(t.c, t.a)
return cross(ba, ca)
}
func (t Triangle) checkIntersectionPoint(point, planeNormal geom.Vector) bool {
ba := diff(t.b, t.a)
pa := diff(point, t.a)
baXpa := cross(ba, pa)
if dot(planeNormal, baXpa) < 0 {
return false
}
ac := diff(t.a, t.c)
pc := diff(point, t.c)
acXpc := cross(ac, pc)
if dot(planeNormal, acXpc) < 0 {
return false
}
cb := diff(t.c, t.b)
pb := diff(point, t.b)
cbXpb := cross(cb, pb)
if dot(planeNormal, cbXpb) < 0 {
return false
}
return true
}
type Quad struct {
a, b, c, d geom.Vector
}
func NewQuad(a, b, c, d geom.Vector) Quad {
return Quad{a: a, b: b, c: c, d: d}
}
func (q Quad) Intersect(ray geom.Ray) bool {
// all four points will be in the same plane, so
// plane normal could be obtained from one of the triangles
t := NewTriangle(q.a, q.b, q.c)
normal := t.getNormal()
n := dot(normal, ray.Direction)
if math.Abs(n) < eps {
// ray is parallel to the plane
return false
}
origDist := dot(normal, t.a)
correction := -(dot(normal, ray.Origin) + origDist) / n
if correction < 0 {
// ray either starts before the triangle with positive, or
// behind the triangle with negative direction
return false
}
intersectionPoint := sum(ray.Origin, vecXnum(ray.Direction, correction))
return q.checkIntersectionPoint(intersectionPoint, normal)
}
func (q Quad) checkIntersectionPoint(point, planeNormal geom.Vector) bool {
ad := diff(q.a, q.d)
pd := diff(point, q.d)
if dot(planeNormal, cross(ad, pd)) < 0 {
return false
}
dc := diff(q.d, q.c)
pc := diff(point, q.c)
if dot(planeNormal, cross(dc, pc)) < 0 {
return false
}
cb := diff(q.c, q.b)
pb := diff(point, q.b)
if dot(planeNormal, cross(cb, pb)) < 0 {
return false
}
ba := diff(q.b, q.a)
pa := diff(point, q.a)
if dot(planeNormal, cross(ba, pa)) < 0 {
return false
}
return true
}
type Sphere struct {
origin geom.Vector
r float64
}
func NewSphere(origin geom.Vector, r float64) Sphere {
return Sphere{origin: origin, r: r}
}
func (s Sphere) Intersect(ray geom.Ray) bool {
delta := diff(s.origin, ray.Origin)
- rayOriginHeight := dot(delta, ray.Direction)
- d2 := dot(delta, delta) - rayOriginHeight*rayOriginHeight
- if d2 > s.r {
+ rayOriginHeight := dot(delta, normalize(ray.Direction))
+ intersection := dot(delta, delta) - rayOriginHeight*rayOriginHeight
+ if intersection > s.r {
return false
}
- intersectHeight := math.Sqrt(s.r - d2)
+ intersectHeight := math.Sqrt(s.r - intersection)
firstIntersection, secondIntersection := rayOriginHeight-intersectHeight, rayOriginHeight+intersectHeight
return firstIntersection >= 0 || secondIntersection >= 0
+}
+
+func normalize(a geom.Vector) geom.Vector {
+ len := math.Sqrt(a.X*a.X + a.Y*a.Y + a.Z*a.Z)
+ if len == 0 {
+ return a
+ }
+ return geom.Vector{X: a.X / len, Y: a.Y / len, Z: a.Z / len}
}
func sum(a, b geom.Vector) geom.Vector {
return geom.NewVector(a.X+b.X, a.Y+b.Y, a.Z+b.Z)
}
func diff(a, b geom.Vector) geom.Vector {
return geom.NewVector(a.X-b.X, a.Y-b.Y, a.Z-b.Z)
}
func vecXnum(a geom.Vector, n float64) geom.Vector {
return geom.NewVector(a.X*n, a.Y*n, a.Z*n)
}
func cross(a, b geom.Vector) geom.Vector {
return geom.NewVector(a.Y*b.Z-a.Z*b.Y, a.Z*b.X-a.X*b.Z, a.X*b.Y-a.Y*b.X)
}
func dot(a, b geom.Vector) float64 {
return a.X*b.X + a.Y*b.Y + a.Z*b.Z
}