Problem 52334. ICFP2021 Hole-In-Wall: Figure Validation with Segment Crossing and Segment on Wall Checks

The ICFP held its annual 3-day contest in July 2021 with Hole-In-Wall. Contest Specification.
The contest folds the figure in Red to fit within the hole shown in light grey
This Challenge is to evaluate the complete Figure validation defined in the Specification when given the hole vertices in hxy, original figure vertices in pxy, updated figure vertices in npxy, segment matrix mseg, and epsilon. The hxy matrix is [N+1,2] where N is number of hole vertices. A repeat of the first vertex occurs for drawing the hole. The pxy(original) and npxy(final) matrices are [P,2] where P is the number of figure vertices. The mseg indicates connected vertices that must maintain a length as a function of epsilon from the original length. The final figure vertices must be integer thus the allowed fuzziness of segment lengths.
Valid is 1) all npxy vertices must be on or inside the hole, hxy 2) all npxy segments must match the pxy segments within an allowed epsilon, abs(Lsqr(npxy,seg(i,:))/Lsqr(pxy,seg(i,:))-1)<= epsilon/1000000. Lsqr is length squared 3) No figure segments may cross hole segments. Segment vertices may touch segments. No part of any Red segment should be outside the hole shown in light grey. 4) Pathological cases of Segments crossing Wall region between Hole Vertices or from figure vertices on Hole edges is not allowed.
Valid=check_figureSP(hxy, pxy, mseg, epsilon, npxy)
Crossing Segments appears in Cody 1720 but the test set is not strong. A 7/18/21 solution of size 117 is robust and fast. See the function template for reference material to solve intersecting segments.
The ICFP 2021 Hole In Wall contest site has enabled a public user login to allow submissions. A login must be created to access all the problems and to submit solutions. Solutions are simple text files. Other challenges will show reading files, drawing figures, and producing submission files. To fully access the ICFP/Problems site use Register Team. Anyone can select Problems Page and then click problem numbers to see the puzzles and to download problem files.
Solve

Solution Stats

75.0% Correct | 25.0% Incorrect
Last Solution submitted on Jul 23, 2021

Solution Comments

Show comments

Problem Recent Solvers2

Suggested Problems

More from this Author308

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!