Hi again,
I'm not sure who is interested, but with your help especially concerning /. and
#^:_1 I arrived at the following.
I have points xyz:
$xyz
1093414 3
10{.xyz
0 0 0
92225.8 434950 2.65
92225.5 434950 2.65
92225.3 434951 2.66
92225 434951 2.68
92226.5 434950 2.66
92226.3 434950 2.67
92226 434951 2.67
92225.8 434951 2.66
92225.5 434951 2.67
(the triangulation software wants the first point to be number 1)
and I have triangles tri:
$tri
2177070 3
10{.tri
25669 40050 7894
7894 40050 25577
7894 40049 14657
3 14660 14657
40050 34010 25577
25669 7894 14657
25669 34100 4
34100 25669 14660
14660 40141 34100
3 40141 14660
I want a list of sets of neighbors, one set for each point, and with an empty
slot for unused points.
6!:2 't =. |: tri' NB. $tri = ntri,3
0.093476
6!:2 't =. t,.(1|.t),.(2|.t)' NB. triplicate with rotation
0.099777
6!:2 't =. |: (/:0{t) {|: t' NB. sort according to top row
0.673855
6!:2 'e =. (i.1+_1{0{t) e. ~. 0{t' NB. which points are used (and which
ones aren't)
0.06735
6!:2 't =. (0{t) </. |:t' NB. grouping per point (the top row) into
boxes
1.12286
6!:2 't =. e #^:_1 t' NB. insert empty boxes for unused points
0.229392
All this is quick enough for me. Now I have a boxed list t:
$t NB. one for each point
1093414
6{.t
++-------------+-------------+-------------+-------------+-------------+
||1 14662 34009|2 14659 25576|3 14660 14657|4 25761 14701|5 39780 33920|
||1 25484 39868|2 39958 34009|3 40141 14660|4 14701 34457|5 7895 14666|
||1 14661 25483|2 34009 40048|3 25668 40141|4 40231 25761|5 33920 7895|
||1 39868 14661|2 25576 39958|3 14663 7898|4 25669 34100|5 14666 39780|
||1 25483 14662|2 40048 14659|3 40048 14663|4 34100 25668| |
||1 14658 25484| |3 7898 25668|4 25668 40231| |
||1 34009 14658| |3 14657 14659| | |
|| | |3 14659 40048| | |
++-------------+-------------+-------------+-------------+-------------+
(number 0 is empty, but there are other empty ones as well)
Furthermore I have an ugly verb mkstar that does:
mkstar >3{t
14660 14657 14659 40048 14663 7898 25668 40141 14660
mkstar >4{t
25669 34100 25668 40231 25761 14701 34457
Point 3 has neighbors all around, which is indicated by the first being the
same as the last.
Point 4 has not, because it is at the outer edge of the data set.
The complete boxed list is obtained with
6!:2 's =: mkstar each t'
39.6474
This is still acceptable, until you consider the AHN2 dataset, which covers the
entire Netherlands: 40000 sq. km. with 10 points/m^2) :-)
Thanks again,
Ben
________________________________________
From: programming-boun...@jsoftware.com [programming-boun...@jsoftware.com] on
behalf of Raul Miller [rauldmil...@gmail.com]
Sent: Wednesday, January 11, 2012 3:20 PM
To: Programming forum
Subject: Re: [Jprogramming] Boxes of different lengths
On Wed, Jan 11, 2012 at 4:55 AM, Ben Gorte - LR <b.g.h.go...@tudelft.nl> wrote:
> Thanks a lot to all for enlightening me!
>
>> DATA=: ".;._2]0 :0 0 0 1 1 1 1 2 2 2 2 2 4 4 4 5 5 5 0 7 8 9 2 2 5 5 5 3 8
>> 0 0 5 6)
Note that this line is bugged.
It was supposed to look like this (I hope this looks right):
DATA=: ".;._2]0 :0
0 0 1 1 1 1 2 2 2 2 2 4 4 4 5 5
5 0 7 8 9 2 2 5 5 5 3 8 0 0 5 6
)
In other words, four lines, with a line break between the first two
adjacent zeros, a line break between the second pair of adjacent fives
and a line break before the closing right parenthesis.
Unfortunately, gmail will not let me declare that all copy and paste
into a plaintext email composing region should be plain texts copy and
paste. And, worse, the default paste mechanism does not show me how
it will be represented when the email is sent. So I am composing
blind, and using a mechanism which is confusing.
>> 6 (</./@] #inv~ i.@[ e. {.@] ) DATA
>> 6 {. (</./ #inv~ (e.~ i.@(1 + >./))@{. ) DATA
>> I could not choose between these options without better understanding
>> your application.
>
> Well, my application ... continue reading at your own risk.
>
> I have (say) a million points (x,y,z) and I use software that makes a
> Delaunay triangulation (http://www.cs.cmu.edu/~quake/triangle.html):
> approximately two million triangles. Each triangle consists of three point
> numbers. Although my points are 3D, the triangulation is 2D and z is merely
> an attribute (it is terrain height, but it could also be temperature).
>
> With each point I want to do "something" , which also depends on the point's
> neighbours: those points that are together with the considered point in a
> triangle. This is going to happen very often (different things that I want
> to do), and therefore I wondered whether it makes sense to find each point's
> set of neighbours only once and store that. Since the number of neighbours is
> not the same for each point (on average it is six), I was thinking of a boxed
> list. Occasionally an (x,y) occurs twice in the input data. Then only one of
> these points is used in the triangulation and for the other I get an empty
> slot in my list.
I would be careful about using boxed lists for this application.
Consider, for example:
size=: #@(3!:1)
size i. 4 4
176
size (<:/~ i.4) <@#"1 i.4 4
312
(I hope I pasted that in properly... I will find out when I send the message.)
Here, by saving only the data elements in the upper triangle, I have
increased the amount of space needed to represent the data. I have
also increased the complexity of any code that would process the data,
and I have increased how much time would be needed to process the
data.
Anyways, I try and save boxing for big, measurable advantages and
major code simplifications.
Zeros are nice for many of the remaining cases. Zero may be old
fashioned, but it's a good mechanism.
> I sort it from left to right according to the top row and then something like
> </. comes in. After that it gets again a bit complicated since I want the
> neighbours to be ordered (counter-clockwise). Fortunately all input triangles
> have the same orientation.
This might be a good candidate for boxing -- boxes that hold a lot of
stuff tend to amortize the cost of the box itself.
> Another envisaged use for storing the neighbours with each point is answering
> the question: which triangle contains a given (x,y). Normally this requires
> visiting half of the triangles on average (one million), or using a spatial
> index. Now it will be possible to start at an arbitrary location, step
> through a sequence of adjacent triangles in the right direction, and arrive
> after one thousand steps or so.
I do not know enough about this issue to make any useful suggestions.
However, this sounds like it might be a candidate for an index vector
or a selection mask.
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
