/*
ReferenceFinder - a program for finding efficient folding sequences for locating reference
points and lines in a unit square.
Version 3.1
Copyright ©1999-2003 by Robert J. Lang. All rights reserved.
RIGHTS OF USAGE
You may distribute the compiled executable freely so long as you do not charge for it.
You may compile the code and modifications thereof for your own personal use.
You may not redistribute this code or modifications thereof.
The software and code are supplied as-is, with no warranties of fitness for any given purpose.
ACKNOWLEDGEMENTS AND THANKS
Thanks to the following contributors:
Carlos A. Furuti -- Linux compatibility/porting and expression parser/evaluator
Robert Allan Schwartz -- Windows compatibility/porting
WHAT IT DOES
ReferenceFinder is a program that constructs folding sequences for reference points in
a square. When you run it, ReferenceFinder first builds a database of marks (points) and
lines that have short folding sequences. This takes 30 to 90 seconds. You then select
whether the reference you are seeking will be a point (enter 1) or a line (enter 2).
If a point, you will be prompted for its x and y coordinates, which should be between
0 and 1.
If a line, you will be prompted for the x and y coordinates of any two points on the
line. They should be distinct, obviously.
You can enter coordinates either as their decimal values (e.g., 0.4142), or as a mathematical
expression (e.g., sqrt(2)-1, or even d-1). Expressions may contain any of the operators +, -,
*, /, ^, (), sqrt, sin, cos, tan, deg2rad and constants e/pi/phi/Phi; d is an abbreviation
for sqrt(2), which shows up a lot in origami crease patterns. Trigonometric functions use
radians, deg2rad converts degrees to radians.
Once you have entered the point or line, ReferenceFinder will print out verbal instructions
for 5 folding sequences that give close approximations of the the point or line you entered.
For 97% of points, the approximated point will be within 0.005 of the target point. (The other
3% are still pretty close.) Lines are similarly close to their targets.
In addition to the verbal instructions, ReferenceFinder writes a file, "ReferenceFinder_xxx.ps"
(where xxx is a number), which contains PostScript code for the folding diagrams. You can use
GhostScript or Adobe Acrobat Distiller to convert the file to a viewable format. The numbering
restarts each time you run ReferenceFinder; if you want to keep the diagrams, move them to a
different directory or rename the file(s).
HOW IT DOES IT
There are 7 possible ways of defining a fold in terms of alignments between points
and lines (known as the "Huzita-Hatori Axioms"). ReferenceFinder starts with an unmarked
square and recursively constructs all distinct lines (and points, which are defined as
intersections between pairs of lines) that use no more than 6 sequential HHA operations.
Along the way, ReferenceFinder filters the list to weed out duplicates and folds that are
difficult to make precisely in practice.
When you enter a point or line, ReferenceFinder searches through this list and picks out the
points or lines closest to the one you entered.
FOR MAC, WINDOWS, LINUX, AND/OR NON_PROGRAMMERS
The distribution contains a folder, /executables/, that contains executables for Mac,
Windows, and Linux.
/mac/ReferenceFinder 3.1 -- runs on Mac OS 9 and X.
/mac/ReferenceFinder 3.1 Classic -- runs on OS 8.
/win/ReferenceFinder 3.1 -- runs on Windows 98 and XP (I'm not sure about others; try it.)
/linux/ReferenceFinder -- runs on Linux on i586.
FOR OTHER PLATFORMS AND/OR PROGRAMMERS
ReferenceFinder is ANSI C++ code that should compile for any compiler/platform
that supports the C++ standard library. For ease of portability, ReferenceFinder is a
text-based program that uses the standard console, cin and cout, for user interaction.
However, it has a fairly clean API that supports integration with a GUI and/or a
variety of imaging models for the diagrams, if anyone were so inclined to write one.
The source code consists of:
lexer.h -- header for the lexical analyzer
lexer.cpp -- implementation of the lexical analyzer
parser.h -- header for the expression evaluator
parser.cpp -- implementation of the expression evaluator
ReferenceFinder.h -- header for reference point/line construction and searches
ReferenceFinder.cpp -- implementation for reference point/line construction and searches
ReferenceFinder_console.cpp -- a console-based main program.
(Linux/Unix specific)
makefile.unx -- compatible with most versions of "make"
(Mac specific)
carb.r -- resource file needed for Carbon compliance on Mac
ReferenceFinder_mac.mcp -- CodeWarrior 8 project file with targets for Mac and Win32
For other compilers and/or platforms, ReferenceFinder 3 should compile with minimal modification
for any compiler that supports the C++ standard (including templates). Email me if you find
bugs or incompatibilities.
ReferenceFinder uses a lot of memory during initialization. You should allocate 60 MB of RAM
to the program.
PROGRAM NOTES AND HISTORY
Version 3.1b1
-- Added more information to verbal output and PostScript diagrams, including the target
point and coordinates of each solution point.
-- Added number to ReferenceFinder_xxx.ps so you can find multiple points within a single
session without having to rename the file after every search.
Version 3.0, released 2003-06-12.
-- Minor cleanups to README.txt.
Version 3.0b8
-- From Carlos: in order to avoid portability problems, all-new lexer.cpp/h fully replace
expr.l/lex.yy.c/y.tab.h. Patched parser.cpp and parser.h now fully C++ citizens;
no more global vars or yacc types.
ReferenceFinder.cpp suffered minor changes:
- several switch cases left unhandled, now marked explicitly
- added a void* parameter to the progress callback. It can be useful at a GUI
if no global vars are available to give context. Incidentally it's not needed in my
particular wxW GUI.
ReferenceFinder_console.cpp: typing <Enter> is accepted as zero, except at the
0/1/2 prompt
Makefile.unx had a little polish.
parser.cpp/expr.l: RJL's fixes for compiling in CodeWarrior (interim from b7) no
more necessary with new lexer.
ReferenceFinder.cpp - in lines 4567 and 4537, "%Page" should be "%%Page" - it's all my fault
Version 3.0b7
-- New and improved parser from Carlos!
Files changed:
- makefile.unx (creates executable in executables/linux)
- expr.y, y.tab.c (deleted)
- expr.l/lex.yy.c
- ReferenceFinder_console.cpp
- y.tab.h
- parser.cpp, parser.h (new)
-- RJL has made further small changes to parser.cpp and lex.yy.c to make CodeWarrior happy.
-- Added PS comments and pagination comments to PSFileDgmr since Ghostview is not as forgiving
as Acrobat Distiller.
Version 3.0b6
-- Reorganized distribution folders and files. Made makefiles specific to win and lin.
-- Renamed "ReferenceFinder_main.cpp" to "ReferenceFinder_console.cpp".
-- Fixed a bug in arrow generation in Axiom 1 in which arrows didn't connect mating points.
-- Fixed a bug in Axiom 7 whereby an illegal alignment (pt-to-line where pt is already on the line)
was getting through. This slightly reduces the total number of marks and lines.
-- Added multipass drawing to diagrams so that (among other things) hilited lines are always on top
of non-hilited lines and labels are always on top of everything else.
-- Fixed a bug in diagram generation that improperly hilited some refs within diagrams.
-- Added the RefBase::IsDerived() method, which was necessary to fix the diagram generation bug, but
is also generally useful.
-- Added RefBase::ClarifyVerbalAmbiguities() to turn on/off additional coordinate information in
verbal instructions that resolves ambiguities when there are multiple solutions for a given
alignment.
-- Added RefBase::SetAxiomsInVerbalDirections() to turn on/off the axiom numbers in the verbal
directions.
-- Added RefBase::GetLabel(), which returns the single-character label for a mark or line (or a
null character for original refs).
-- Minor typedef cleanup involving rank_t and index_t (typedef'd as short to minimize object size).
Version 3.0b5
-- Replaced find() and map<>.operator[] with map<>.count() and map<>.insert() for a slight speedup.
-- Moved RefLine_L2L up in priority above RefLine_P2P, since the former are what people usually
think of doing when folding a square in half.
-- Removed pragmas for portability
-- Fixed a bug in BuildDiagrams that arose if you passed a RefMark_Original or RefLine_Original.
Version 3.0b4
-- Added a new class, RefDgmr, and two examples (ConsoleTextDgmr and PSFileDgmr) for generating
diagrams. RefDgmr provides an API for any GUI that wants to show diagrams. The old text-
based output routines have now been rolled into ConsoleTextDgmr. The new class PSFileDgmr
generates a Postscript file that provides folding diagrams for the most-recently-sought
mark or line. PSFileDgmr also provides a template for how other descendants of RefDgmr
might be written to implement other imaging models (e.g., OpenGLDgmr, QuartzDgmr,
TclDgmr...).
-- Added two routines designed specifically for diagrams:
RefBase::DrawDiagram(RefDgmr&, DgmInfo), which draws the image of a diagram using the
imaging model specified by the RefDgmr;
RefBase::PutDiagramCaption(ostream&, DgmInfo), which puts the caption for a particular
diagram to a stream (similar to how PutHowtoSequence puts the entire verbal description
to a stream).
-- Numerous small changes to permissions, function names, and ownership of static member variables
for reasons of compatiblity with the new RefDgmr class (and its descendants) and general
cleanliness of code.
-- Removed the sayWhat global in favor of a compiler switch, NO_CONSOLE, which, if #defined,
suppresses all output calls to the console in compilation.
Version 3.0b3
-- Carlos updated the expression evaluator to accept leading decimal points (e.g., ".2"),
which it didn't used to do.
-- Moved all of the global settings (e.g., minAspectRatio, maxRank, etc.) into the new object
ReferenceFinder. Also global search routines are now part of the object. Projects that embed
don't have to declare anything extern, then can just #include ReferenceFinder.h.
-- Adjusted some public/protected/private permissions for RefBase methods.
-- MakeAllMarksAndLines() can now be called repeatedly if you decide to change some of the global
settings.
Version 3.0b2 (5-12-03)
-- Added expression evaluator by Carlos Furuti.
-- Cleaned up signed/unsigned inconsistencies, added typename keywords for compatibility with gcc.
-- Fixed a bug in Axiom 7 that allowed alignments involving points not on the paper
-- Added more description to the output of Axiom 6 to disambiguate cases where there are
multiple solutions for a given alignment.
-- Replaced Paper::Overlaps(), Paper::GetEndpoints() with Paper::InteriorOverlaps() and
Paper::ClipLine(), which are cleaner implementations of the concept.
-- Created globals minAngleSine and minAspectRatio, which are used to filter out (respectively)
RefMarks formed by the intersection of two nearly-parallel angles, and RefLines that require
folding a long skinny flap near the edge of the paper.
Version 3.0b1 (5-6-03)
Version 3 is almost completely rewritten from version 2.1 and its predecessors.
-- I have implemented all 7 of the Huzita-Hatori Axioms, which are all the things you
can do with a single crease.
-- Version 3 contains no duplicate lines or marks. Duplicates are avoided by a new scheme
of storing objects that uses the C++ map<> class and distinct keys associated with each
mark or line.
-- The combination of more axioms and elimination of duplication means that Version 3
provides better accuracy than versions 1 or 2 with fewer creases. Nothing has a rank
higher than 6 (2 fewer than version 2.1).
-- Version 3 also checks visibility of alignments and won't create an alignment that can't
be made with opaque paper.
-- There are many switches and compiler-level custom settings that let you adjust the
level of accuracy and the tradeoffs with speed and memory.
CONTACT INFORMATION
For comments, bugs, attaboys, etc., please contact me, Robert J. Lang, via this page:
http://www.langorigami.com/info/contact.php4.
*/