Do I have to invent the wheel myself?

Bing Zhang

unread,

Aug 26, 1996, 3:00:00 AM8/26/96

to

I am not sure whether there are any tools out there for me to pick up to finish
my project. If you have a clue, please drop me a line. Here are what I try to
accomplish:

There are a dozen of radar station across the Nothern American continent. Each
station has four properties: longitude, lattitude, scan radius and availability.
Given the first three, a circle will be drawn accordingly. Depending on the
value of the availability, the circle will be filled with predined color. If
two or three circles overlap, the availability at the overlapping region will
be a composite one and the color at this region will be changed accordingly.
The final image will be something like a temperature map in an evening TV
weather report in which different temperature is represented by different color. Are
there any products out there that will prompt the user directly (or indirectly if it
allow me to code an user interface) with these properties, draw and fill
the color, update the map automatically automatically if one station is deleted
or enlarged?

If I have to invent my own wheel, I will create an image of US map using a
GIF file and figure out how the pixels in the canvas correspond to the actual
mileages or longitudes and lattidudes. Then draw the circle. The hard thing is to fill
the circle with the color. If the circles do not overlap, thing will be much
easy. But for the overlapping region, it is not trivial.

One proposal is to detect the overlapping region and fill it accordingly. I
have not seen a good algorithm to calculate the intersecting points of arcs
and define the region. The overlapping region consists of arcs, not lines, so
the region is not a polygon and the "fill" option of the canvas may not be
used.

The second proposal which is the one I am going to use if I have to invent the
wheel is to draw the circle without fill color or with the fill color of the
underlined US map. Then find the square enclosing the circle, use a small
window, say 4x4 pxels, to traverse the square. If the circles are detected
underneath the center of this small windows, the small window will be filled
with color according to the composite availability.

wi...@news.sns-felb.debis.de

unread,

Aug 27, 1996, 3:00:00 AM8/27/96

to

Bing Zhang (bzh...@sohar.com) wrote:
: I am not sure whether there are any tools out there for me to pick up to finish

: my project. If you have a clue, please drop me a line. Here are what I try to
: accomplish:
:
: There are a dozen of radar station across the Nothern American continent. Each
: station has four properties: longitude, lattitude, scan radius and availability.
: Given the first three, a circle will be drawn accordingly. Depending on the
: value of the availability, the circle will be filled with predined color. If
: two or three circles overlap, the availability at the overlapping region will
: be a composite one and the color at this region will be changed accordingly.
: The final image will be something like a temperature map in an evening TV
: weather report in which different temperature is represented by different color. Are
: there any products out there that will prompt the user directly (or indirectly if it
: allow me to code an user interface) with these properties, draw and fill
: the color, update the map automatically automatically if one station is deleted
: or enlarged?

I don't know if there's anything out there. So let's build it
up from scratch.

:
: If I have to invent my own wheel, I will create an image of US map using a

: GIF file and figure out how the pixels in the canvas correspond to the actual
: mileages or longitudes and lattidudes. Then draw the circle. The hard thing is to fill
: the circle with the color. If the circles do not overlap, thing will be much
: easy. But for the overlapping region, it is not trivial.
:
: One proposal is to detect the overlapping region and fill it accordingly. I
: have not seen a good algorithm to calculate the intersecting points of arcs
: and define the region. The overlapping region consists of arcs, not lines, so
: the region is not a polygon and the "fill" option of the canvas may not be
: used.

It's possible to calculate if and what area of two circles
overlap. This is more a mathematical problem than a Tcl one.
Anyway.

Given two midpoints of two circles you can calculate the
distance between them by sqrt((x1-x2)**2 + (y1-y2)**2) (**
means power). The two circles overlap if the distance is
less than the sum of the two radii.

Another special case is if one circle is completely covered
by the other one. Easy to detect because in that case the
distance plus one radius is less than or equal to the other
radius.

The last case is where the two circles intersect but none is
covered completely by the other - that's a bit tricky. So
let's show a little graph:

/ \ -------------
/ -O \
/ . / |\. \
/ c1. / | \. \
| . / b| | .c2 \
| . | | | . |
| x1-------------|---+-|----x2 |
| a1 | | a2 |
| \ | /
\ \ / /

O.K. - it's not that good - but should do it. 'x1' and 'x2'
are the midpoints of the two circles. 'O' is the point where
the circle lines cross. 'a1' and 'a2' are in summary the
distance between the mitpoints that we call 'd' from now on.
'b' is a line 90 degrees from 'd' going through 'O'. 'c1' and
'c2' are the radii of the two circles that go through 'O'.

The values we already know are 'd', 'c1' and 'c2'. What we
now want to calculate is the angle between 'a1' (or 'd') and
'c1'. From Pytagoras we know that

2 2 2 2 2
b = c1 - a1 = c2 - a2

While 'a2' and 'a1' are 'd' we can say that

2 2 2 2
c1 - a1 = c2 - (d - a1)

what ends up in

2 2 2
d + c1 - c2
a1 = --------------
2d

From that we simply get the angle between 'a1' and 'c1' by
the inverse cosine of 'a1' divided by 'c1'. The last we must
know is the direction of 'd' from 'x1' to 'x2'. Thats easy
and now we know the start and extent for the arc item to draw
in the canvas. Using the arc style 'chord' draws a segment
instead of a sector. If we do that for both circles exactly
the overlapping area is drawn.

:
: The second proposal which is the one I am going to use if I have to invent the

: wheel is to draw the circle without fill color or with the fill color of the
: underlined US map. Then find the square enclosing the circle, use a small
: window, say 4x4 pxels, to traverse the square. If the circles are detected
: underneath the center of this small windows, the small window will be filled
: with color according to the composite availability.

What I would suggest here is to use a stipple bitmap for the
filling of the arcs. The bitmap should be 'light', so enough
of the background shows through. The sample program I include
at the end might give you an impression. Drawing of the arcs
and mapping to the bitmap is done by the X server. So this is
fast.

The sample does not detect if an area is covered more than
twice. And I think that this would be a bit too much
calculations for doing it in Tcl/Tk. Therefore, the handling
of switching stations on/off must be much more intelligent
than it is now (completely remove and redraw anything). A
bunch of tags would be required. If you really need it, I'll
help you with the algorithms. But we should switch to eMail
for that to avoid flames saying 'wrong newsgroup'.

:
: --

Until later, Jan

--
#define OPINIONS "they are all mine - not those of debis or daimler-benz"

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me. #
#================================== wi...@sapserv.debis.de (Jan Wieck) #

begin 644 sample.tar.Z
<uuencoded_portion_removed>
%^J[PVA``
`
end

John Ellson

unread,

Aug 27, 1996, 3:00:00 AM8/27/96

to

In article <4vuq0d$o...@news.sns-felb.debis.de>,

>....[mathematics deleted]

If you don't actually need the program to detect the overlaps, and you
just want the overlaps to be visually obvious, then a simpler solution
might be to use stipple patterns so that a third pattern
occurs when the stipples are overlaid.

With careful design of the stipple patterns you might even get the
appearance of a third color, but I haven't tried this.

In the attatched example the overlap of the gray25 with the
gray50 bitmaps produces a distinct striped pattern.

John Ellson
ell...@lucent.com

#!/bin/sh
# This is a shell archive (produced by GNU sharutils 4.2).
# To extract the files from this archive, save it to some FILE, remove
# everything before the `!/bin/sh' line above, then type `sh FILE'.
#
# Made on 1996-08-27 09:55 EDT by <ellson@ontap>.
# Source directory was `/home/ellson/tempsample'.
#
# Existing files will *not* be overwritten unless `-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------
# 275 -rwxr-xr-x gray25.bmp
# 275 -rwxr-xr-x gray50.bmp
# 160 -rwxrwxr-x sample2.tcl
#
save_IFS="${IFS}"
IFS="${IFS}:"
gettext_dir=FAILED
locale_dir=FAILED
first_param="$1"
for dir in $PATH
do
if test "$gettext_dir" = FAILED && test -f $dir/gettext \
&& ($dir/gettext --version >/dev/null 2>&1)
then
set `$dir/gettext --version 2>&1`
if test "$3" = GNU
then
gettext_dir=$dir
fi
fi
if test "$locale_dir" = FAILED && test -f $dir/shar \
&& ($dir/shar --print-text-domain-dir >/dev/null 2>&1)
then
locale_dir=`$dir/shar --print-text-domain-dir`
fi
done
IFS="$save_IFS"
if test "$locale_dir" = FAILED || test "$gettext_dir" = FAILED
then
echo=echo
else
TEXTDOMAINDIR=$locale_dir
export TEXTDOMAINDIR
TEXTDOMAIN=sharutils
export TEXTDOMAIN
echo="$gettext_dir/gettext -s"
fi
touch -am 1231235999 $$.touch >/dev/null 2>&1
if test ! -f 1231235999 && test -f $$.touch; then
shar_touch=touch
else
shar_touch=:
echo
$echo 'WARNING: not restoring timestamps. Consider getting and'
$echo "installing GNU \`touch', distributed in GNU File Utilities..."
echo
fi
rm -f 1231235999 $$.touch
#
if mkdir _sh04283; then
$echo 'x -' 'creating lock directory'
else
$echo 'failed to create lock directory'
exit 1
fi
# ============= gray25.bmp ==============
if test -f 'gray25.bmp' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'gray25.bmp' '(file already exists)'
else
$echo 'x -' extracting 'gray25.bmp' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'gray25.bmp' &&
#define grey_width 16
#define grey_height 16
static char grey_bits[] = {
X 0x11, 0x11, 0x44, 0x44, 0x11, 0x11, 0x44, 0x44, 0x11, 0x11, 0x44, 0x44,
X 0x11, 0x11, 0x44, 0x44, 0x11, 0x11, 0x44, 0x44, 0x11, 0x11, 0x44, 0x44,
X 0x11, 0x11, 0x44, 0x44, 0x11, 0x11, 0x44, 0x44};
SHAR_EOF
$shar_touch -am 0827095496 'gray25.bmp' &&
chmod 0755 'gray25.bmp' ||
$echo 'restore of' 'gray25.bmp' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'gray25.bmp:' 'MD5 check failed'
2d5d17b53d2211ccc9b0b2dd9546a7f8 gray25.bmp
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'gray25.bmp'`"
test 275 -eq "$shar_count" ||
$echo 'gray25.bmp:' 'original size' '275,' 'current size' "$shar_count!"
fi
fi
# ============= gray50.bmp ==============
if test -f 'gray50.bmp' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'gray50.bmp' '(file already exists)'
else
$echo 'x -' extracting 'gray50.bmp' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'gray50.bmp' &&
#define grey_width 16
#define grey_height 16
static char grey_bits[] = {
X 0x55, 0x55, 0xaa, 0xaa, 0x55, 0x55, 0xaa, 0xaa, 0x55, 0x55, 0xaa, 0xaa,
X 0x55, 0x55, 0xaa, 0xaa, 0x55, 0x55, 0xaa, 0xaa, 0x55, 0x55, 0xaa, 0xaa,
X 0x55, 0x55, 0xaa, 0xaa, 0x55, 0x55, 0xaa, 0xaa};
SHAR_EOF
$shar_touch -am 0827095496 'gray50.bmp' &&
chmod 0755 'gray50.bmp' ||
$echo 'restore of' 'gray50.bmp' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'gray50.bmp:' 'MD5 check failed'
2cb1536ab1bca06f540aa52bfff4402f gray50.bmp
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'gray50.bmp'`"
test 275 -eq "$shar_count" ||
$echo 'gray50.bmp:' 'original size' '275,' 'current size' "$shar_count!"
fi
fi
# ============= sample2.tcl ==============
if test -f 'sample2.tcl' && test "$first_param" != -c; then
$echo 'x -' SKIPPING 'sample2.tcl' '(file already exists)'
else
$echo 'x -' extracting 'sample2.tcl' '(text)'
sed 's/^X//' << 'SHAR_EOF' > 'sample2.tcl' &&
#!/usr/local/bin/wish
X
pack [canvas .c]
X.c create oval 10 10 50 50 -fill black -stipple @gray25.bmp
X.c create oval 30 30 70 70 -fill black -stipple @gray50.bmp
SHAR_EOF
$shar_touch -am 0827095496 'sample2.tcl' &&
chmod 0775 'sample2.tcl' ||
$echo 'restore of' 'sample2.tcl' 'failed'
if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
&& ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
md5sum -c << SHAR_EOF >/dev/null 2>&1 \
|| $echo 'sample2.tcl:' 'MD5 check failed'
7194cd0264f59c58d823c9c9325e0793 sample2.tcl
SHAR_EOF
else
shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'sample2.tcl'`"
test 160 -eq "$shar_count" ||
$echo 'sample2.tcl:' 'original size' '160,' 'current size' "$shar_count!"
fi
fi
rm -fr _sh04283
exit 0

Michel Dalle

unread,

Aug 29, 1996, 3:00:00 AM8/29/96

to

In article <4vuq0d$o...@news.sns-felb.debis.de>,

I'm glad to see such enthusiasm, but have you taken a look at tkmapedit, or at
mapmarker ? They might already contain most of what you want...

Both should be available on an ftp site near you :-)

Michel.

Jeffrey Hobbs

unread,

Aug 29, 1996, 3:00:00 AM8/29/96

to

In article <3225A4...@sungardss.com>,
Jay Schmidgall <jay.sch...@sungardss.com> wrote:
>Why not just let the canvas figure it out, right? If you are using the
>canvas' oval item, you have the x1 y1 x2 y2 coordinates of the bounding
>box for the oval. So, after drawing the oval, just ask the canvas to

Because box != oval, and overlapping bounding box != overlapping ovals.
Consider this: _
_ / \
/ \\_/
\_/

You'll have to do the math.

--
Jeffrey Hobbs office: 541.683.7891
Nomad of the 'Net email: jho...@cs.uoregon.edu
URL: http://www.cs.uoregon.edu/~jhobbs/

Jay Schmidgall

unread,

Aug 29, 1996, 3:00:00 AM8/29/96

to

wi...@news.sns-felb.debis.de wrote:
> Bing Zhang (bzh...@sohar.com) wrote:

> : One proposal is to detect the overlapping region and fill it accordingly. I
> : have not seen a good algorithm to calculate the intersecting points of arcs
> : and define the region. The overlapping region consists of arcs, not lines, so
> : the region is not a polygon and the "fill" option of the canvas may not be
> : used.
>
> It's possible to calculate if and what area of two circles
> overlap. This is more a mathematical problem than a Tcl one.
> Anyway.
>
> Given two midpoints of two circles you can calculate the
> distance between them by sqrt((x1-x2)**2 + (y1-y2)**2) (**
> means power). The two circles overlap if the distance is
> less than the sum of the two radii.
>
> Another special case is if one circle is completely covered
> by the other one. Easy to detect because in that case the
> distance plus one radius is less than or equal to the other
> radius.
>
> The last case is where the two circles intersect but none is
> covered completely by the other - that's a bit tricky. So
> let's show a little graph:

Why not just let the canvas figure it out, right? If you are using the

canvas' oval item, you have the x1 y1 x2 y2 coordinates of the bounding
box for the oval. So, after drawing the oval, just ask the canvas to

find any overlapping or enclosed items in that region. You know,
perhaps something like

.canvas find overlapping x1 y1 x2 y2

which will give you any items completely enclosed by or overlapping the
given region. Seems a bit easier than having to duplicate the math,
anyways.

Of course, that doesn't help with coloring the specific areas that
overlap, but if the suggested stippling idea works, you wouldn't even
have to worry about that.

: jay

Tom Poindexter

unread,

Aug 29, 1996, 3:00:00 AM8/29/96

to

In article <504cnr$p...@snidns.ch.sni.be>,

Michel Dalle <Michel...@sni.be> wrote:
>In article <4vuq0d$o...@news.sns-felb.debis.de>,
> wi...@news.sns-felb.debis.de () wrote:

Also take a look at MapEdit, a fine piece of software for mapping using
USGS Digital Line Graphs as input data. I've bugged the author recently
to include support for the 1:2,000,000 data as well as 1:100,000 previously
supported (thanks Jan!!)

See Jan's MapEdit page for info and source at:

http://www1.ridgecrest.ca.us/~jan/me/me.html

The program reads the older "optional" USGS formatted datasets, still
available at ftp://spectrum.xerox.com/pub/map/dlg

--
Tom Poindexter
tpoi...@nyx.net
http://www.nyx.net/~tpoindex/