Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
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 browsing the Monastery: (4)
As of 2022-01-26 09:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:












    Results (69 votes). Check out past polls.

    Notices?