Commit2ebecc1

authored

Bug in the face order check (#1394)

* Fixed face order check* Update test_planar_faces.cpp

1 parentdfacc51 commit2ebecc1Copy full SHA for 2ebecc1

File tree

+33

-13

lines changed

+33

-13

lines changed

Lines changed: 7 additions & 13 deletions

Original file line number	Diff line number	Diff line change
`@@ -125,20 +125,14 @@ std::vector<std::vector<size_t>> find_faces(std::vector<Point> vertices, std::ve`
`125`	`125`	`e = e1;`
`126`	`126`	`}`
`127`	`127`	`std::reverse(face.begin(), face.end());`
`128`		`- int sign = 0;`
`129`		`- for (size_t j = 0; j < face.size(); j++) {`
`130`		`- size_t j1 = (j + 1) % face.size();`
`131`		`- size_t j2 = (j + 2) % face.size();`
`132`		`- int64_t val = vertices[face[j]].cross(vertices[face[j1]], vertices[face[j2]]);`
`133`		`- if (val > 0) {`
`134`		`- sign = 1;`
`135`		`- break;`
`136`		`- } else if (val < 0) {`
`137`		`- sign = -1;`
`138`		`- break;`
`139`		`- }`
	`128`	`+ Point p1 = vertices[face[0]];`
	`129`	`+__int128 sum = 0;`
	`130`	`+ for (int j = 0; j < face.size(); ++j) {`
	`131`	`+ Point p2 = vertices[face[j]];`
	`132`	`+ Point p3 = vertices[face[(j + 1) % face.size()]];`
	`133`	`+ sum += (p2 - p1).cross(p3 - p2);`
`140`	`134`	`}`
`141`		`- if (sign <= 0) {`
	`135`	`+ if (sum <= 0) {`
`142`	`136`	`faces.insert(faces.begin(), face);`
`143`	`137`	`} else {`
`144`	`138`	`faces.emplace_back(face);`

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -93,8 +93,34 @@ void test_cycle_with_chain() {`
`93`	`93`	`assert(equal_cycles(faces[1], {2,5,4,5,2,1,0,3}));`
`94`	`94`	`}`
`95`	`95`
	`96`	`+voidtest_ccw_angle() {`
	`97`	`+ std::vector<Point> p = {`
	`98`	`+Point(0,2),`
	`99`	`+Point(1,3),`
	`100`	`+Point(0,1),`
	`101`	`+Point(1,0),`
	`102`	`+Point(-1,0),`
	`103`	`+Point(-1,3)`
	`104`	`+ };`
	`105`	`+`
	`106`	`+ std::vector<std::vector<size_t>> adj = {`
	`107`	`+ {1,5},`
	`108`	`+ {0,2},`
	`109`	`+ {1,3},`
	`110`	`+ {2,4},`
	`111`	`+ {3,5},`
	`112`	`+ {0,4}`
	`113`	`+ };`
	`114`	`+`
	`115`	`+auto faces =find_faces(p, adj);`
	`116`	`+assert(faces.size() ==2u);`
	`117`	`+assert(equal_cycles(faces[0], {0,1,2,3,4,5}));`
	`118`	`+assert(equal_cycles(faces[1], {5,4,3,2,1,0}));`
	`119`	`+}`
	`120`	`+`
`96`	`121`	`intmain() {`
`97`	`122`	`test_simple();`
`98`	`123`	`test_degenerate();`
`99`	`124`	`test_cycle_with_chain();`
	`125`	`+test_ccw_angle();`
`100`	`126`	`}`

Comments

(0)