help with script

[mawk]

I have a file that contains data with xy coordinates such as:
111 1 125000 9100000
111 2 130000 9150000
222 1 140000 9150000
222 2 155000 9200000
333 1 210000 9190000
333 2 110000 9010000
333 3 125000 9110000
444 0 130000 9150000

The 3 and 4th fields are x and y respectively.

I also have a control file like:
100000 9000000
150000 9000000
155000 9100000
200000 9200000
125000 9200000
110000 9100000
100000 9000000
These points are also x and y in order.
This file is an outline described by 4 or more corner points and the first and last point repeating.
This file is an outline that I want to use against the first data file.

If a data point from file 1 has a x and y point that falls inside the boundary points of file 2, I would print the entire record from file 1 to output, if not the point is ignored and so on for entire file.

If a point from file 1 falls on the boundary line between 2 boundary points, i would like to keep these points also along with the inside points.

I'm not sure if this is a simple task for Awk, I hope so.
Any help would be appreciated.

 

[Salem]

This looks like the 'point inside the polygon' problem.

http://www.faqs.org/faqs/graphics/algorithms-faq/

Subject 2.03: How do I find if a point lies within a polygon?

I don't know how familiar you are with C, but I think the example C code can be converted into an AWK function by simply removing all the variable types

Since this test is likely to be slow, I would do this...

333 1 210000 9190000
333 2 110000 9010000
333 3 125000 9110000
If the first record (210000 9190000) is inside the polygon, then you can skip testing the remaining records for this particular shape.

 

[mawk]

Thanks for the help.
Here's what I have so far using the c code.
It still needs some help but not sure what to do.

I'm running it by gawk -v fn="polygon_file.dat" -f polygon_edit.gawk data_file.dat

and here's the awk script so far. I only want to print complete records that a xy point falls within the polygon boundary.

BEGIN {
if (!fn) fn = "polygon_file.dat"
while ((getline < fn) > 0) {
xp[$1]
yp[$2]
}
}
{
x=$3;
y=$4;

for (i = 0; j = npol-1; i < npol; j = i++) {
if ((((yp<=y) && (y<yp[j])) ||
((yp[j]<=y) && (y<yp))) &&
(x < (xp[j] - xp) * (y - yp) / (yp[j] - yp) + xp)) { print $0
}
}
}


Thanks very much for help.

 

[vgersh99]

disable the 'Process TGML' check-box and repost, pls!
your array indexing like are turning into Italics by TGML.

vlad
+----------------------------+
| #include<disclaimer.h> |
+----------------------------+

 

[mawk]

Here it is. Thanks vlad.

BEGIN {
if (!fn) fn = &quot;polygon_file.dat&quot;
while ((getline < fn) > 0) {
xp[$1]
yp[$2]
}
}
{
x=$3;
y=$4;

for (i = 0; j = npol-1; i < npol; j = i++) {
if ((((yp<=y) && (y<yp[j])) ||
((yp[j]<=y) && (y<yp))) &&
(x < (xp[j] - xp) * (y - yp) / (yp[j] - yp) + xp)) { print $0
}
}
}

 

[CaKiwi]

This is not tested but it is a more complete implementation of the C algorithm referenced by Salem

BEGIN {
if (!fn) fn = &quot;polygon_file.dat&quot;
while ((getline < fn) > 0) {
xp[$1]
yp[$2]
npol++
}
}
{
x=$3;
y=$4;
c=0
for (i = 0; j = npol-1; i < npol; j = i++) {
if ((((yp<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp))) && (x < (xp[j] - xp) * (y - yp) / (yp[j] - yp) + xp)) {
c = !c
}
}
if (c) print
}





CaKiwi

&quot;I love mankind, it's people I can't stand&quot; - Linus Van Pelt

 

[mawk]

CaKiwi,

I get a syntax error on line 13 on the for statement.
It doesn't like the i < npol;

Any ideas? Thanks

 

[CaKiwi]

The first ; should be a ,

for (i = 0, j = npol-1; i < npol; j = i++) {


CaKiwi

&quot;I love mankind, it's people I can't stand&quot; - Linus Van Pelt

 

[CaKiwi]

I just noticed another poblem

while ((getline < fn) > 0) {
xp[npol]=$1
yp[npol]=$2
npol++
}


CaKiwi

&quot;I love mankind, it's people I can't stand&quot; - Linus Van Pelt

 

[CaKiwi]

I got a chance to test it. awk gets a syntax error on the for statement so I changed it to

j = npol-1
for (i = 0; i < npol; j = i++) {

CaKiwi

&quot;I love mankind, it's people I can't stand&quot; - Linus Van Pelt

 

[mawk]

CaKiwi,

Do you get a few points passed to output that fall inside the polygon file? When I run it, I get nothing output.

Thanks

 

[CaKiwi]

Here's the awk program I used

BEGIN {
if (!fn) fn = &quot;polygon_file.dat&quot;
while ((getline < fn) > 0) {
xp[npol]=$1
yp[npol]=$2
npol++
}
}
{
x=$3
y=$4
c=0
j = npol-1
for (i = 0; i < npol; j = i++) {
if ((((yp<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp))) && (x < (xp[j] - xp) * (y - yp) / (yp[j] - yp) + xp)) {
c = !c
}
}
if (c) print
}

Here's the output I get

111 1 125000 9100000
111 2 130000 9150000
222 1 140000 9150000
333 2 110000 9010000
333 3 125000 9110000
444 0 130000 9150000


CaKiwi

&quot;I love mankind, it's people I can't stand&quot; - Linus Van Pelt