Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re: Points, Lines. Polygons OO my

by mirod (Canon)
on Aug 31, 2001 at 13:50 UTC ( #109337=note: print w/replies, xml ) Need Help??


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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://109337]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (5)
As of 2023-02-06 09:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer not to run the latest version of Perl because:







    Results (33 votes). Check out past polls.

    Notices?