>>> Veli D Tough Question <<<

[Chris]

Hey! guys, I got one tough question that I can't figure it. Hope your guys lend me a hand.

Here the cenario:
I've a data file that will store a fews hundred line of data and the data is look like below:

Item01=100,3;101,4;101,4.5;101.8,3
Where:
Item01 mean the Line description
The value after "=" sign is the X,Y coordinate seperate by semi-colon (delimiter)
100,3
101,4
101,4.5
101.8,3

What is the best algorithm to calculate the line build up from those X,Y coordinate after the
"=" sign is fall inside or outside the given rectangular as below:

Rectangular No.1 with (99,5)-(102,2)
Upper Left value (99,5)
Lower Right value (102,2)

and Rectangular No.2 with (100,5)-(100.5,4)
Upper Left value (100,5)
Lower Right value (100.5,4)

NOTE:
You're not allow to split those X,Y coordinate.


Regards,
Chris.C

[kedaman]

If youre not allowed to use split function? That sounds very stupid. I guess you can use Instr and Mid instead then.

I'm not getting the qwestion either and what do you mean a line built up from 4 coordinates?!? What has the line description to do with anything and how does the rectangle affect the lines?

[Chris]

Kedaman,

First let me make my question more clear.
Item01=100,3;101,4;101,4.5;101.8,3

Above is the data use to build a line by using the Polyline API function and the Item01 is the line's description
which will be display by using the DrawText API
function.

What I mean the line is build up by 4 points from the data
show above.

(100,3)
(101,4)
(101,4.5)
(101.8,3)

That is :

Option Explicit
Private Declare Function Polyline Lib "gdi32" (ByVal hdc As Long, lpPoint As POINTAPI, ByVal nCount As Long) As Long
Private Declare Function DrawText Lib "user32" Alias "DrawTextA" (ByVal hdc As Long, ByVal lpStr As String, ByVal nCount As Long, lpRect As RECT, ByVal wFormat As Long) As Long
Private Declare Function SelectObject Lib "gdi32" (ByVal hdc As Long, ByVal hObject As Long) As Long
Private Declare Function GetDC Lib "user32" (ByVal hwnd As Long) As Long
Private Declare Function DeleteObject Lib "gdi32" (ByVal hObject As Long) As Long
Private Declare Function ReleaseDC Lib "user32" (ByVal hwnd As Long, ByVal hdc As Long) As Long
Private Declare Function SetRect Lib "user32" (lpRect As RECT, ByVal X1 As Long, ByVal Y1 As Long, ByVal X2 As Long, ByVal Y2 As Long) As Long
Private Declare Function CreatePen Lib "gdi32" (ByVal nPenStyle As Long, ByVal nWidth As Long, ByVal crColor As Long) As Long

Private Const PS_SOLID = 0

Private Type POINTAPI
        x As Long
        y As Long
End Type
Private pt As POINTAPI

Private Type RECT
        Left As Long
        Top As Long
        Right As Long
        Bottom As Long
End Type
Private rc As RECT

Private Sub DrawData()
Dim hdc As Long
Dim hPen As Long

hdc = GetDC(Picture1.hwnd)
hPen = CreatePen(PS_SOLID, 1, RGB(255, 0, 0))
SelectObject hdc, hPen

Polyline hdc, pt(0), 4
DeleteObject hPen
ReleaseDC hdc
End Sub

I juz show path of the code. The reason why I does not
allow using Split function is because the X,Y coordinate
can be growth upto 200++ pair of XY value.

So, I only Split and store into a POINTAPI structure. That
a few steps before I start draw the line with the Polyline
API.

I during the validation sction, I also Split the data, the it may take even more processing time to juz draw a single
line. So, I need a kind of algorithm that can enable me to
check a stream of XY value is inside or outside the given
rectangular.

Hope this make it more clear to those are interested and wish to lend me hie/her hand.

Cheers!

[rekcus]

Wierd question...

Let me try to understand what your question is about.

1 You have two rectangles with known coordinates
2 You have a file with many items that are actually
coordinates of a line..

And you want to find the best way to check if these items
in the file are in your rectangles or not. Correct?

[Chris]

rekcus, you're rite.
So do you've any idea abt this?

[kedaman]

x<left or x>right or y<top or y>bottom
should return true if outside a rectangle. Use this for all points/rectangles, i'm still not sure what youre trying to approach.

[Chris]

Okay, Kedaman
Here is more simplified what I intend to archieve.

I have 4 pair of XY coordinate from the following string od data:
Item01=100,3;101,4;101,4.5;101.8,3

When the XY coordinate is seperate by the delimiter, it look like this:
Point 1 = (100,3)
Point 2 = (101,4)
Point 3 = (101,4.5)
Point 4 = (101.8,3)

When all this 4 point connect to next XY value you'll have a line:

(Point 1) <-> (Point 2) <-> (Point 3) <-> (Point 4)

Hence, I want to determine is this line cross the following
2 rectangulars (99,5)-(102,2) and (100,5)-(100.5,4)

Here is more detail of the 2 rectangular XY value:
(99,5)-(102,2)
Upper Left value (99,5)
Lower Right value (102,2)

(100,5)-(100.5,4)
Upper Left value (100,5)
Lower Right value (100.5,4)

Am I make it clear for your? Hope I do so.
I want to archieve this without split the XY value into
individual set as show above.

Can this be archieve?

[kedaman]

Here's what you need, that is if it's really the intersection you want to detect, note you have to change the names of the UDT's
The reason you need to this is because of the possibility of a line crossing trough 2 border walls of a rectangle.

Function ISCross(lne1 As Cline, lne2 As Cline, intersection As Coordinate) As Boolean
    Dim dx1!, dy1!, dx2!, dy2!, n!, s!
    dx1 = lne1.coord2.X - lne1.coord1.X
    dy1 = lne1.coord2.Y - lne1.coord1.Y
    dx2 = lne2.coord2.X - lne2.coord1.X
    dy2 = lne2.coord2.Y - lne2.coord1.Y
    If (dx2 * dy1 - dy2 * dx1) = 0 Then
        'they are parallell
        ISCross = False
        Exit Function
    End If
    
    n = (dx1 * (lne2.coord1.Y - lne1.coord1.Y) + dy1 * (lne1.coord1.X - lne2.coord1.X)) / (dx2 * dy1 - dy2 * dx1)
    s = (dx2 * (lne1.coord1.Y - lne2.coord1.Y) + dy2 * (lne2.coord1.X - lne1.coord1.X)) / (dy2 * dx1 - dx2 * dy1)
    ISCross = s >= 0 And s <= 1 And n >= 0 And n <= 1
    'the intersection is then:
    If ISCross Then intersection.X = lne1.coord2.X + s * dx1: intersection.Y = lne1.coord2.Y + s * dy1
End Function

Think the rectangles of 4 lines and test each wall with each line. Yes, you have 3 lines (it seems like) whereas each second is the first coordinate in the next, except the last. If you want you could have this algoritm short circuit by exiting the loop as soon as intersection is detected, or if crossing trough 2 wall occurrs very seldom: use the boolean expression i mentioned earlier to check if points are outside/inside and then use XOR operator to detect one wall crossing. If we assume no 2 wall crossing you don't need ISCROSS function at all, just loop and xor the expression until it fails.

[Chris]

Thanks Kedaman, your formula is pretty good. I almost forget all abt the differentiation formula
which I've learn from my lecturer. As from your suggestion, I still need to split all the XY value
rite. I my above mention example, it juz 4 pair of XY value. But the real data can have more than
100++ pair of XY. So it sure will take some time to split it and comapre all the line.

It may not be efficiency way for my program to do so. 'Coz if I can split all the XY value, I can
straigh proceed to draw the line with the Polyline API without chicking it. My concern is how am I
can figure out if the line is cross the border of the given rectangular without split the XY value.

Then this will much more improve my program. hope you get what I mean.

[kedaman]

spliting 100 pairs of XY won't take that much time Chris, how much would you need? What is this file for? If you want you could store the data again, binary and you don't need to split a ****.

[Chris]

kedaman, eventually I'll implement it in VC++/
My data file can content upto 1000++ lines of data and
each line can have 200++ pairs of XY value.

I'll post the data later and let you have a llok on it.

[Chris]

Kedaman, here juz some of my data. Do you've any idea how I ccan iplement it.

[ROAD]
R79=JALAN KUCHING;2;255;1;101.6692,3.19;101.6693,3.189816;101.6699,3.187189;101.67,3.186599
R97=JALAN SRI HARTAMAS 1;2;255;1;101.6682,3.17;101.6682,3.17;101.6683,3.170009;101.6683,3.170013;101.6684,3.170012;101.6684,3.170011;101.6691,3.17
R145=JALAN SEGAMBUT;2;255;1;101.6517,3.177401;101.6532,3.18142;101.6535,3.181972;101.6551,3.183172;101.6555,3.183514;101.6557,3.183813;101.656,3.184615;101.6562,3.184912;101.6566,3.185177;101.6626,3.187204;101.6628,3.18731;101.6628,3.18731;101.6628,3.187327;101.663,3.187368;101.6631,3.187348;101.6632,3.187301;101.6632,3.187301;101.6634,3.187181;101.6639,3.187061;101.6641,3.18706;101.6659,3.187194;101.6665,3.187157;101.6672,3.186949;101.6674,3.1868;101.67,3.185074
R240=JALAN BUKIT MAHKAMAH;3;0;1;101.67,3.171114;101.6696,3.171592;101.6695,3.171868;101.6695,3.172264;101.6695,3.172348;101.6695,3.172348;101.6697,3.173167;101.6697,3.173167;101.6698,3.173298;101.67,3.173625
R1362=PERSIARAN ARFAH;3;0;1;101.6694,3.189005;101.67,3.189039
R1439=JALAN KELAPA BULAN;3;0;1;101.6627,3.19;101.6633,3.189265;101.6637,3.188344;101.6638,3.187917;101.6638,3.187917;101.6639,3.187583;101.6643,3.187075
R1440=JALAN SELUDANG;3;0;1;101.6633,3.189265;101.6641,3.19
R2452=JALAN  KELAPA HIJAU;3;0;1;101.6589,3.185999;101.6591,3.185346;101.6592,3.185257;101.6593,3.185201;101.6594,3.185189;101.6595,3.185204;101.6595,3.185205;101.6605,3.185763;101.6606,3.185788;101.6607,3.185764;101.6608,3.185705;101.6608,3.185621;101.6608,3.185555;101.6609,3.184238
R2453=JALAN 1/38B;3;0;1;101.6609,3.184238;101.6609,3.181852;101.6608,3.181596;101.6606,3.181006;101.6601,3.180535;101.6594,3.180336;101.6578,3.18027;101.6573,3.180224;101.657,3.18009;101.6564,3.179787;101.6563,3.179741;101.6562,3.179747;101.6561,3.179778;101.6551,3.180384
R2454=JALAN 2/38B;3;0;1;101.6609,3.184248;101.6595,3.18421;101.6592,3.184135;101.659,3.18404
R2455=JALAN 3/38B;3;0;1;101.6588,3.180315;101.6588,3.183765;101.6588,3.183851;101.6589,3.183955;101.659,3.184049
R2456=JALAN 5/38B;3;0;1;101.6594,3.180336;101.6593,3.183992
R2457=JALAN 4/38B;3;0;1;101.6605,3.184236;101.6605,3.18224;101.6605,3.182113;101.6604,3.181864;101.6602,3.181304;101.6601,3.181217;101.6601,3.181217;101.6598,3.181046;101.6595,3.180962;101.6588,3.180924
R2458=JALAN 9/38B;3;0;1;101.6594,3.182117;101.6605,3.182128
R2459=JALAN 8/38B;3;0;1;101.6594,3.182562;101.6605,3.1826
R2460=JALAN 7/38B;3;0;1;101.6594,3.183073;101.6605,3.183093
R2461=JALAN 6/38B;3;0;1;101.6593,3.183547;101.6605,3.183557
R2462=JALAN 1/60A;3;0;1;101.6572,3.180165;101.657,3.185321
R2463=JALAN 2/60A;3;0;1;101.6588,3.181793;101.6571,3.181708
R2464=JALAN  KELAPA MUDA;3;0;1;101.659,3.1869;101.6593,3.186152
R2465=JALAN  KELAPA GADING;3;0;1;101.6579,3.185643;101.6576,3.186352;101.6573,3.187366
R2466=LENGKOK KELAPA;3;0;1;101.6573,3.187366;101.6576,3.187379;101.6579,3.187356;101.6581,3.187285;101.6582,3.187172;101.6582,3.187146;101.6582,3.187146;101.6583,3.186844;101.6584,3.186763;101.6584,3.186763;101.6584,3.186749;101.6584,3.186692;101.6583,3.186638;101.6583,3.186595;101.6582,3.186565;101.6576,3.186352
R2467=JALAN  KELAPA;3;0;1;101.6573,3.185433;101.6571,3.185806;101.6569,3.18638;101.6569,3.186581;101.6569,3.186927;101.6569,3.186927;101.6569,3.186962;101.6569,3.187126;101.6571,3.187271;101.6573,3.187366
R2469=NKVE;1;32768;1;101.65,3.175279;101.6517,3.175097;101.6567,3.175794;101.6596,3.176948;101.6604,3.177002;101.6613,3.176402;101.6613,3.1764;101.6613,3.1764;101.6615,3.175378;101.6614,3.174892;101.6607,3.172737;101.6605,3.171833;101.6605,3.171218;101.6606,3.171012;101.6606,3.171012;101.6608,3.17001;101.6608,3.17
R3410=JALAN;2;255;1;101.65,3.172775;101.651,3.173486;101.6512,3.175149
R3587=JALAN BUKIT KIARA;2;255;1;101.6534,3.17;101.6538,3.171243
R4059=JALAN 4/38A;3;0;1;101.6562,3.184925;101.6553,3.185081;101.6546,3.185602;101.6541,3.186752
R6265=JALAN 6/38A;3;0;1;101.6529,3.185833;101.6536,3.186603;101.6541,3.186752;101.6553,3.186923
R6266=JALAN  PERUT PUTIH  8;3;0;1;101.65,3.187923;101.6513,3.187041;101.6529,3.185833
R6267=JALAN 30/38A;3;0;1;101.65,3.188102;101.6509,3.18935;101.6511,3.19
R6335=JALAN 1/38A;3;0;1;101.6553,3.186923;101.6553,3.185081

[rekcus]

Hi guys... Chris, can't think of an easy way to quickly
solve your problem. With your kind of data, it will
definitely take a lot of processing power to go through
all that.
And from the looks of it, you may have the only choice of
sequentially calculating if each of the portions belong to
touch the rectangle or not.

Good luck thou.

[kedaman]

I'd say that would take less than 10'th of as second, I know ppl don't like parsing, it's an ugly tiresome method (except if you split strings) it's mechanical and easy though.
Are you allowed to change the data at all? if youre concerned about the speed, i'd store it binary, but you'd have to do the parsing at least once to store it binary.

[Chris]

At first I plan to store it as binary. But I really no idea how it can be done. Therefore, I juz store the data as what
I show you in my previous post.

Parsing a string is not a difficult task. As long as the
data format is fixed and we know what we're looking at.
Then everyhing will br going smooth.

To do the parsing before we store the data is the best
solution and I agree with you too. Perhaps you can explain
and show some example how can I store the data in binary
format and make life easy when reading the data.

Again thanks for your interested in my post. Seem you're
contribute most idea to me. Man )

[kedaman]

The data you posted don't look fixed at all, you have strings and dynamic amount of coordinates, that makes it a bit complicated to store, not that it is. All numeric values are single datatype i guess, which makes 8 bytes/coordinate.
I'm not sure about the strings and stuff to the left, but if we'd say its a varlen string, and the coordinates is dynamic array of a udt with two singles, we could pick up a primary and a secondary header:

Type Primheader
	Items as long 'amount of items
End Type
Type Secheader
	VarstrL() as byte'length of string
	CoordL() as byte'amount of coordinates
End type
Type Data
	VarStr() as string
	Coord() as Coordinate
End type

This should make a reasonable file structure for your binary file. When you open the file, you read the primary header first, then redim the items in secheader, read the secheader and then buffer the strings in Data and redim the coord. Next you read the Data section. To store you just put primheader, secheader and data (in that order).

[Chris]

Thanks kedaman, you're my hope & i'll do it and back to you soon. )

[Chris]

Kedaman, can you help me?

http://forums.vb-world.net/showthrea...751#post205751

[Chris]

Kedaman, Does you mean the Primheader and Seecheader need to be store in
seperate file from the data file?

[code]
'So call reference file

Type Primheader
	Items as long 'amount of items
End Type
Type Secheader
	VarstrL() as byte'length of string
	CoordL() as byte'amount of coordinates
End type

'So call all the data file
Type Data
	VarStr() as string
	Coord() as Coordinate
End type

That mean, I've 2 file. first file is store all the Maximum array size for each set
of data and the second file is store all the data. Hence I can Redim my array before I
use Get to read the data?

Thanks

Originally posted by kedaman
The data you posted don't look fixed at all, you have strings and dynamic amount of coordinates, that makes it a bit complicated to store, not that it is. All numeric values are single datatype i guess, which makes 8 bytes/coordinate.
I'm not sure about the strings and stuff to the left, but if we'd say its a varlen string, and the coordinates is dynamic array of a udt with two singles, we could pick up a primary and a secondary header:

Type Primheader
	Items as long 'amount of items
End Type
Type Secheader
	VarstrL() as byte'length of string
	CoordL() as byte'amount of coordinates
End type
Type Data
	VarStr() as string
	Coord() as Coordinate
End type

This should make a reasonable file structure for your binary file. When you open the file, you read the primary header first, then redim the items in secheader, read the secheader and then buffer the strings in Data and redim the coord. Next you read the Data section. To store you just put primheader, secheader and data (in that order).

[Edited by Chris on 01-16-2001 at 10:26 PM]

[kedaman]

I don't think you want that Chris, you could do so but i'm sure you're still thinking about random access files. They are just a limited version of binary; you have to read them record by record.

I think i would have to give you the exact code or you wouldn't see what i mean:

'To write
Open file for binary as 1
  put#1,,Primheader
  put#1,,Secheader
  put#1,,data
close 1
'to read
Open file for binary as 1
  get#1,,Primheader
  redim Secheader.Varstrl(primheader.items-1)
  redim Secheader.Coordl(primheader.items-1)
  redim data(primheader.items-1)
  get#1,,Secheader
  for x=0 to primheader.items-1
    data(x).VarStr=space(secheader.VarstrL(x))
    redim data(x).Coord(secheader.CoordL(x)-1))
  next x
  get#1,,data
close 1

Sorry about the VarStr in Data section, it meant not to be an array of strings but a varlen string. Otherways you would need a third header Hope you see what i mean now

[Chris]

Great Man! Hope I won't reply this post later on.

Thanks Kedaman )