Thread history

From User talk:Rednaxela/kD-Tree
Viewing a history listing
Jump to navigation Jump to search
Time User Activity Comment
23:45, 25 March 2013 Wolfman (talk | contribs) New thread created  
00:28, 26 March 2013 Rednaxela (talk | contribs) New reply created (Reply to Null Pointer Exception - 3rd Gen Tree)
08:43, 26 March 2013 Wolfman (talk | contribs) New reply created (Reply to Null Pointer Exception - 3rd Gen Tree)
14:50, 26 March 2013 AW (talk | contribs) New reply created (Reply to Null Pointer Exception - 3rd Gen Tree)
15:06, 26 March 2013 Wolfman (talk | contribs) New reply created (Reply to Null Pointer Exception - 3rd Gen Tree)
15:30, 26 March 2013 Rednaxela (talk | contribs) New reply created (Reply to Null Pointer Exception - 3rd Gen Tree)

Null Pointer Exception - 3rd Gen Tree

Hiya,

Getting an occasional null pointer exception. I've not worked out why its happening, and looking at the source I can't quite see how it could happen. Call stack looks like

at KDTree.KdNode.addLeafPoint(KdNode.java:70) at KDTree.KdNode.splitLeafNode(KdNode.java:173) at KDTree.KdNode.addLeafPoint(KdNode.java:79) at KDTree.KdNode.addPoint(KdNode.java:63) at KDTree.KdTree.addPoint(KdTree.java:1)

Any ideas?

Wolfman23:45, 25 March 2013

Seems that the "points" array is getting set to 'null' in a newly created child node. Assuming you haven't modified the code of the tree, and you're not doing any multithreading things, I can only see one possible cause: *All* of the data points are being put in the same child node, causing the newly created child node to itself be split while the upper level's splitLeafNode is still running. This implies that calculateSplit() is returning true when it shouldn't.

Could you add code to line 169 to print the list of coordinates stored in the node being split, or use a debugger to obtain similar information? My suspicion is that the coordinates you're putting into the tree are very unusual in some manner, possibly involving NaN values.

Rednaxela00:28, 26 March 2013
 

Sorry for the wall of numbers. Here are the values inside the splitLeafNode function:

Points array: [ [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.27476300750221805, 0.0, 0.5, 0.5, 0.05944248946787964, 0.05944248946787964], [0.25781116652220715, 0.08692892561404503, 0.49442777954156447, 0.525842295924762, 0.06786100210077804, 0.14692687699385826], [0.2578177856998261, 0.08372619661301722, 0.49463837126786636, 0.5064605739811905, 0.06785023783184158, 0.1469334424631162], [0.2578214298492213, 0.08292549845220197, 0.4946909579122118, 0.5016151434952976, 0.06784441533138576, 0.14693385451422164], [0.25782433041558794, 0.08272532316252756, 0.49470410169693013, 0.5004037858738244, 0.06783982767738157, 0.14693272660841677], [0.25782704507786713, 0.0826752795385066, 0.4947073884210326, 0.500100946468456, 0.06783554880964597, 0.14693121360417843], [0.25782971324440696, 0.0826627688903635, 0.4947082111092713, 0.5000252366171141, 0.0678313472047577, 0.14692960432136848], [0.2578323697665857, 0.08265964148995872, 0.4947084178030773, 0.5000063091542785, 0.06782716496882069, 0.14692797097446295], [0.25783502335720493, 0.08265885990173155, 0.49470847049921196, 0.5000015772885695, 0.06782298762433847, 0.14692633161848062], [0.2578376761944629, 0.0826586647665601, 0.49470848469597223, 0.5000003943221424, 0.06781881155096657, 0.14692469076738635], [0.25784032882290964, 0.08265861624464657, 0.49470848926786565, 0.5000000985805355, 0.06781463584332002, 0.14692304954976892], [0.2578429813786835, 0.0826586043760398, 0.49470849143351225, 0.5000000246451339, 0.06781046027498529, 0.14692140824779062], [0.2578456338958197, 0.08265860167075158, 0.4947084929975659, 0.5000000061612835, 0.06780628478936644, 0.1469197669319714], [0.2578482863828274, 0.08265860125628488, 0.49470849441118986, 0.5000000015403209, 0.06780210937228809, 0.1469181256199622], [0.2578509388418348, 0.08265860141451545, 0.49470849578717485, 0.5000000003850803, 0.06779793402021453, 0.14691648431616464], [0.2578535912733745, 0.08265860171591212, 0.49470849715371845, 0.5000000000962701, 0.06779375873223772, 0.14691484302170008], [0.2578562436775801, 0.08265860205309222, 0.4947084985178703, 0.5000000000240675, 0.0677895835081634, 0.146913201736816], [0.257858896054486, 0.08265860239921004, 0.49470849988139254, 0.5000000000060169, 0.06778540834789157, 0.14691156046162138], [0.2578615484041011, 0.0826586027475541, 0.49470850124472593, 0.5000000000015042, 0.06778123325144109, 0.1469099191960998], [0.25786420072642846, 0.08265860309644661, 0.4947085026079805, 0.500000000000376, 0.06777705821881806, 0.1469082779402436], [0.2578668530214694, 0.08265860344546808, 0.4947085039711838, 0.500000000000094, 0.06777288324998178, 0.14690663669408965], [0.25786950528922475, 0.08265860379451359, 0.4947085053343428, 0.5000000000000234, 0.06776870834495623, 0.1469049954576125], [0.25787215752969567, 0.08265860414355704, 0.49470850669745914, 0.5000000000000058, 0.06776453350371553, 0.14690335423083412], [0.2578748097428828, 0.08265860449259181, 0.4947085080605333, 0.5000000000000014, 0.06776035872627743, 0.1469017130137357], [0.25787746192878697, 0.08265860484161626, 0.4947085094235653, 0.5000000000000003, 0.0677561840126425, 0.1469000718063138], [0.2578801140874092, 0.08265860519062998, 0.4947085107865553, 0.5000000000000001, 0.06775200936277642, 0.14689843060859753], null ] bucket capacity is 50 Size is currently 48 Split dimension is 5 Split value is 0.10318817199105064

Wolfman08:43, 26 March 2013
 

The last point there is null...

AW14:50, 26 March 2013
 

Yes but its index 49, and size is currently 48. :)

Wolfman15:06, 26 March 2013
 

Yeah, that null there is not a problem, though it does look like I accidentally made the nodes split one entry too early. That wouldn't cause any issue besides a tiny amount of wasted memory though.

Later today I'll see if I can replicate the issue with that list of points.

Rednaxela15:30, 26 March 2013