eric@orfeo.radig.de (Eric Tuerlings) (03/28/91)
I can remember there was a discussion last year about: "Clicking on irregualar shapes". Because I want to use irregular shapes to click on, I am interested in a solution to this problem, since I found nothing else than to click on rectangle shapes only. Does somebody know a solution? -- Eric Tuerlings, E-Mail: eric@radig.de Stresemannallee 63, Tel: +49 69 6316870 6000 Frankfurt am Main 70, Germany. Holland is _just_ a part of the Netherlands, like Bavaria is in Germany
jpotter@ucs.adelaide.edu.au (Jonathan Potter) (03/28/91)
For a BOOLGADGET, specify SpecialInfo as pointing to a BoolInfo structure, and fill in the Mask variable in the BoolInfo structure. This allows you to specify a mask that details the shape for selecting/unselecting of the gadget. Jon -- | Jonathan Potter | | Life is like a piece of | | P.O. Box 289 | jpotter@itd.adelaide.edu.au | spinach... | | Goodwood, SA | FidoNet : 3:680/829 | | | Australia 5034 | | Sort of green and wrinkly |
peterk@cbmger.UUCP (Peter Kittel GERMANY) (03/28/91)
In article <1991Mar27.212214.6204@orfeo.radig.de> eric@orfeo.radig.de (Eric Tuerlings) writes: > >I can remember there was a discussion last year about: "Clicking on >irregualar shapes". Because I want to use irregular shapes to click on, >I am interested in a solution to this problem, since I found nothing else >than to click on rectangle shapes only. How about this brute force attempt: When the user clicks, you do a flood fill from that point with a certain color different from the previous one. Previously you have stored for every shape on your screen a (x,y) coordinate pair. Then you do a loop and look in every of these shapes at that very point, if it changed its color (the flood fill should have reached also this). Thus you get two effects: The user gets an immediate feedback where he clicked, and you can find which shape it was. (I imagine you want to do something like clicking on a world map and identifying the country.) Hello to Frankfurt! -- Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions... Commodore Frankfurt, Germany \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
peter@cbmvax.commodore.com (Peter Cherna) (03/28/91)
In article <2710@sirius.ucs.adelaide.edu.au> jpotter@ucs.adelaide.edu.au (Jonathan Potter) writes: >For a BOOLGADGET, specify SpecialInfo as pointing to a BoolInfo >structure, and fill in the Mask variable in the BoolInfo structure. This allows >you to specify a mask that details the shape for selecting/unselecting of the >gadget. That works, provided that the rectangular extents of the gadget overlap. In other words, using masked boolean gadgets, you can do this: _______ _______ | \ \ | | \ \ | | \ \ | | / / | | / / | |_______/ /_______| But not this: _______ _______ | \\ | | \\ | | \\ | | // | | // | |_______//_______| >| Jonathan Potter | | Life is like a piece of | Peter -- Peter Cherna, Operating Systems Development Group, Commodore-Amiga, Inc. {uunet|rutgers}!cbmvax!peter peter@cbmvax.commodore.com My opinions do not necessarily represent the opinions of my employer. "If all you have is a hammer, everything looks like a nail."
peter@cbmvax.commodore.com (Peter Cherna) (03/29/91)
In article <20181@cbmvax.commodore.com> peter@cbmvax.commodore.com (Peter Cherna) writes: >That works, provided that the rectangular extents of the gadget overlap. There I go, mixing up my do's and don'ts. Make that: That works, provided the rectangular extents of the gadget DO NOT overlap. (The diagrams were fine, BTW) Thanks to eagle-eye Dale of our Siberia office... Peter -- Peter Cherna, Operating Systems Development Group, Commodore-Amiga, Inc. {uunet|rutgers}!cbmvax!peter peter@cbmvax.commodore.com My opinions do not necessarily represent the opinions of my employer. "If all you have is a hammer, everything looks like a nail."
schwager@m.cs.uiuc.edu (Michael Schwager) (03/29/91)
eric@orfeo.radig.de (Eric Tuerlings) writes: >I can remember there was a discussion last year about: "Clicking on >irregualar shapes". Because I want to use irregular shapes to click on, >I am interested in a solution to this problem, since I found nothing else >than to click on rectangle shapes only. >Does somebody know a solution? >-- >Eric Tuerlings, E-Mail: eric@radig.de Hi, I was the one who asked the question. I'll try to describe what I did: I have a map of the world, that looks remarkably like a Risk board :-). I made it using DPaint. I saved each territory as a seperate brush. Then I used iff2c on each of those files, and got a lovely 1-bitplane description of the shape (if your shapes are >1 bitplanes deep, I suggest converting them to only a single color before saving them, so iff2c creates a single bitplane representation of the shape... a "cookie"). It was kind of a tedious process: first I cleaned up all around the image, then I used the grab brush tool (grabbing a rectangular area and noting the upper left coordinates of the object), then I saved this brush, and finally used iff2c on it. iff2c will give you the width and height of your object (in an Image structure). So now I have this file that I saved all these image structures in.... This is known as the "cookie-cutter" technique. Thanks to someone from Commodore for describing it to me. It's yecksellent having Commodore Tech people on the Net! On the screen, let's say I click at x=400, y=100. My algorithm goes thusly: 1. Which rectangles (captured above) contain that point? 2. Of those rectangles, which one has a 1 bit in the position in question (there can be one and only one)? 3. Bingo! I have found an object! I decided to use this technique because once I've clicked on an object I wanted it to flash, by xor'ing the cookie's bitmap with the proper location and planes in the screen's bitmap. So I knew I was gonna have to make the cookies anyway. -Mike Schwager
schwager@m.cs.uiuc.edu (Michael Schwager) (03/29/91)
Oh, yeah... iff2c is on Fish Disk 316. -Mike
mmaston@leland.Stanford.EDU (Michael Maston) (03/29/91)
This may be somewhat unrelated to the original intent of the author, but it seems to be along the same basic lines... I am currently developing a MacDraw II lookalike object-oriented drawing package. One of my chief concerns is being able to quickly determine which object on the screen has been chosen by a mouse-click. Now this is pretty straightforward for boxes, lines, circles and even ellipses, but how does one do this with say an object drawn with a freehand tool? I have experimented a lot with MacDraw and its algorithms are pretty good, even when objects are stacked on top of each other. Anyway, are there good references on this type of algorithm that the great gurus of the net can refer me to? By the way, all development is currently taking place on a pretty much stock 2000 with Lattice 5.1... Thanks!!! Michael Maston GTE Government Systems Mt. View, CA 94039
jbickers@templar.actrix.gen.nz (John Bickers) (03/30/91)
Quoted from <1991Mar29.022042.14110@leland.Stanford.EDU> by mmaston@leland.Stanford.EDU (Michael Maston): > object on the screen has been chosen by a mouse-click. Now this is pretty > straightforward for boxes, lines, circles and even ellipses, but how does > one do this with say an object drawn with a freehand tool? I have experimented One approach is to determine if the point is within a polygon or not. First check the point against the extent of the polygon, and if it's in, then count how many edges of the polygon a line from the point to one edge of the screen intersects. Odd and it's inside, even and it's outside. > Anyway, are there good references on this type of algorithm that the great There's comp.graphics. I think the above approach is in the FAQ posting there. The FAQ also contains a list of references for various things. > Michael Maston -- *** John Bickers, TAP, NZAmigaUG. jbickers@templar.actrix.gen.nz *** *** "Patterns multiplying, re-direct our view" - Devo. ***
bairds@eecs.cs.pdx.edu (Shawn L. Baird) (03/31/91)
jbickers@templar.actrix.gen.nz (John Bickers) writes: >Quoted from <1991Mar29.022042.14110@leland.Stanford.EDU> by mmaston@leland.Stanford.EDU (Michael Maston): >> object on the screen has been chosen by a mouse-click. Now this is pretty >> straightforward for boxes, lines, circles and even ellipses, but how does >> one do this with say an object drawn with a freehand tool? I have >> experimented > One approach is to determine if the point is within a polygon or > not. First check the point against the extent of the polygon, and > if it's in, then count how many edges of the polygon a line from > the point to one edge of the screen intersects. > Odd and it's inside, even and it's outside. If you're really lazy and don't mind wasting a little extra memory, or if your objects have non-polygon shapes, try setting up a one plane mask of the area. Then just check the point to see if it is a 1 or a 0 when clicking occurs inside of the box. (This could even be an extension to normal Intuition buttons. Just set up the mask and a pointer to it as part of the structure and then check it whenever you get the appropriate event) When I said lazy up above, essentially I mean quick. The memory loss isn't usually tremendous either. Note: This is just an idea. Never tried it, but I have thought about it before and this seemed like a fairly straight forward and yet powerful way to accomplish it. This way you can have holes in buttons or pieces of buttons (that is, maybe the button is broken into two distinct pieces, neither of which connects with the other). --- Shawn L. Baird, bairds@eecs.ee.pdx.edu, Wraith on DikuMUD The above message is not licensed by AT&T, or at least, not yet.
nj@truffula.Berkeley.EDU (Narciso Jaramillo) (03/31/91)
mmaston@leland.Stanford.EDU (Michael Maston) asked: [in the context of object-oriented drawing programs] >> [how does one select] say an object drawn with a freehand tool? In article <2151@pdxgate.UUCP> bairds@eecs.cs.pdx.edu (Shawn L. Baird) writes: > If you're really lazy and don't mind wasting a little extra memory, or if > your objects have non-polygon shapes, try setting up a one plane mask of > the area. Then just check the point to see if it is a 1 or a 0 when clicking > occurs inside of the box. This is a good idea for irregularly-shaped Intuition buttons and *filled* objects, but it doesn't work for unfilled objects or non-closed objects, where you only want to select it if you hit the mouse button near the boundary of the object. The suggestion I accidentally sent through email to Michael depended on how he was storing the freehand objects. 1) If you're storing the freehand object as a plain old bitmap, the easiest thing to do is probably to just go ahead and search all the pixels in the bitmap that are within your pick sensitivity radius of the mouse button press. Since pick sensitivity is unlikely to be huge, this shouldn't take too long, unless there are a bunch of overlapping bitmaps. (Of course, you should do a bounding box test first, to make sure the mouse button actually hit near the bitmap.) 2) If you're storing the object as a sequence of lines, then you can go through each of the lines and do a standard line-pick check. 3) If the object is a sequence of curves, it's harder. The trick I plan to use is to check bounding boxes of curve segments first (I'm using splines with the convex-hull property). Then, for each of the curve segments whose bounding boxes the mouse button hit, I go through and ``redraw'' the curve segment (actually, just recomputing points on the curve without drawing), checking if any points on the curve are near the mouse press. Since I'm using a reasonably fast curve-drawing algorithm (forward differences), this shouldn't be too slow (unless there are a bunch of overlapping curve segments). Does anyone have any better suggestions for the last case? It's sort of a general problem with selecting parametrized curves. nj
edgar@csri.toronto.edu (Edgar LeBel) (04/02/91)
Here's a REALLY cheap way of detecting clicks on irregular shapes: draw the shapes in different colours, so you can sample the pixel clicked on to figure out which shape was picked. Hobie Orris
nj@magnolia.Berkeley.EDU (Narciso Jaramillo) (04/03/91)
In article <1991Apr2.083226.28814@jarvis.csri.toronto.edu> edgar@csri.toronto.edu (Edgar LeBel) writes:
Here's a REALLY cheap way of detecting clicks on irregular shapes: draw the
shapes in different colours, so you can sample the pixel clicked on to
figure out which shape was picked.
Except that (1) this forces you to click exactly on the shape boundary
for an unfilled shape and (2) it forces every shape to be a different
color. Useful for some applications, not for others.
njumueller@iiic.ethz.ch (Urban Dominik Mueller) (04/04/91)
There have already been many answers to this question, but none of them complete. The basic solution has been mentioned: Draw an imaginary line from the point the user clicked on to a point in nowhereland, far away in any case. A hori- zontal line would be best. Now count the number of times this line would intersect with edges of the polygon. If that number is even, you're outside, otherwise you're inside. But that's not all of it. Assume your imaginary line passes exactly through a vertex, which can easily happen. I that case, count it only as an inter- section if that vertex is a local maximum or minimum. The only problem left is the line intersection. I have no formula handy, but it should not be too hard to intersect with a horizontal line. Urban Mueller, umueller@iiic.ethz.ch
ptavoly@cs.ruu.nl (Peter Tavoly) (04/05/91)
umueller@iiic.ethz.ch (Urban Dominik Mueller) writes: >There have already been many answers to this question, but none of them >complete. > >The basic solution has been mentioned: Draw an imaginary line from the point >the user clicked on to a point in nowhereland, far away in any case. A hori- >zontal line would be best. Now count the number of times this line would >intersect with edges of the polygon. If that number is even, you're outside, >otherwise you're inside. >But that's not all of it. Assume your imaginary line passes exactly through >a vertex, which can easily happen. I that case, count it only as an inter- >section if that vertex is a local maximum or minimum. >The only problem left is the line intersection. I have no formula handy, but >it should not be too hard to intersect with a horizontal line. > I am currently writing a game that needs this (and probably will never be finished :^). Now what about this: /\ / \ /\ / O \ / \ X / \/ ___\ /_______ / \/ (this is a totally random shape, created by a misty mind :) where you draw the horizontal line from the 'O' to the 'X', now, it intersects an odd number of boundaries, yet it is OUTside the shape. Or am I mistaking something here? In other words this even/odd thing does not work since you can always make a shape that has a 'too irregular' shape. Or imagine a shape like this: /\ / \ / / O \ / X / \/ /_______/ Here, an even number of boundaries is crossed. (The second intersection is a single line) -Thomas Tavoly. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ "Help, I've been attacked by a Prime terminal at 1200 baud!!!" -Thomas T. Did you know that IBM have a secret factory with an infinite number of monkeys? That's how they invented MS-DOS... -ptavoly@praxis.cs.ruu.nl ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kris@tpki.toppoint.de (Kristian Koehntopp) (04/05/91)
See "Algorithms, Second Edition", Robert Sedgewick, Addison Wesley, ISBN 0-201-06673-4. Section "Geometric Algorithms", Ch. 24: "Elementary Geometric Methods" contains "Points, Lines and Polygons" "Line Segment Intersection", "Simple Closed Path", "Inclusion in a polygon", "Perspective" Ch. 27: "Geometric Intersection" contains "Horizontal and Vertical Lines", "Implementation", "General Line Intersection". In Ch.24 Sedgewick covers the horizontal line test, in Ch.27 he uses a database of line-coordinates. The book is quite terse, you may find more elaborate descriptions in a book on computer graphics. Kristian Kristian Koehntopp, Harmsstrasse 98, 2300 Kiel, +49 431 676689 "Das Editier, das Editier, das lebt jetzt leider nicht mehr hier." -- aus "Un-Zen oder die Kunst des schlechten Kalauers".
umueller@iiic.ethz.ch (Urban Dominik Mueller) (04/05/91)
ptavoly@cs.ruu.nl (Peter Tavoly) writes: >umueller@iiic.ethz.ch (Urban Dominik Mueller) writes: >> [an algorithm for determining whether a point's inside a polygon] >I am currently writing a game that needs this (and probably will never be >finished :^). Now what about this: > /\ > / \ /\ > / O \ / \ X > / \/ ___\ > /_______ / > \/ >where you draw the horizontal line from the 'O' to the 'X', now, it intersects >an odd number of boundaries, yet it is OUTside the shape. Or am I mistaking >something here? Am *I* mistaking *you*? The way I see it, the 'O' is clearly inside, as the algorithm states. Or are you talking about the 'X'? 'X' must be a point that's sure to be outside, but 'O' is the point in question. The polygon can be as complex as you want. > /\ > / \ / > / O \ / X > / \/ > /_______/ >Here, an even number of boundaries is crossed. (The second intersection is a >single line) The polygon must be closed for this algorithm to work. To make it closed, you have to draw a second line over that single line already drawn, there- fore you get a double interection at that line, so the total number of inter- sections is odd again -> inside. BTW I just discovered that I explained the problem with the imaginary line going through a vertex exactly the wrong way round. Count the intersection only if it's *no* local maximum or minimun, otherwise don't (or do it twice). My apologies if that caused problems to anyone. __ | Urban Mueller | / / | Urban Mueller | | INTERNET:umueller@iiic.ethz.ch | __ / / | Schulhausstr. 83 | | FIDONET: 2:302/906 (AUGL) | \ \/ / | CH-6312 Steinhausen | | "Don't tell my employer" | \__/ | SWITZERLAND |
nj@magnolia.Berkeley.EDU (Narciso Jaramillo) (04/06/91)
In article <1991Apr05.104141.2118@cs.ruu.nl> ptavoly@cs.ruu.nl (Peter Tavoly) writes: > /\ > / \ /\ > / O \ / \ X > / \/ ___\ > /_______ / > \/ >where you draw the horizontal line from the 'O' to the 'X', now, it intersects >an odd number of boundaries, yet it is OUTside the shape. Er, from your diagram, it looks to me as if the O is INSIDE the shape. If you mean that the two `mountains' are separate shapes, then presumably the boundaries of each are represented separately. So you should only check the intersection against the boundaries of the polygon you're interested in. > imagine a shape like this: > > /\ b > / \ / > / O \c / X > / \/ > /_______/a >Here, an even number of boundaries is crossed. (The second intersection is a >single line) This is only a problem if you represent that odd line as only one line. Since it's a closed polygon, it makes a little more sense to represent it as two lines--one going from the point I've marked `a' to the point I've marked `b', and another going from `b' back down to `c'. I just realized that you may be assuming that this test works with raw bitmaps. In general, it only completely works if you have an internal representation of your polygons. If you're only working with a bitmap image, this won't work so well in degenerate cases. It's probably better to go ahead and represent your polygons internally--a simple array of line endpoints won't take up much room. nj
dillon@overload.Berkeley.CA.US (Matthew Dillon) (04/06/91)
In article <27832@neptune.inf.ethz.ch> umueller@iiic.ethz.ch (Urban Dominik Mueller) writes: >There have already been many answers to this question, but none of them >complete. > >The basic solution has been mentioned: Draw an imaginary line from the point >the user clicked on to a point in nowhereland, far away in any case. A hori- >zontal line would be best. Now count the number of times this line would >intersect with edges of the polygon. If that number is even, you're outside, >otherwise you're inside. >But that's not all of it. Assume your imaginary line passes exactly through I think the best solution is to simply have a grainy bitmap of the object and just compare the coordinate against the grainy bitmap (e.g. a 16x16 bitmap = 32 bytes) (for this case) > Urban Mueller, umueller@iiic.ethz.ch -Matt -- Matthew Dillon dillon@Overload.Berkeley.CA.US 891 Regal Rd. uunet.uu.net!overload!dillon Berkeley, Ca. 94708 USA
peterk@cbmger.UUCP (Peter Kittel GERMANY) (04/08/91)
(Sorry, deleted the originator's name.) > [an algorithm for determining whether a point's inside a polygon] > >I am currently writing a game that needs this (and probably will never be >finished :^). Now what about this: > /\ > / \ /\ > / O \ / \ X > / \/ ___\ > /_______ / > \/ I always have moot feelings with such analytical algorithms. Often you have to compare for equality of real numbers, which is normally a NO-NO. You would have to convert coordinates to integers only to do this algorithm on them. Look for another example at this shape, would it be processed correctly? /\ / \ /\ / O \_____/ \ /_______________\ The O is thought to be on the same y coordinate as the horiz. line. -- Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions... Commodore Frankfurt, Germany \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
espie@flamingo.Stanford.EDU (Marc Espie) (04/09/91)
In article <1079@cbmger.UUCP> peterk@cbmger.UUCP (Peter Kittel GERMANY) writes: >(Sorry, deleted the originator's name.) >> [an algorithm for determining whether a point's inside a polygon] >> >>I am currently writing a game that needs this (and probably will never be >>finished :^). Now what about this: >> /\ >> / \ /\ >> / O \ / \ X >> / \/ ___\ >> /_______ / >> \/ > >I always have moot feelings with such analytical algorithms. Often >you have to compare for equality of real numbers, which is normally >a NO-NO. You would have to convert coordinates to integers only to >do this algorithm on them. > >Look for another example at this shape, would it be >processed correctly? > /\ > / \ /\ > / O \_____/ \ > /_______________\ > >The O is thought to be on the same y coordinate as the horiz. line. > This is an old problem, well-known by people working on the subject. It is solvable generally. There are actually two cases to consider. 1) You're really working with integer coordinates. In that case, don't switch to float. Take an horizontal line passing through the end point, and see which lines it crosses. Don't forget every equality cases, and every subcase. That works, because these special cases are determined by integer comparisons only. 2) You're working with floating-point coordinates. You can either reduce everything to integer coordinates, in that case you will check the adjusted point against the adjusted shape, and use the previous algorithm. As Peter Kittel very rightly said, don't even think of mixing the two algorithms, you will be fixing subtle bugs three months later. Or... you can work with floating-point coordinates. Set up a margin of error, and choose a line passing through your point. Check for special cases using your margin: do you get within your margin of passing through a vertex ? Are you near a line which has nearly the same orientation as the line you've chosen ? If a problem arises, well, choose another line. It will eventually work (pretty soon, usually), or your margin is too big for the kind of shape you're drawing (ill-dimensionned problem). Both ideas are easy to implement if you're careful of what you're doing. For further references, check any textbook in computational geometry (Preparata, Edelsbrunner...). -- Marc Espie (espie@flamingo.stanford.edu)
umueller@iiic.ethz.ch (Urban Dominik Mueller) (04/09/91)
>I always have moot feelings with such analytical algorithms. Often >you have to compare for equality of real numbers, which is normally >a NO-NO. You would have to convert coordinates to integers only to >do this algorithm on them. It's not that bad, in order to find out whether a point is a local maximum or minimum, you need only check for less-equal. Additionally, you can often work with integer arithmetics when it comes to gfx. For example the guy who started this thread is programming a game, I doubt he works with reals. >Look for another example at this shape, would it be >processed correctly? > /\ > / \ /\ > / O \_____/ \ > /_______________\ > >The O is thought to be on the same y coordinate as the horiz. line Yes, it works. If you have defined a local minimum to be a point whose neighbours have higher *or same* y-coordinates, you've got two minima here, which aren't counted. This works even of that horizontal line consists of more than one edge. But it's really good to be suspicious, I know a lot of people (including my CS prof) who have trouble getting that problem right... Not counting all the bad solutions that were posted on this net. Ah yes, I have to join that guy who recommended the Sedgewick book, it's a must for any good programmer. >Best regards, Dr. Peter Kittel // E-Mail to \\ Only my personal opinions.. __ | Urban Mueller | / / | Urban Mueller | | INTERNET:umueller@iiic.ethz.ch | __ / / | Schulhausstr. 83 | | FIDONET: 2:302/906 (AUGL) | \ \/ / | CH-6312 Steinhausen | | "Don't tell my employer" | \__/ | SWITZERLAND |
utoddl@uncecs.edu (Todd M. Lewis) (04/09/91)
In article <NJ.91Apr2105446@magnolia.Berkeley.EDU> nj@magnolia.Berkeley.EDU (Narciso Jaramillo) writes: >In article <1991Apr2.083226.28814@jarvis.csri.toronto.edu> edgar@csri.toronto.edu (Edgar LeBel) writes: > > Here's a REALLY cheap way of detecting clicks on irregular shapes: draw the > shapes in different colours, so you can sample the pixel clicked on to > figure out which shape was picked. > >Except that (1) this forces you to click exactly on the shape boundary >for an unfilled shape and (2) it forces every shape to be a different >color. Useful for some applications, not for others. > Here's a similar technique that requires (1) that you click within the shape boundary (on it isn't good enough--helps reduce errors) and (2) all shapes be filled with one of a given set of colors. (Below I've assumed they are all the same color.) Try this. You have irregular shapes with borders, right? The shapes are all plane, and filled with the same pen color, right? Make sure that the only place on screen where that pen is used is in those shapes. Now, when the user clicks on the screen, check the pixel s/he clicked on and make sure it is that pen, and therefore is actually in one of these shapes. If not, ignore the click (or give a message). So far so good. We know a shape was selected, but we don't know which one. Next, flood-fill with a different pen starting at that pixel. If this different pen has a different color then the user can see which shape was selected, but it could be a pen of the same color--just depends on what you want. Now go through your list of irregular shapes and check a single pixel within each one until you find the shape whose color was changed. You'll probably want to flood-fill it again to set the color back to "normal", or not, depending on your needs. Todd M. Lewis, utoddl@ecsvax.uncecs.edu, utoddl@ecsvax.bitnet "It is curious that this many people [...] would assume to know the intent of the author based on the observed behavior of the program." --- Eugene H. Spafford, "Crisis and Aftermath", CACM, (June 1989)
ptavoly@cs.ruu.nl (Peter Tavoly) (04/09/91)
This post contains reactions to three other posts in the same thread. 1. umueller@iiic.ethz.ch (Urban Dominik Mueller) writes: >> /\ >> / \ /\ >> / O \ / \ X >> / \/ ___\ >> /_______ / >> \/ >>where you draw the horizontal line from the 'O' to the 'X', now, it intersects >>an odd number of boundaries, yet it is OUTside the shape. Or am I mistaking >>something here? > >Am *I* mistaking *you*? The way I see it, the 'O' is clearly inside, as the >algorithm states. Or are you talking about the 'X'? 'X' must be a point that's >sure to be outside, but 'O' is the point in question. The polygon can be as >complex as you want. You wrote, that you explained it the other way around; I guess that's why I did it that way too :) >> /\ >> / \ / >> / O \ / X >> / \/ >> /_______/ >>Here, an even number of boundaries is crossed. (The second intersection is a >>single line) > >The polygon must be closed for this algorithm to work. To make it closed, >you have to draw a second line over that single line already drawn, there- >fore you get a double interection at that line, so the total number of inter- >sections is odd again -> inside. Yes, that is the problem, what if it is not closed? You are bound to come across one of those at some point. BTW, I was thinking of a bitmap indeed, not a polygon, or maybe an imaginary polygon only, which is not visible but is the internal representation of the boundaries and then a bitmap inside for the graphical stuff. > >BTW I just discovered that I explained the problem with the imaginary line >going through a vertex exactly the wrong way round. Count the intersection >only if it's *no* local maximum or minimun, otherwise don't (or do it twice). >My apologies if that caused problems to anyone. No problem. > | Urban Mueller | / / | Urban Mueller | > | INTERNET:umueller@iiic.ethz.ch | __ / / | Schulhausstr. 83 | > | FIDONET: 2:302/906 (AUGL) | \ \/ / | CH-6312 Steinhausen | > | "Don't tell my employer" | \__/ | SWITZERLAND | 2. nj@magnolia.Berkeley.EDU (Narciso Jaramillo) writes: >In article <1991Apr05.104141.2118@cs.ruu.nl> ptavoly@cs.ruu.nl (Peter Tavoly) writes: [shapes and stuff deleted] > >I just realized that you may be assuming that this test works with raw >bitmaps. In general, it only completely works if you have an internal >representation of your polygons. If you're only working with a bitmap >image, this won't work so well in degenerate cases. It's probably >better to go ahead and represent your polygons internally--a simple >array of line endpoints won't take up much room. Exactly that's what I was thinking. Thank you for the suggestions. >nj 3. dillon@overload.Berkeley.CA.US (Matthew Dillon) writes: > I think the best solution is to simply have a grainy bitmap of the > object and just compare the coordinate against the grainy bitmap (e.g. > a 16x16 bitmap = 32 bytes) > > (for this case) Yes, I think I might be lazy and do this :^) > -Matt -Thomas T. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ "Help, I've been attacked by a Prime terminal at 1200 baud!!!" -Thomas T. Did you know that IBM have a secret factory with an infinite number of monkeys? That's how they invented MS-DOS... -ptavoly@praxis.cs.ruu.nl ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --