FAQ about ex4:   (Last updated:  Sun 28/05/06)

-----------------------------------------------------------------------------

0: (a meta-question)

Q: Who asks these questions? Who answers them?

A: Students of the CG class ask the questions; Osnat answers them.  Any
   further questions about the answers in this file should be directed to
   Osnat.

-----------------------------------------------------------------------------

1:

Q: Is it ok to program in Python language?

A: Yes, in some version constraints (talk to Osnat).

-----------------------------------------------------------------------------

2:

Q: About the output format. Consider the following example: 
   consider the symmetric difference of two triangles which create a "star of
   david"-like shape. Which is the desired output:
   1) A single star-like polygon with one hexagonal hole.
   2) 6 triangle polygons with no holes.

A: 2 - 6 triangle polygons with no holes.

-----------------------------------------------------------------------------

3:

Q: What do you mean by *two* layers of polygons? Are you talking
   about 3D?

A: No, the exercise is only about 2D. An input "layer" is a set of polygons,
   which do not intersect each other. (Note that a polygon can be enclosed
   by a hole of another polygon of the same layer).

-----------------------------------------------------------------------------

4:

Q: I've noticed this problem: if there exists a vertical edge (like in
   LayerA.txt that you provided, in the hole) I should rotate all the scene
   by some angle a. but rotating and rotating back does not produce the same
   result. for example, rotating (0,-50) by some angle and then rotating it
   back results in (-8.88178e-016,-50).  How should I treat this problem?

A: There will be no degeneracies in the input - you can assume that
   events (vertices and edge intersections) are always more than epsilon
   apart in *each* of the directions.  That is, any two events will have
   different x coordinate, and different y coordinate.  (epsilon is 0.05).
   layerA.txt was given only as an *example* of the input *format*.

-----------------------------------------------------------------------------

5:

Q: What about complexity? Are there any restrictions?

A: Your program should be implemented using the segment-intersection
   algorithm taught in class.  Therefore, it should have the same time and
   space complexity as the taught algorithm.  That is, a total time
   complexity of O((n+k)log(n)).  (See the space complexity in the next
   question)
   Note: Operations specific to this exercise should NOT increase the total
   complexity - neither time nor space.

-----------------------------------------------------------------------------

6:

Q: Space complexity.  The sweep-line segment intersection algorithm
   presented in class had two variations:
   (1) that works in O(n + k) space;
   (2) that works in O(n) space.
   can we implement (2), or (1) is required ?

A: You can implement any one of the above that you choose.

-----------------------------------------------------------------------------

7:

Q: For determining, in the output, whether a polygon is a material polygon
   or a hole, must I use the given hint, or can I use other methods?

A: You can use any method you choose, as long as your algorithm meets the
   complexity restrictions.

-----------------------------------------------------------------------------

8:

Q: If a polygon is enclosed by a hole of another polygon, how does it appear
   in the input/output files?

A: These two polygons will appear as two different polygons in the files.
   (Except by checking their coordinates, there is no other clue one is
   enclosed by the other one).  However, holes appear "attached" to the
   polygons they belong to in the input/output files.
   (See given example "layerA.txt").

-----------------------------------------------------------------------------

9:

Q: Regarding the given hint - what should be the orientation of the holes in
   a polygon?

A: In the opposite direction of the orientation of the polygon.  (Find out
   yourself why this is true).

-----------------------------------------------------------------------------

More questions:  open http://www.cs.technion.ac.il/~osnattal/cg/moreFAQ.txt