http://qs1969.pair.com?node_id=109337


in reply to Points, Lines. Polygons OO my

I remember that problem from school, a long time ago, and you have to be careful with a naive implementation of the algorithm. Angle points should _sometimes_ count as 2 points.

Just to clarify, here is the problem with angles and edges:

Warning: crappy ASCII art follows.

          _     ___
         | \   /   |
         |  \ /    |
 (1)_ _ _|_ _v_ _ _|_ _  3 intersections
         |         |
          \        |
 (2)_ _ _ _\_ _ _ _|_ _  2 intersections
           /       |
          /        |
 (3)_ _ _|_ _ _ _ _|_ _  3 intersections
         |    /\   |
         |   /  \  |
 (4)_ _ _|__/_ _ \_|_ _  ? intersections

The solution for angle points is to count them in only if the line they belong to goes down (or up, it doesn't matter, just choose one direction), thus (1) would have 2 intersections (the angle does not count) and (3) would have 4 (the angle counts twice, once for each line).

The solution for an edge is to count it as 2 intersections, one for each end, thus (4) would have 4 intersections.