From: h8915726@hkuxb.hku.hk (Medusa)
Subject: Summary: (WAS: Point inside an enclosed region)
Reply-To: h8915726@hkuxa.hku.hk
Organization: University of Hong Kong
X-Newsreader: Tin 1.1 PL4
Date: Tue, 29 Dec 1992 11:52:28 GMT

Hi, 

Here are the replies, up to now, I got. Thanks very much for the suggestion.
If there are anymore, I will post the summary again.


1) This is from Mike Brindley.

> Well, it seems to me that you should be able to precalculate a bounding
> box (a width at least) for your pattern.  You will probably want to sort

	Yes. His guess is right. I know the bounding box, and that's
	what I have done today. it reduces the time by 1/3 to 1/2 if
	the pattern is small enough (i.e., there are MORE complete-within-
	pattern than part-within-pattern). But my program still
	runs slowly as much 30-40 sec as to fill around 300x300 irregular
	closed-type with a semi-circle pattern of around 15x15 pixels.

> or otherwise order your pattern.  Then, when you find the span extrema,
> you can do trivial accept/rejects on the points in the pattern. With the
> points in the pattern sorted/ordered, you only need check a part of them
> before you know that you need not check any more.  This is the same idea
> as keeping an active edge list for the polygon.  See your favourite 
> graphics text (Foley, VanDam, Hughes, et al; Newman & Sproull; Harrington;
> etc.)  for details on the scanline/raster filling technique.

> Of course, for bitmap (raster) displays, the pattern is normally kept in
> a bitmap.  Then you can easily and cheaply index into it and use the pattern
> pixel as a mask (plot or no plot; complement or leave alone; which color).

	Yes. This idea also comes from the following nice people too.

2) This is from Sumant.

> 1. Faster Ways to find point inside Polygon:
>	The Infinite Ray test is still the best one for
>	point inside a general polygon test.
>	However, its not as expensive as U think.
>	You can convert the method to simple camparison
>	method.
>	Look at the book "Introductions to Ray Tracing"
>	by Glassner on ray-object intersection !!
>	It gives you the fast algorithm.
>	If U dont have access to it, let me know.
>	I'll send U the alo by mail.
> 2. No one does pattern filling by checking every point for
>	inside-outside. It is done by a simple modification to
> 	polygon scan-conversion filling method.
>	If your region to be filled with pattern is not a
>	polygon, then modify the seed-fill algorithm.
> 	Look at the Book by Foley, VanDam , Feihner and Hughes.

	Yeah. I'm thinking of modifying the seed-fill alg. But my
	another real practical restrain is, I'm controlling a embroidery
	machine, so one stitch must follow another stitch either next-to-next
	or follow the boundary of the area. So seed-fill do requires quite
	some modifications, and I'm working on it. But hope it does not
	incurr to much time on overall performance.


3) This is from Steve Cunningham

> Your question on "point inside polygon" is prompted, you say, by a desire to
> fill polygons with patterns.  I don't understand why this is a problem; just
> take a standard scanline polygon fill and apply YourFavoritePatternProcess (tm)
> to each point on the scanlines the fill generates.  This is quick, painless,
> and a totally standard technique; see your favorite source for polygon fills.

	I wish I could do as if working in a scanline polyfill, but
	this is not, (I think, any enlightenment?), applicable for me.


Thanks again for the replies. Anyone have more info are REALLY appreicated
to mail me.

--
Medusa
University of Hong Kong
H8915726@hkuxa.hku.hk